Методические рекомендации по решению предложенных олимпиадных задач

Часть 3. Методика проверки и система оценивания

решений задач регионального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году

• 
  общие методические рекомендации по проверки решений участников;
  
• 
  комплекты тестов в электронном виде, содержащие для каждой задачи файлы входных данных и соответствующие им файлы выходных данных (для некоторых задач имеются специально разработанные программы – генераторы тестов);
  
• 
  проверяющие программы, позволяющие для каждой задачи определять правильность полученного решения в автоматическом режиме и программы визуализаторы тестов;
  
• 
  систему оценки решений участников;
  
• 
  краткие методические рекомендации по решению предложенных олимпиадных задач.
  

1. 
   Общие методические рекомендации по проверки решений участников
   

1. 
   Всем участникам регионального этапа Всероссийской олимпиады школьников на каждом туре предлагается комплект из четырех задач, подготовленный в соответствии с п. 16 Положения о Всероссийской олимпиаде школьников, утвержденного Приказом Минобрнауки от 22 октября 2007 года
   № 286.
   
2. 
   Текст каждой задачи содержит описание задачи, максимальное время работы программы на отдельном тесте, размер доступной программе памяти в процессе ее исполнения, форматы входных и выходных данных и примеры входных и выходных данных.
   
3. 
   Заданные в условии каждой задачи ограничения на максимальное время работы программы ориентированы на использование при проверке решений участников компьютеров с процессором Celeron 3 ГГц. Именно такого типа компьютеры необходимо использовать для проверки решений участников, причем все решения должны проверяться на одинаковых компьютерах.
   

4. 
   Результатом решения всех предложенных задач является исходный текст программы на одном из разрешенных языков программирования – Pascal, C, С++, и Visual Basic. Допустимыми являются следующие среды программирования:
   

• 
  компиляция исходного текста программы;
  
• 
  последовательное исполнение полученного exe-файла для файлов с входными данными, соответствующих тестам из набора тестов для данной задачи,
  
• 
  сравнение результатов исполнения программы на каждом тесте с правильным ответом.
  

1. 
   Жюри должно использовать вполне определенные командные строки для компиляции решений, о чем участников следует известить до начала тура. Эту информацию необходимо разместить в Памятке участнику, например, в следующем виде:
   

2. 
   Размер файла с исходным текстом программы не должен превышать 256 килобайт. Время компиляции программы не должно превышать 1 минуты. В случае нарушения этих ограничений решение участника считается неправильным и никакие баллы за эту задачу участнику не начисляются Информация об этих ограничениях также должна быть размещена в Памятке участнику.
   

2. 
   Характеристика тестов для каждой задачи
   

1. 
   группа простых тестов;
   
2. 
   группа тестов на все частные случаи, позволяющие выявить особенности используемых алгоритмов;
   
3. 
   группа общих тестов (входят достаточно случайные тесты, разные по размеру: от простых тестов до сложных);
   
4. 
   группа антиэвристических тестов (тесты, позволяющие выявлять приближенные решения);
   
5. 
   группа тестов максимальной размерности (тесты с использованием максимальных значений входных переменных, позволяющие оценить эффективность предложенных алгоритмов или их работоспособность при максимальной размерности задачи).
   

• 
  исходный текст программы генератора тестов (она может называться «doall.dpr», «generateTests.dpr», «TestsGen.java», «write_tests.dpr», «TestGen.java», «numberes_gen.java»),
  
• 
  исходный текст программы визуализатора тестов («Visualizer.java», только в папках для тех задач, для которых она разработана);
  
• 
  пакетные файлы для генерации тестов («doall.cmd», «tall.cmd», «clean.cmd», «wipeall.cmd») и визуализации тестов («testvis.cmd»).
  

3. 
   Система оценки решений участников
   

1. 
   Решение каждой задачи оценивается из 100 баллов, то есть, максимальное количество баллов, которое участник может получить за полное решение каждой задачи, составляет 100 баллов.
   
2. 
   Общая оценка за решение отдельной задачи конкретным участником складывается из суммы баллов, начисленных ему по результатам исполнения всех тестов из набора тестов для этой задачи. Для предложенных центральной методической комиссией задач оценка для каждого теста представлена в таблице ниже.
   

   Задача	Количество тестов	Оценка теста
   1. Черно-белая графика	25	4 балла
   2. Газон	20	5 баллов
   3. Трамвай	50	2 балла
   4. Треугольники	25	4 балла
   5. Клавиатура	20	5 баллов
   6. Неправильное сложение	25	4 балла
   7. Числа	50	2 балла
   8. Перестановки	50	2 балла

3. 
   Итоговая оценка проверки решений всех задач олимпиады для каждого участника формируется как сумма полученных этим участником баллов за каждую задачу.
   

1. 
   небольшие тесты (1 – 11), допускающие решения с перебором пучков травы;
   
2. 
   средние тесты (12 – 15), выявляющие вычисление ответа с помощью 32-битного типа данных;
   
3. 
   большие тесты (16 – 20), допускающие только правильное решение.
   

1. 
   решения со временем работы O(r²), перебирающие все постриженные пучки травы и считающие количество политых среди них (решения оцениваются из 55 баллов);
   
2. 
   решения, оперирующие 32-битными числами (решения оцениваются из 70 баллов);
   
3. 
   решения, содержащие различные ошибки при увеличении ответа (решения оцениваются из 80 баллов).
   

1. 
   небольшие тесты (1 – 30), оценивающие неэффективные решения, имеющие худшие асимптотические оценки, чем O(N∙P);
   
2. 
   средние тесты (31 – 40), выявляющие решения, реализующие операции с упорядоченными множествами за линейное время;
   
3. 
   большие тесты (41 – 50), использующиеся для проверки только полных решений.
   

1. 
   неэффективные решения, реализующие операции с упорядоченными множествами за линейное время (решение оцениваются из 80 баллов);
   
2. 
   неэффективные решения, имеющие худшие асимптотические оценки, чем O(N∙P) (решение оцениваются из 60 баллов);
   
3. 
   решения, оперирующие 32-битными числами для подсчета ответа (решение оцениваются из 60 баллов).
   

1. 
   небольшие тесты (1 – 8), выявляющие решения, основанные на полном переборе всех треугольников;
   
2. 
   средние тесты (9 – 12), выявляющие решения, использующие вещественные числа;
   
3. 
   большие тесты (13 – 25), использующиеся для проверки только полных решений.
   

1. 
   неэффективные решения, такие как перебор и проверка всех возможных треугольников (решения оцениваются из 40 баллов);
   
2. 
   решения с потерей точности, использующие вычисление полярного угла и сортировку по этому значению (решения оцениваются из 60 баллов).
   

1. 
   небольшие тесты (1 – 10), содержащие не более чем трехзначные числа;
   
2. 
   средние тесты (11 – 19), содержащие не более чем пятизначные числа;
   
3. 
   большие тесты (20 – 25), содержащие 6- и 7-значные числа.
   

1. 
   небольшие тесты (1 – 30), выявляющие переборные решения;
   
2. 
   большие тесты (31 – 50), использующиеся для проверки полных решений.
   

1. 
   небольшие тесты (1 – 25), оценивающие переборные решения;
   
2. 
   средние тесты (26 – 42), выявляющие решения, использующие 32-битный тип данных;
   
3. 
   большие тесты (43 – 50), использующиеся для проверки полных решений.
   

1. 
   переборные решения (оцениваются из 50 баллов);
   
2. 
   решения, оперирующие 32-битными числами (оцениваются из 84 баллов).
   

4. 
   Краткие методические рекомендации по решению задач
   

ans := "";

while (a <> 0) or (b <> 0) do begin

ans := IntToStr(a mod 10 + b mod 10) + ans;

a := a div 10;

b := b div 10;

end;