Организация туров

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

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

И вот соревновательный тур настал: билеты с условиями задач розданы, часы включены. В течение тура участник может задавать жюри вопросы для устранения неясностей в условиях задач. Вопросы задают только в письменной форме (другие участники их слышать не должны!) и формулируют так, чтобы ответом было «да» или «нет». Нельзя, например, спросить, в каких пределах находится число N, но можно выяснить, является ли это число положительным («да» или «нет»?).

По окончании тура, участники покидают рабочие места, и начинается официальное тестирование их решений. Решение задачи – это исходный файл на выбранном языке (обычно на Паскале или Си). Тесты запускают в присутствии участника с использованием упомянутой тестирующей системы. Успешное решение должно компилироваться и выдавать правильные решения на предлагаемые тесты. Если тест не проходит, соответствующие ему баллы не начисляются. Жюри не рассматривает исходный текст как таковой, его интересуют лишь правильность прохождения тестов. Участник вправе опротестовать результат тестирования, если, по его мнению, на это есть основания (например, ошибка в тестовых данных). Протест подается в жюри в письменной форме. Жюри рассматривает все протесты и принимает своё решение. По окончании тестирования и рассмотрения протестов, жюри подводит официальные итоги, объявляя победителей и призеров олимпиады.

Олимпиадные задачи

Как выглядит олимпиадная задача? – пример найдете в приложении М. В чем особенности таких задач?

Прежде всего, отметим способ ввода и вывода данных. То и другое выполняется только через текстовые файлы, которым присваивают заранее оговоренные имена. Так, если для файла с решением оговорено имя «ABC.PAS», то входной файл будет называться «ABC.IN» а выходной – «ABC.OUT». На эти расширения имен рассчитаны упомянутые тестирующие системы.

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

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

Таковы особенности олимпиад по информатике, теперь обсудим подготовку к ним.

Подготовка к олимпиаде

Предметные олимпиады – это ступень на лестнице профессионального роста. Советы программисту-ремесленнику отчасти годятся и «спортсмену». И все же в олимпиадном программировании есть свои особенности.

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

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

Табл. 13 – Некоторые ресурсы Сети по олимпиадному программированию

Ресурс

Ссылка

Алгоритмы

http://algolist.manual.ru

Алгоритмы

http://bestalgorithm.ru

Олимпиады по программированию

http://www.olympiads.ru

Олимпиады по информатике(редактор – Андрей Станкевич)

http://neerc.ifmo.ru/school

Разбор олимпиадных задач(редактор – Михаил Густокашин)

http://g6prog.narod.ru

Олимпиады по информатике(сайт мытищинской школы программистов)

http://www.informatics.ru

Уральские олимпиады по программированию

http://contest.ur.ru

Спортивное программирование(соревнования «онлайн» с дистанционным тестированием)

http://acm.timus.ru

Командные олимпиады

http://de.ifmo.ru/cyber-net

Олимпиадные хитрости

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

Явитесь на олимпиаду без опоздания. Не тревожьтесь, ведь коленки дрожат не только у вас. Волнение – это нормальная реакция на опасность, оно мобилизует организм, но все хорошо в меру.

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

А если все решить невмоготу? Тогда примените разрешенную правилами хитрость: выдайте хотя бы одно или два частных решения. Что это такое? Это решение, удовлетворяющее одному из тестов. Предположим, что по условию задачи вы должны вычислить факториал числа. Но вы напрочь забыли о факториале все, кроме того, что факториалы для нуля и единицы равны единице. Тогда выдавайте единицу как решение для всех входных данных. Составители тестов наверняка проверят эти точки, и тогда ваша программа пройдет, по крайней мере, пару тестов.

Олимпиада быстротечна, и время надо беречь. А потому не пишите комментариев, не измышляйте слишком длинных имен. Но основными правилами оформления программ не пренебрегайте (логическими отступами, например), – они избавят вас от путаницы в собственном творении.

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

const CTask = 'Name';

      CIn = CTask+'.in';

      COut = CTask+'.out';

procedure ReadData;

var F: text;

begin

Assign(F, CIn); Reset(F);

Close(F);

end;

procedure WriteData;

var F: text;

begin

Assign(F, COut); Rewrite(F);

Close(F);

end;

begin

ReadData;

WriteData;

end.

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

Организаторы гарантируют правильность входных данных в своих тестах. Если в условии сказано, что число лежит в пределах от 1 до 10, то так оно и будет. Но это не значит, что вы введете его таким, – ошибка может затаиться в процедуре ввода. Она сведет на нет последующие правильные действия, и вы не получите нужный ответ. Так проверяйте ввод данных (отладчиком или выводом на экран). Разумеется, что для проверки решения вам придется выдумать свои тесты, поскольку тесты жюри участникам неизвестны.