И вот соревновательный тур настал: билеты с условиями задач розданы, часы включены. В течение тура участник может задавать жюри вопросы для устранения неясностей в условиях задач. Вопросы задают только в письменной форме (другие участники их слышать не должны!) и формулируют так, чтобы ответом было «да» или «нет». Нельзя, например, спросить, в каких пределах находится число 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;beginAssign(F, CIn); Reset(F);Close(F);end;procedure WriteData;var F: text;beginAssign(F, COut); Rewrite(F);Close(F);end;beginReadData;WriteData;end.Взяв за основу шаблон, и определив константу CTask для имен файлов, вы получите отчасти готовую программу.
Организаторы гарантируют правильность входных данных в своих тестах. Если в условии сказано, что число лежит в пределах от 1 до 10, то так оно и будет. Но это не значит, что вы введете его таким, – ошибка может затаиться в процедуре ввода. Она сведет на нет последующие правильные действия, и вы не получите нужный ответ. Так проверяйте ввод данных (отладчиком или выводом на экран). Разумеется, что для проверки решения вам придется выдумать свои тесты, поскольку тесты жюри участникам неизвестны.
И вот тестирование завершено, и результаты оглашены. Где мы с вами? Впереди на белом коне? Поздравляю! Искупайтесь в лучах славы, и, обсохнув на лаврах, начинайте готовиться к следующему этапу.
А если неудача? Каждый переживает ее по-своему. Кто-то даст волю чувствам и размажет слезы по щекам. Но вы не из тех, – я знаю. Поражение закаляет упорных. Внимательно прослушайте разбор задач, – его устраивают по окончании туров. Разберитесь в своих ошибках, решите задачи дома. А может, вам просто не хватило времени? – не беда, ведь и среди великих встречались тугодумы. Не опускайте рук, работайте, и обязательно добьетесь успехов. В конце концов, олимпиада – это всего лишь ступенька, которую можно… перепрыгнуть. Все ещё впереди!
Приложение АУстановка и настройка IDE Borland Pascal
Рассмотрим установку и настройку интегрированной среды разработки Borland Pascal. Она создавалась для операционной системы MS-DOS, а такие приложения, исполняемые под Windows, своенравны, и требуют особого подхода.
Далее мы рассмотрим:
• историю создания IDE Borland Pascal и её состав;
• установку IDE из официального дистрибутива;
• устранение ошибки в модуле CRT;
• русификацию справочной системы;
• организацию рабочей папки;
• создание и настройку ярлыка для запуска IDE;
• предварительную настройку IDE;
• русификацию консольного окна;
• школьный пакет Turbo Pascal School Pak.
Полагаю, что ваш компьютер оснащен одной из операционных систем семейства Windows. Разным системам свойственны небольшие отличия в настройке IDE, они будут отмечены мною по ходу изложения.
Седьмая версия IDE Borland Pascal – самая совершенная версия этого продукта. Её появление в начале 90-х годов совпало с расцветом операционной системы Windows 3.1 – первой коммерческой системы этого рода. Фирма Borland, шагая в ногу со временем, предусмотрела в своем товаре компилятор для разработки программ под Windows, ставший прообразом Delphi. В этом же пакете Borland предложила два компилятора для MS-DOS: один, более мощный, – для современных компьютеров, а другой – для компьютеров на слабеньких процессорах Intel 80x86. Прошли годы, и – странное дело! – компилятор под Windows 3.1 давно заб