Введение.
Олимпиады по информатике, как и олимпиады по математике, широко распространены и имеют достаточно долгую историю. Командный студенческий чемпионат мира по программированию ACM ICPC (
Association for Computing Machinery International Collegiate Programming Contest) проводится с 1977 года. Международная олимпиада школьников по информатике IOI (
International Olympiad in Informatics) проводится с 1989 года. Эти олимпиады позволяют выявлять способности как в математике, так и в программировании, а также умение работать под стрессом в сжатых временных рамках. Указанные соревнования студентов традиционно являются командными, а школьников - личными. В России более долгую историю имеют олимпиады школьников по информатике.
Популярность соревнований по информатике и программированию стремительно растет. Их спонсорами выступают такие крупные корпорации, как AT&T, Microsoft, IBM, Google.
Соревнования обычно проходят следующим образом. Команда состоит из 3х человек. Каждой команде выдается 1 компьютер, набор задач (обычно от 8 до 15) и 5 часов на то чтобы их решить. Решение задачи должно быть оформлено в виде программы на алгоритмическом языке, в стандарте ACM прописаны следующие языки: С, С++, Java, но в рамках правил региональных соревнований набор языков может быть расширен.
Все решения отправляются автоматической проверяющей системе, каждое неверное решение приносит команде 20 минут штрафного времени.
Победителем становится команда, решившая наибольшее количество задач, за наименьшее время.
Команды Самарского Государственного Университета регулярно принимают участие в различных соревнованиях по олимпиадному программированию, таких как: четвертьфинал и полуфинал чемпионата мира по олимпиадному программированию, чемпионат Урала, и многих других.
Также с 1999 года на базе Самарского Государственного университета проводится чемпионат города среди студентов по олимпиадному программированию. С 2011 года чемпионат получил статус Международного чемпионата Поволжья.
1Анализ предметной области.
Подготовка и проведение соревнования это очень важный и кропотливый процесс, в котором нужно постараться максимально исключить возможность ошибки, поскольку любой недочет в условии задачи, тестах или проверяющей системе может привести к тому что та или иная команда не получит свои заветные очки или потеряет время, пытаясь решить неправильно составленную задачу.
Подготовка к соревнованию начинается с того, что авторы придумывают пакет задач. Каждая задача состоит из легенды, условия и форматов входных и выходных данных.
На каждую задачу устанавливаются ограничения на максимальное время, за которое должна отработать программа, и на максимальную память, которую может занять программа.
Далее на каждую задачу составляется набор тестов, либо проверяющая программа - «Чекер» (от англ. Check - проверять). Один тест представляет собой набор из двух текстовых файлов – входного и выходного. Формат файлов должен строго следовать формату, описанному в задаче. Во входном файле описаны данные, которые должны быть переданы программе, которую пришлет команда на проверку. В выходном файле описаны данные, с которыми должны быть сравнены выходные данные программы команды.
Если у задачи есть несколько правильных вариантов выходных данных на один и тот же тест, то применяется программа проверки решения. В таком случае существует файл с входными данными. Получив выходные данные от программы команды, запускается программа «Чекер», которая проверяет, удовлетворяют ли выходные данные условию задачи.
По прохождению каждого теста, программа команды получает один из возможных вердиктов:
Accepted (Полное решение) - Данный вердикт означает, что программа успешно прошла тест.
Wrong Answer (Неправильный ответ) – Данный вердикт означает, что программа участника выдала неверный ответ на данном тесте.
Time limit Exceeded (Превышен лимит времени) – Данный вердикт означает, что программа не уложилась в отведенный её лимит времени
Memory limit Exceeded (Превышен лимит памяти) – Данный вердикт означает, что программа не уложилась в отведенный ей лимит памяти.
Idleness Limit Exceeded (Превышено время бездействия) – Данный вердикт означает, что программа «зависла» во время выполнения.
Runtime error (Ошибка времени выполнения) – Данный вердикт означает, что произошло исключение времени выполнения.
Compilation Error (Ошибка компиляции) – Данный вердикт означает, что программа не смогла скомпилироваться на сервере.
При вердикте «Accepted» тестирование продолжается на следующем тесте. Если все тесты были пройдены с этим вердиктом, то решение получает вердикт «Accepted», и задача считается решенной.
При любом другом вердикте тестирование прекращается, и команда получает вердикт с номером теста, на котором был получен данный вердикт, и штрафное очко.
Все задачи и тесты заносятся в проверяющую систему, выставляется время начала и окончания соревнования.
Во время соревнования у всех участников и зрителей есть возможность следить за ходом соревнования по монитору. Монитор – сводная турнирная таблица, на которой приведены результаты всех команд на текущий момент времени. Для внесения интриги в процесс прохождения соревнования, обычно за час до конца монитор «замораживают» и после этого на мониторе либо просто отображается положение команд на момент «заморозки», либо дополнительно отображают попытки команд сдать ту или иную задачу, без указания успешности или провала попытки.
Проектирование и построение такой системы является сложной задачей, поскольку существует много тонкостей, которые необходимо предусмотреть. Существует много систем созданных в разных городах и странах, разными людьми. Каждая система обладает своими преимуществами и недостатками, которые выражаются в настройке системы, простоте доступа к условиям задач, возможности проведения одновременно нескольких соревнований.
Система, использующаяся для проведения четвертьфиналов чемпионата мира по программированию в Саратове, имеет дружелюбный web-интерфейс, в ней прописаны все основные возможности, но в данной системе невозможно одновременное проведение нескольких соревнований.
Система, спроектированная и построенная в СпбГУ ИТМО - PCMS2, является java клиент-серверным приложением. В данной системе также учтены все основные возможности, но система не позволяет одновременное проведение нескольких соревнований, а также крайне сложна в настройке, поскольку для успешного запуска соревнований требуется создание сложных конфигурационных файлов и скриптов запуска.
Система, использующаяся в Самарском Государственном Университете, имеет также достаточно дружелюбный web-интерфейс. Система также поддерживает все основные функции, необходимые для проведения чемпионатов, в том числе и проведение нескольких соревнований одновременно. Однако данная система создает проблемы при отправке решений, в частности для участников пишущих решение на языке программирования Java существует ряд условий на расстановку операторных скобок основного класса и т.п.
Идеальной системы не существует, каждая спроектирована под определенных организаторов соревнований. Поэтому каждая система уникальна, и их крайне сложно сравнивать между собой.