Всероссийская олимпиада школьников 2005/2006

Информатика

III - этап
(областная олимпиада)

1. Введение
2. Методические рекомендации
3. Рекомендуемые задачи
   1. Задача А
   2. Задача B
   3. Задача C
   4. Задача D
   5. Задача E
   6. Задача F
   7. Задача G
4. Краткие комментарии к решению задач
5. Рекомендации по системе оценивания и тестированию решений участников
6. Результаты олимпиады
7. Тесты (463 Кб)

Введение

Настоящие методические материалы подготовлены Центральной методической комиссией по информатике и направлены на упорядочивание деятельности оргкомитетов, региональных методических комиссий по информатике и жюри при организации и проведении 3-го этапа Всероссийской олимпиады школьников по информатике в субъектах Российской Федерации.

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

Центральная методическая комиссия выражает надежду, что представленные материалы окажутся полезными при проведении краевых, республиканских и областных олимпиад по информатике, и желает успехов организаторам в их проведении. В случае необходимости, дополнительную информацию по представленным методическим материалам можно получить по электронной почте, обратившись по адресу vkiryukhin@nmg.ru в центральную методическую комиссию по информатике.

Для тех, кто интересуется уровнем сложности задач, предлагавшихся на последней международной олимпиаде по информатике в Польше, рекомендуем посетить официальный сайт олимпиады http://www.ioi2005.pl Здесь Вы найдете тексты задач на английском языке, тесты для всех задач, а также результаты олимпиады.

В настоящее время идет разработка официального олимпиадного портала, на котором, в том числе, будут представлены всероссийские и международные олимпиады по информатике. В марте-апреле планируется завершить его создание и начнется и в это же время его информационное наполнение. На этом портале отводится специальный раздел для освещения 3-го этапа Всероссийских олимпиад школьников по информатике, проводимого во всех субъектах РФ. Для размещения на этом портале информации о региональных олимпиадах по информатике необходимо сразу после их окончания предоставить в центральную методическую комиссию по информатике полную информацию о прошедших олимпиадах.

Председатель центральной методической комиссии по информатике В.М. Кирюхин

Методические рекомендации

1. При организации и проведении третьего этапа Всероссийской олимпиады школьников по информатике необходимо руководствоваться Положением о Всероссийской олимпиаде школьников, утвержденным Приказом Минобразования России № 4072 от 30 октября 2003 года.
2. Центральная методическая комиссия по информатике рекомендует проводить третий этап Всероссийской олимпиады школьников по информатике в два компьютерных тура, длительность каждого из которых не превышает 5-и часов.
3. При проведении компьютерных туров рекомендуется предоставить в распоряжение каждого участника олимпиады персональный компьютер на базе процессора с частотой не ниже 866 МГц и оперативной памятью не менее 256 Мбайт, стандартной клавиатурой US/РУС, мышью и SVGA монитором.
4. Для обеспечения равных условий всем участникам используемые во время соревнований компьютеры должны иметь одинаковые или близкие технические характеристики. Все компьютеры должны быть объединены в локальную вычислительную сеть.
5. При обеспечении каждого участника соревнований необходимым программным обеспечением следует учитывать, что при проведении заключительного этапа Всероссийской олимпиады школьников по информатике на рабочем месте каждого участника олимпиады инсталлируется следующее программное обеспечение:
   • Windows 2000/XP;
   • Far manager;
   • Borland Pascal 7.0;
   • Free Pascal 1.0.10
   • Borland C/C++ 3.1;
   • DJGPP 2.03 (включая GNU C/C++ 3.2.1, Rhide и Gdb);
   • Borland Delphi 6.0;
   • Microsoft Visual Basic 6.0;
   • Microsoft Visual C++ 6.0.
6. Рекомендуется в течение двух часов с момента начала тура предоставить возможность каждому участнику олимпиады задать вопросы членам жюри по условиям задач. Вопросы должны задаваться в письменном виде и формулироваться так, чтобы ответ был либо "да", либо "нет". Ответы жюри на вопросы участников могут быть следующими: "да", "нет", «без комментариев».
7. Участникам олимпиады категорически запрещается во время туров пользоваться личными компьютерами, калькуляторами, электронными записными книжками, средствами связи (пейджерами, мобильными телефонами и т.п.), принесенными электронными носителями информации (дискетами, CD- и DVD-дисками, модулями флэш-памяти и т.п.), а также учебной литературой и заготовленными личными записями.
8. Участникам олимпиады разрешается использование в решениях задач любых внешних модулей и заголовочных файлов, включенных в стандартную поставку соответствующего компилятора.
9. В решениях задач участникам запрещается:
   • использовать инструкции ассемблера в тексте программы;
   • использовать расширенную и дополнительную память в программах на Borland Pascal и Borland C/C++;
   • создавать каталоги и временные файлы при работе программы;
   • осуществлять чтение и запись векторов прерываний;
   • любое использование сетевых средств;
   • любые другие действия, нарушающие работу проверяющей системы, если такая система используется при проведении олимпиады.
10. Во время тура участники олимпиады имеют право общаться только с представителями жюри, технического комитета, а также с находящимися в аудитории дежурными преподавателями.
11. В случае возникновения во время тура не по вине участника сбоев в работе компьютера или используемого программного обеспечения по решению жюри время, затраченное на восстановление работоспособности компьютера, может быть компенсировано.
12. По истечении времени тура участникам олимпиады запрещается выполнять любые действия на компьютере.
13. Категорически запрещается размещать тексты представленных в настоящих методических материалах задач на каких-либо сайтах и публиковать в открытых источниках до окончания проведения региональных олимпиад по информатике во всех субъектах РФ.

Рекомендуемые задачи

Ответственность за подготовку задач для 3-го этапа Всероссийской олимпиады школьников по информатике несет региональная методическая комиссия по информатике, формируемая органами управления образованием субъектов РФ до начала олимпиады.

Всем участникам олимпиады на каждом туре должны предлагаться одни и те же задачи. Рекомендуемое количество задач на каждом туре – три.

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

Для задач, в которых решением является программа, в условии указывается максимальное время работы программы на каждом тесте и размер доступной программе памяти. В случае превышение установленных ограничений, тест будет считаться не пройденным. При этом указанные ограничения по памяти включают всю память, используемую программой, в том числе память под код программы, системные нужды и т.д.

Решение должно выдавать одинаковые ответы на одинаковые тесты, вне зависимости от времени запуска и программного окружения. Жюри вправе произвести неограниченное количество запусков программы участника и выбрать наихудший результат по каждому из тестов.

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

Настоящие методические материалы содержат 7 задач. Конкретный набор задач для каждого тура определяется региональными методическими комиссиями и жюри региональных олимпиад в зависимости от уровня подготовленности участников. Тематика и сложность задач приведена в следующей таблице:

В мурманской области были выбраны 3 задачи: "Вырубка деревьев", "Разрезание торта", "Разнообразные строки".

Тексты рекомендуемых центральной методической комиссией задач представлены ниже.

Задача A «Палиндромы»

Известно, что палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, палиндромами являются строки «A», «ABA», «ABBA», а строки «AB», «AAB», «ABAB» палиндромами не являются.

Рассмотрим некоторую строку S, состоящую только из латинских букв A и B. Назовем запрещенными все строки длины n, которые состоят также только из букв A и B и содержат S в качестве подстроки. Например, если S = «AB» и n =3, то существует четыре запрещенных строки— «AAB», «ABA», «ABB» и «BAB». Остальные строки будет называть допустимыми.

Требуется написать программу, которая для заданной строки S длиной не более пяти символов и заданного числа n определяет количество допустимых строк длины n, которые являются палиндромами.

Формат входных данных

Первая строка входного файла содержит строку S. Длина строки S не превосходит пяти. Вторая строка содержит число n (1 <= n <= 100).

Формат выходных данных

Выведите в выходной файл одно число — количество строк длины n, которые являются палиндромами и не содержат S в качестве подстроки.

Примеры входного и выходного файлов

Пояснение к примеру

В приведенном примере две искомые строки — «AAA» и «BBB».

Задача B «Парикмахер»

Петин папа работает парикмахером. Его парикмахерская совсем не большая, и он — единственный парикмахер, который в ней работает. Парикмахерская открывается в 9:00 и закрывается в 17:00, но папа остается на работе, пока не обслужит всех клиентов, которые зашли в парикмахерскую до 17:00.

Обслуживание в парикмахерской происходит следующим образом. Когда очередной клиент заходит в парикмахерскую и парикмахер свободен, то он немедленно начинает стричься. В противном случае клиент ждет, пока закончится стрижка всех клиентов, которые вошли в парикмахерскую до него.

В течение дня каждый момент времени, когда в парикмахерскую заходит очередной клиент, записывается в журнале регистрации. Также в журнале регистрации записывается время, когда последний клиент покидает парикмахерскую. Чтобы оптимизировать свою работу, парикмахер хочет определить, сколько может продолжаться самая долгая стрижка. К сожалению, по указанным записям не всегда можно определить это точно. Поэтому для начала парикмахер хочет определить предельное время стрижки, а именно, какое минимальное время могла продолжаться самая долгая стрижка. Известно также, что любая стрижка занимает не менее пяти минут.

Требуется написать программу, которая по информации о моментах входа в парикмахерскую всех клиентов, а также моменту окончания стрижки последнего клиента, определяет, какое минимальное время могла бы продолжаться самая долгая стрижка.

Формат входных данных

Первая строка входного файла содержит число n — количество клиентов, обслуженных в рассматриваемый день (1 <= n <= 50). Следующие n строк содержат моменты времени входа клиентов в парикмахерскую в формате hh:mm. Времена заданы в порядке входа клиентов в парикмахерскую и находятся в диапазоне от 09:00 до 17:00. Последняя строка содержит время выхода из парикмахерской последнего клиента в формате hh:mm. Это время находится в диапазоне от 09:00 до 18:59.

Формат выходных данных

Выведите в выходной файл минимальное возможное время самой долгой стрижки в минутах. Ответ должен отличаться от правильного не более чем на 10^–8. Если парикмахер не может обслужить клиентов за указанное время, выведите «–1».

Примеры входных и выходных файлов

Пояснения к примерам

В первом примере, чтобы второму клиенту пришлось ждать времени окончания стрижки первого, тот должен был бы стричься более 7 часов. Второй же клиент освободился через 90 минут после того, как вошел в парикмахерскую, значит, самая долгая стрижка займет не менее 90 минут.

Во втором примере два клиента, которые зашли в 9:22, были суммарно обслужены за 49 минут. Они вошли через 22 минуты после первого клиента. Самая долгая стрижка в этом случае займет не менее 23 2/3 минут. Данная оценка достигается тогда, когда обслуживание всех трех клиентов продолжалось одно и то же время.

В последнем примере клиент был обслужен за одну минуту, чего не может быть по условию задачи.

Задача C «Вырубка деревьев»

Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

Требуется написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев и соседние деревья находились на равном расстоянии друг от друга.

Формат входных данных

Входной файл содержит два целых числа n и m (0 <= m <= n <= 1000).

Формат выходных данных

Выведите в выходной файл одно число — искомое количество способов.

Примеры входного и выходного файлов

Пояснение к примерам

Если обозначить условно исходное расположение деревьев перед дворцом как «TTTTT», то возможные результаты после вырубки следующие: «TTT..», «.TTT.», «..TTT», «T.T.T».

Задача D «Разрезание торта»

Мама испекла Мише на день рождения торт. Торт имеет форму выпуклого многоугольника с n вершинами. Вместе с гостями и родственниками у Миши на празднике оказалось k человек. В нужный момент Миша планирует разрезать торт на k частей. Каждый разрез должен представлять собой диагональ исходного многоугольника. Чтобы торт не развалился, разрезы не должны пересекаться нигде, кроме как в вершинах торта.

Как юного математика, Мишу заинтересовал вопрос — сколько существует способов разрезания торта на k частей указанным выше способом. Порядок выполнения разрезов не важен. Помогите Мише найти ответ на интересующий его вопрос.

Требуется написать программу, которая по заданным значениям чисел n и k определяет количество способов разрезания на k частей торта с n вершинами, как указано выше.

Формат входных данных

Входной файл содержит два целых числа n и k (1 <= k <= n <= 50, n >= 3).

Формат выходных данных

Выведите в выходной файл одно число — искомое количество способов разрезания торта.

Примеры входных и выходных файлов

Пояснение к примерам

Все способы разрезания торта с шестью вершинами на четыре части приведены на следующем рисунке.

Задача E «Перепутанные диски»

Вася — страстный любитель компьютерных игр. Его коллекция насчитывает десятки компакт-дисков с играми. Однако он очень неаккуратный мальчик. Коробки с дисками в полном беспорядке раскиданы по его столу, и поэтому найти что-либо на столе практически невозможно.

Когда Вася хочет поиграть в очередную игру, он действует следующим образом: берет произвольную коробку с диском со стола и вставляет диск из этой коробки в CD-привод своего компьютера. Если в CD-приводе уже есть какой-нибудь диск, то вместо того, чтобы найти коробку от этого диска и убрать его туда, Вася убирает диск в коробку, из которой он только что достал очередной диск.

Например, пусть у Васи есть три компакт-диска с играми — «Цивилизация», «Тетрис» и «Сапер». Пусть Вася сначала начал играть в «Цивилизацию», а затем решил поиграть в «Тетрис». Тогда после этого диск с «Цивилизацией» окажется в коробке от «Тетриса». Пусть затем он решил поиграть в «Сапера». Тогда диск от «Тетриса» окажется в коробке от «Сапера». Если после этого он снова решит поиграть в «Цивилизацию» (заметим, что для этого он достанет ее из коробки от «Тетриса»), то игра «Сапер» окажется в коробке от «Тетриса», а «Цивилизация» — в CD-приводе Васиного компьютера.

Предполагая, что исходно все диски с играми находятся в своих коробках, напишите программу, которая по заданной последовательности игр, в которые играл Вася, определит, в какой коробке окажется после этого каждый из дисков с играми.

Формат входных данных

Первая строка входного файла содержит число n — количество игр, в которые играл Вася (1 <= n <= 1000), при этом Вася мог играть в одну и ту же игру несколько раз. Следующие n строк содержат названия игр в том порядке, в котором играл Вася. Все названия состоят из латинских букв, цифр и пробелов, длина названия не превышает 50 символов.

Формат выходных данных

Выведите в выходной файл k строк, где k — количество различных игр, в которые играл Вася. Каждая строка должна иметь вид «<game> - <box>», где <game> — название игры, а <box> — название игры, в коробке от которой лежит игра <game>. Если соответствующая игра лежит в CD-приводе компьютера, вместо <box> выведите «*» (звездочку). Выводите игры в произвольном порядке

Задача F «Разнообразные строки»

Будем называть разнообразностью строки количество символов, которые встречаются в ней ровно один раз. Например, разнообразность строки «INFORMATICS» — 9, поскольку символы «A», «C», «F», «R», «M», «N», «O», «S» и «T» встречаются в ней ровно один раз.

Для заданной строки S найдите подстроку, которая имеет наибольшую разнообразность. Если таких подстрок несколько, то найдите ту, которая минимальна в лексикографическом порядке.

Строка A меньше строки B в лексикографическом порядке, если выполняется одно из условий:

1. A является началом B;
2. для некоторого числа i первые i символов строки A совпадают с первыми i символами строки B, а i +1-й символ в строке A идет в алфавите раньше i +1-го символа в строке B.

Например, строка «SOL» меньше в лексикографическом порядке строк «SOLVE», «START», «TIME».

Формат входных данных

Входной файл содержит строку, состоящую только из букв латинского алфавита. Длина строки не превышает 2000 символов.

Формат выходных данных

Выведите в выходной файл подстроку исходной строки, имеющую максимальную разнообразность среди всех ее подстрок. Если таких подстрок несколько, выведите минимальную в лексикографическом порядке.

Примеры входных и выходных файлов

Задача G «Домашние задания»

Петя очень не любит делать домашние задания. Поэтому он просит отличников из своего класса сделать их за него. За это он дает им шоколадные конфеты. Так как Петин папа работает на шоколадной фабрике, то у Пети всегда много конфет.

Но отличники — капризные ребята. В разные дни они просят разное количество конфет за выполнение домашнего задания. Про каждого отличника в классе Петя знает, сколько конфет придется ему дать в i-й день учебы, чтобы тот сделал за него домашнее задание. Кроме того, каждый день делать домашние задания за Петю не согласится ни один отличник, и поэтому, про каждого отличника Петя знает, какое максимальное количество домашних заданий тот согласится сделать за него подряд.

Требуется написать программу, которая по информации о количестве конфет, которое отличники просят за свои услуги, а также о максимальном количестве дней подряд, которое каждый отличник готов делать домашние задания за Петю, определяет, какое минимальное количество конфет требуется Пете, чтобы все домашние задания были за него сделаны.

Формат входных данных

Первая строка входного файла содержит два числа: n — количество учебных дней, в течение которого Петя хочет, чтобы за него отличники делали домашние задания;

m — количество отличников в классе у Пети (1 <= n <= 100, 2 <= m <= 100).

Вторая строка входного файла содержит m целых чисел a_i (1 <= i <= m), задающих для каждого отличника максимальное количество заданий подряд, которое он согласен выполнять за Петю (1 <= a_i <= n).

Следующие m строк содержат по n неотрицательных целых чисел, при этом j-е число i-й строки означает количество конфет, которое Пете придется отдать i-му отличнику, чтобы он сделал за Петю домашнее задание в j-й день. Все эти числа не превышают 10⁶. Числа в строках разделяются пробелами.

Формат выходных данных

На первой строке выходного файла выведите одно число — минимальное количество конфет, которое необходимо Пете. На второй строке выведите n целых чисел, каждое из которых определяет для каждого дня номер отличника, который должен решать домашнее задание за Петю в этот день.

Примеры входного и выходного файлов

Краткие комментарии к решению задач

Задача А. Палиндромы

Рассмотрим два случая. Если длина строки меньше удвоенной длины запрещенного образца, просто переберем все возможные строки (в этом случае длина строки не превышает 10, следовательно, количество таких строк не превышает 2¹⁰ = 1024). В противном случае используем динамическое программирование по профилю. Пусть длина запрещенного образца равна l. Подсчитаем для всех строк z длины l и всех длин k, l <= k <= n/2 значение a[k][z] — количество строк длины k, заканчивающихся на z и не содержащих ни запрещенного образца s, ни его разворота rev(s).

После этого в «центре» выполним «слияние». В случае четного n для всех профилей z, для которых конкатенация z и rev(z) не содержит образца, добавим к ответу a[n/2][z]. В случае нечетного n добавим к ответу a[(n – 1)/2][z] для всех z , для которых z + A + rev(z) не содержит s, и еще раз для тех z, для которых z + B + rev(z) не содержит s.

Выделяются следующие частичные решения:

1. переборное решение (оценивается в 30 баллов);
2. решение, которое забывает запрещать rev(s) (оценивается в 40 баллов);
3. решение, которое работает для ответов, не превышающих 2³¹–1 (оценивается в 40 баллов);
4. решение, которое неверно выполняет слияние в центре в случае четного n (оценивается до 60 баллов);
5. решение, которое неверно выполняет слияние в центре в случае нечетного n (оценивается до 60 баллов);
6. решение, которое не выполняет слияния в центре (оценивается до 40 баллов).

Задача B. Парикмахер

В оптимальном решении можно считать, что время обслуживания всех клиентов одинаково. Зафиксировав это время, можно проверить, раньше или позже чем требуется, выйдет из парикмахерской последний клиент. После этого делаем двоичный поиск по ответу — если время меньше, чем требуется, то ответ больше, если больше чем требуется, то ответ следует уменьшить.

Выделяются следующие частичные решения:

1. поиск только целочисленного решения (оценивается в 26 баллов);
2. поиск только решения с некоторым шагом (оценивается до 60 баллов).

Задача C. Вырубка деревьев

Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.

Выделяется следующее частичное решение — переборное решение (оценивается до 40 баллов).

Задача D. Разрезание торта

Пронумеруем вершины торта от 1 до n. Будем считать a[n][k] — количество разбиений n-угольника на k частей.

Посмотрим, в какой части лежит ребро (1-2). Существуют следующие варианты:

1. Из вершины 2 нет ребра. Тогда выполняется одно из двух:
   • Есть треугольник (1-2-3), количество таких разбиений a[n–1][k–1];
   • Это не так. Тогда можно слить 1-2 и 2-3 в одно ребро, количество таких разбиений a[n–1][k].
2. Из вершины 2 есть ребро. Тогда возьмем то из них, которое идет в вершину с максимальным номером (перебирая этот номер), пусть оно идет в вершину j. Переберем, сколько ребер с одной стороны от этого ребра, сколько с другой, пусть с одной из них i. Кроме того, поскольку j — вершины с максимальным номером, в которую идет ребро из 2, то ребро (2– j) должно лежать в одной части с (1–2), поэтому их можно слить в одно ребро. Итого, суммируем по j и i значения (a[j – 1][i])(a[n – j + 1][k – i]).

Выделяется одно частичное решение — переборное решение (оценивается до 40 баллов).

Задача E. Перепутанные диски

В данной задаче требуется произвести непосредственную симуляцию описанного процесса.

Выделяется одно частичное решение — неверный учет пробелов в начале или конце названия (оценивается в 80 баллов).

Задача F. Разнообразные строки

Решение за O(n²), где n — длина строки. Ищем оптимальную строку, начиная с каждой возможной позиции. При этом поддерживаем текущую разнообразность строки. Когда встречаем очередной символ, смотрим, если он ранее встречался ровно один раз, то уменьшаем разнообразность на один. Если он ранее не встречался, увеличиваем на один. В противном случае не меняем. Параллельно ведем сравнение текущей строки с оптимальным ответом в смысле лексикографического порядка.

Если в какой-то момент текущая разнообразность стала больше, чем у текущего оптимума, то обновляем значение. Если равна, то если текущая строка меньше лексикографически оптимума, то обновляем ответ. Если произошло обновление оптимума, то в дальнейшем обновление следует производить только в случае, если разнообразность строго выше оптимума.

Выделяются следующие частичные решения:

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

Задача G. Домашние задания

Динамическое программирование: обозначим как a[i][j][k] количество конфет, которое необходимо Пете для того, чтобы сделать первые i заданий, причем последние k сделаны отличником j. Для пересчета O(nm) значений, где k = 1, потребуется O(m) действий каждому (перебор предыдущего отличника), для остальных O(n²m) значений — по O(1) действий. Общая сложность алгоритма O(nm(n + m)).

Выделяется одно частичное решение — различные жадные решения (оценивается в 20–50 баллов).

Рекомендации по системе оценивания и тестированию решений участников

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

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

Наборы тестов должны охватывать все возможные случаи, допустимые условием задачи. В наборе должны присутствовать:

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

Следует заметить, что правильное, но не эффективное решение задачи должно набирать ориентировочно 30-60% баллов.

Для большинства задач в условии приведены рекомендуемые ограничения по времени тестирования для отдельного набора входных данных каждого теста. Однако следует учитывать, что данные ограничения годятся для проведения тестирования на компьютерах с процессором Pentium II 450MГц. Поэтому в каждом конкретном случае жюри рекомендуется подбирать время тестирования самостоятельно.

Центральная методическая комиссия рекомендует каждую задачу независимо от ее сложности оценивать из 100 баллов. С учетом этого, если на каждом туре предлагается три задачи, то максимальное количество баллов, которое могут набрать по итогам тура участники олимпиады, будет составлять 300 баллов, а итогам двух туров – 600 баллов.

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

Количество тестов для каждой задачи различно и находится в диапазоне от 20 до 50. Файл с тестом называется «XY» и находится в каталоге tests. Тесты для каждой задачи пронумерованы от 1 до N, где N — количество тестов к задаче. Файл с правильным ответом на соответствующий тест называется «XY.a». Здесь XY — двузначный номер теста, дополненный при необходимости ведущим нулем. Например, файл с седьмым тестом называется «07», а файл с пятнадцатым тестом — «15», файл с правильным ответом на седьмой тест называется «07.a», файл с правильным ответом на пятнадцатый тест — «15.a».

При оценке решений участников рекомендуется полагать стоимость всех тестов для каждой задачи одинаковой. Общее количество тестов и стоимость теста для каждой задачи приведены в следующей таблице.

Проверяющая программа находится в файле «check.dpr». Для ее компиляции следует использовать компилятор Borland Delphi. Она использует библиотеку testlib для проверяющих программ, которая прилагается в файле «testlib.pas». Для проверки ответа на тесте, следует запустить программу с тремя параметрами командной строки — входной файл, выходной файл и файл с правильным ответом.

Тестирование с использование проверяющей программы осуществляется следующим образом. Программа последовательно запускается на тестах. Если программа успешно завершается после запуска на тесте, то запускается программа проверки, которая проверяет результат работы программы на тесте. Если проверяющая программа сообщает, что результат правильный, то участнику начисляются баллы за пройденный тест. Количество баллов за пройденный тест в каждой задаче указано в комментариях к задачам. Если программа выдает неправильный ответ, программа завершается с ошибкой времени исполнения, превышается предел на время исполнения, либо объем используемой памяти, то баллы за тест не начисляются.

Результаты олимпиады