Вы - -й посетитель этой странички 

Олимпиады по информатике.

Лекции читает Е.В. Андреева

Продолжение. Начало см. в № 38/2001

Лекция 2. Правила проведения олимпиады

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

1. Олимпиада проводится в два тура. Продолжительность каждого тура 5 часов. На каждом из туров для решения задач участнику предоставляется персональный компьютер типа IBM PC со следующим программным обеспечением: Turbo Pascal 7.0, Borland C++ 3.1.

Из первого пункта правил становится ясно, что, во-первых, оба тура олимпиады так называемые практические. Во-вторых, для решения задач предлагается использовать лишь один из двух языков программирования. Такое положение полностью соответствует международной практике, хотя на российских олимпиадах соблюдается не всегда строго. Basic исключен из числа официальных языков программирования олимпиады, так как желание программировать только на нем высказывает очень не большое число участников олимпиад высокого уровня, при профессиональной разработке программ он практически не используется (в данном случае Visual Basic мы не рассматриваем), кроме того, решение задач с использованием этого языка иногда затруднено по сравнению с Паскалем и Cи. На наш взгляд, заранее объявляя об ограничениях на использование программного обеспечения, жюрии оргкомитет олимпиады способствуют практике изучения тех языков программированияв российских школах, которые позволят ребятам добиваться нетолько успехов в различных соревнованиях, но и некоторымиз них стать высокими профессионалами в области информатики и программирования. Мы считаем, что именно язык программирования   Паскаль, как никакой другой, позволяет за короткий срок отлаживать довольно сложные программы, что особенно важно в условиях практического тура любой олимпиады, но и не менее значимо при изучении информатики в школе. Использование языка Cи (C++) на олимпиаде стоит приветствовать лишь тогда, когда участник владеет им почти в совершенстве, практически не допуская ошибок при записи решения задачи на Cи, часть из которых невозможно обнаружить на этапе компиляции программы. Кроме того, при программировании на Cи могут возникнуть сложности с настройкой компилятора, а на олимпиаде даже минута, потраченная не на собственно решение задач, может сказаться на результатах  участника. Хотя справедливости ради стоит сказать, что на международной олимпиаде процент участников,использующих язык программирования Cи (C++), достаточно высок, причем многие из них выступают более чем успешно, что опять же свидетельствует о высокой квалификации таких школьников, а размер кода программ на Cи (не следует путать с размером исполняемого файла)часто меньше кода на языке Паскаль. В заключение заметим, что предоставляемое на олимиадах программное обеспечение (операционная система, тип и версия компиляторов, среда программирования) со временем естественно может изменяться, как это и произошло на последней международной олимпиаде по информатике в Финляндии (см. № 37/2001 ).

2. На каждом из туров участникам предлагается решить несколько задач.Вопросы по условиям задач можно задавать только в течение первого часа тура. Вопросы следует задавать только в письменном виде и формулировать их так, чтобы на них можно было ответить “да” или “нет”. Такая практика сложилась исторически и применяется на международных олимпиадах. Строгое соблюдение данного пункта правил иногда вызывает у ряда участников некоторые сложности. Так, школьникам зачастую тяжело именно в начале тура пытаться понять нюансы в формулировках сразу всех задач. Кроме того,часто вопросы по условию возникают лишь тогда, когда участник приступил к решению той или иной задачи. Поэтому немаловажным является умение с первого раза внимательно прочитать условие любой задачи, выделяя неясные для себя места в тексте. Умение грамотно сформулировать вопрос, допускающий один из двух вариантов ответа, также зачастую у школьников отсутствует. Заметим, что при ответе на большинство задаваемых вопросов члены жюри используют фразу “без комментариев”. Это означает, что либо ответ на вопрос все же содержится в формулировке задачи и его следует искать самостоятельно, либо вопрос фактически касается уже способов ее решения и жюри не комментирует различные соображения участников по этому поводу.

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

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

5. В решениях категорически запрещается:

— использовать расширенную память;

— использовать ассемблерные вставки;

— создавать файлы и каталоги во время работы программы;

— читать данные откудалибо, кроме как из входного файла, и записывать их куда-либо, кроме выходного файла;

— читать и записывать вектора прерываний;

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

6. Для решения разных задач могут использоваться разные языки программирования. По каждой задачена проверку должны быть сданы два файла — исходный текст решения и соответствующий ему исполняемый файл (файл с расширением EXE). Если программа написана на языке Cи или C++, то она должна быть скомпилирована в модели памяти large. В программене должны использоваться специально созданные внешние модули. После окончания тура и сдачи работы вносить какие-либо изменения в текст решения не допускается. Файлы с решениями могут быть скопированы на личную дискету участника дежурным преподавателем после окончания тура. Из данного правила следует, что проверка решения задачи производится в основном путем тестирования, созданного участником во время тура исполняемого файла. Однако жюри оставляет за собой право перекомпилировать решения участников, в исключительных случаях это делается по просьбе школьников с разрешения жюри во время тестирования. Текст же решения с целью оценки используемых в нем алгоритмов жюри не анализируется, проверка осуществляется путем запуска программы на различных тестах. Так было далеко не всегда, однако в последнее десятилетие это стало нормой проведения всех практических туров олимпиад по информатике и программированию различного уровня ² . Достаточно строгим является правило, согласно которому текст программы после окончания тура исправлениям не подлежит, даже если ошибки в программе незначительны (иногда требуется исправить всего один символ) или задача практически решена, но нарушен формат выходных данных. В противном случае довольно сложно определить, какие же именно исправления можно считать допустимыми. В последние годы такое правило неуклонно соблюдается и практически не вызывает возражений со стороны как участников, так и их руководителей. Ограничение же на модель памяти при использовании языка программирования Cи является довольно искусственным и введено лишь потому, что данная модель памяти наиболее близка к модели памяти языка Турбо Паскаль, что опять же ставит участников в равные условия при решении задач. На международных олимпиадах такое ограничение отсутствует. Копирование решения участником на собственную дискету в ряде случаев позволяет ему вместе с руководителем найти ошибки и разобраться в особенностях работы программы до окончания олимпиады. Это существенно снижает количество подаваемых в жюри апелляций.

7. Проверка решений осуществляется после окончания тура и проводится в присутствии участника (а пожеланию и руководителя). По результатам тестирования заполняется лист проверки с результатами по каждому тесту. На одном и том же тесте программа всегда должна выдавать одинаковые результаты. Если с результатами проверки участник не согласен, то он вносит свои замечания в лист проверки.

Проверка решения в присутствии участника говорит об открытости работы жюри на этапе тестирования. Такой подход снимает множество вопросов относительно полученных за решение той или иной задачи баллов. Поэтому его применение можно рекомендовать для олимпиад любого уровня, начиная со школьной. На последней, а так же районной олимпиаде участники зачастую получают за решение той или иной задачи нулевые баллы потому, что их решение просто не удалось запустить или файл с решением оказался ненайденным. А ошибки в названиях файлов с решениями, входными и выходными данными, например, на школьной олимпиаде не должны оказаться для ребят фатальными. Но определить, что причины неработоспособности программы именно в этом, зачастую можно только лишь с помощью ее автора. Требование же стабильности работы программы имеет следующий смысл. Различные результаты работы программы на одноми том же тесте в большинстве случаев объясняются либо ошибками в ее работе (например, если значения каких-либо переменных в программе явным образом не проинициализированы, то работа исполняемого файла зависит от того, чем было заполнено содержимое используемой программы при запуске оперативной памяти), либо использованием   датчика случайных (а на самом деле псевдослучайных) чисел. Причем правилами олимпиады использование случайных чисел как таковых не возбраняется. Просто программа должна применять датчик так, чтобы на одних и тех же входных данных генерировалась последовательность из одних и тех же случайных чисел. Например, в языке Турбо Паскаль этого легко добиться, если не использовать в программе процедуру randomize. Кроме того, генератор псевдослучайных чисел можно запрограммировать и самостоятельно. При нарушении указанного правила жюри оставляет за собой право запустить программу несколько раз и засчитать худший из показанных ею результатов.

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

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

Порядок решения олимпиадных задач

1. В самом начале тура полезно набить приведенную ниже универсальную заготовку для решения олимпиадной задачи (она представляет собой работающую программу!), особое внимание следует обратить на директивы компилятора, приведенные в образце. С помощью команды <ctrl> + <o>< o> текущие директивы компилятора можно записать в начале текста программы и исправить те из них, которые не соответствуют приведенным.

{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T+,V+,X+,Y+}

var

    i,j,k:longint;

procedure readdata;

    assign(input,'');

    reset(input);

end;

procedure outdata;

begin

    assign(output,'');

    rewrite(output);

    close(output)

end;

procedure initial;

Далее можно скопировать эту заготовку столько раз, сколько задач предложено на туре, и сразу назвать каждый файл так, как это требуется по условиям олимпиады. В результате вам не придется при переходе от решения одной задачи к другой начинать работу с нуля (а попытка править текст с решением одной задачи для ускорения набора текста другой ведет только к порождению ошибок, на исправление которых будет потрачено гораздо больше времени). В разделе OPTIONS| enviroment|preferences среды программирования Турбо Паскаль полезно установить параметр Auto save [X]Editor Files (автосохранение редактируемых файлов). Это гарантирует автоматическое сохранение текста программы при каждом ее запуске. Таким образом, если, например, программа зависнет и среду программирования придется запускать заново, то результат последнего редактирования будет сохранен (к сожалению, во время тура школьники зачастую забывают самостоятельно время от времени запоминать сделанные ими изменения в тексте программ).

3. Если вы приступили к решению конкретной задачи и основная структура данных для нее вам ясна,то можно описать основные глобальные переменные и набить процедуру readdata ввода данных, чтобыона считывала все параметры задачи так, как это указано в условии. Если не оговорено иное, то делать формальную проверку считанных данных, то есть проверять соответствие введенных значений переменных условию задачи не нужно ( ! ). Объясняется это тем, что,по правилам проведения большинства олимпиад последних лет, считается, что все входные данные при тестировании будут корректны. Кроме того, заметим,что при считывании из файла чисел обычно следует использовать только процедуру read (а не readln),для случаев же считывания символов и строк (тип string) это не так. Если количество чисел во входном файле неизвестно, то нужно использовать функцию seekeof  вместо eof для проверки условия окончания считывания чисел. Для файлов, содержащих произвольный текст, это опять же уже не так.

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

4. В процедуре initial следует обнулить или присвоить соответствующие начальные значения всем ( ! ) глобальным переменным, за исключением тех, которые будут использоваться в качестве параметров циклов. Затем запрограммировать вывод результата в процедуре outdata так, как это требуется в условии задачи. Это поможет дальнейшей отладке программы, и в дальнейшем не потребуется “простой” вывод переделывать в “правильный”. Таким образом, к этому моменту у вас уже должна быть “работающая” программа. Она по крайней мере должна компилироваться, считывать данные и выводить результат, пусть и нулевой, но в нужном формате.

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

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

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

2) Определить, относится ли данная задача к знакомому вам классу, или решение придется искать“с нуля”.

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

4) Попробуйте сформулировать условие существования решения, пусть только необходимое или только достаточное.

5) Продумайте и выпишите ( ! ) достаточную систему тестов.

6. Запрограммируйте решение задачи в виде вызовов процедур и функций, которые пока следует описать ввиде “заглушек” (мнимого или пустого действия или имитации настоящего действия, которое должна выполнять ваша программа). Таким образом, вы сможете отладить логику вашей программы, которая опять же должна оставаться “работающей”.

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

8. Если вы не придумали эффективного решения задачи, то запрограммируйте его попростому: например, с помощью полного перебора или простой эвристики(приближенного решения, в ряде случаев дающего точный ответ). Если и это сложно, то упростите себе задачу, то есть отбросьте условия, которые вам мешают, или добейтесь, чтобы программа проходила на самых простых, например, вырожденных тестах (большинство параметров равны 0 или 1). Аналогично следует поступить с задачами, на решение которых у вас не хватило времени.

9. Прежде чем окончательно cоздавать EXE-файл, замените ряд директив компилятора на следующие:

D- , I- , L- , R- , Q-

и отрегулируйте размер необходимого вашей программе стека.

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

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

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

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

3. Создание программы по плану, описанному в пунктах 6 и 7 данных, обычно называют “методом программирования сверху вниз”.