ACM/ICPC (или просто ICPC) — крупнейшая студенческая командная олимпиада по программированию. Это мероприятие приравнивается к чемпионату мира по программированию. Данная статья открывает новую одноименную категорию на сайте, где мы будем разбирать интересные олимпиадные задачи.

Начну с небольшого экскурса в историю и правила проведения чемпионата. Четвертьфинальные и полуфинальные этапы чемпионата проходят независимо в своих регионах, победители которых проходят в следующий этап. Лучшие команды из каждого региона по итогам полуфинала собираются вместе в одном из городов мира и выясняют отношения в финале. Чемпионат командный, в каждой команде три участника. В распоряжении команды один ПК, некоторое количество времени (обычно 5 часов) и ряд поставленных задач (как правило, 5-10 задач). Каждая задача имеет условие, формат входных и выходных данных, ограничение по времени и по памяти. Решением задачи является программа, написанная на одном из доступных правилами языков программирования (обычно пишут на C). Программы-решения проверяются в автоматическом режиме. Система автоматической проверки выполняет несколько тестов, подавая проверяемой программе входные данные и анализируя выходные согласно условию задачи. Если программа на выходе дает неправильный ответ, превышает лимит допустимой оперативной памяти, выполняется дольше положенного времени (не компилируется, выпадает в runtime error, ну и так далее), то тест не пройден. Задача считается решенной, если программа удачно проходит все тесты, предложенные системой. Вариантов “почти решенная”, “наполовину решенная”, как вы понимаете, нет. При подсчете баллов учитывается количество решенных задач, время и количество попыток, затраченных на их решение.

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

Страсти в финалах, конечно, кипят нешуточные. Финал 2004/2005 гг., Шанхай:

На старте исключительно мощно пошла вперед команда МГУ, возглавляемая Петром Митричевым, являющимся, пожалуй, самым сильным российским студентом в этом виде программистских состязаний за всю историю участия наших университетов в чемпионатах мира. Особенно сильно Петр выступает в тех случаях (появляющихся с частотой, равной примерно одной трети), когда он “проводит нокаутирующий удар” и ему удается сдавать все задачи с первой попытки. В финале реализовался именно этот неудачный для остальных команд вариант, Петр шел вперед “как танк”, и за первые три с небольшим часа его команда решила семь задач — шестую и седьмую задачу команда МГУ сдала на 158 и 186 минутах. Чемпион мира прошлого года команда СПбГУ ИТМО была готова к такому развитию событий, ей удалось, как говорят велосипедисты, “сесть команде МГУ на колесо” и в самом начале четвертого часа борьбы на 191 и 196 минутах тоже сдать шестую и седьмую задачи. Руководители команды СПбГУ ИТМО надеялись, что при решении трех оставшихся очень сложных задач петербуржцы смогут переиграть команду МГУ. Наконец, спустя десять минут после команды СПбГУ ИТМО, на 205 и 211 минутах шестую и седьмую задачи решила и команда Ватерлоо, выйдя на третье место. Команда Шанхайского университета на 203 минуте, чуть раньше Ватерлоо, сдала лишь шестую задачу и в результате в “замороженной” таблице результатов в начале пятого часа борьбы оказалась на пятом месте, проигрывая и команде университета Вроцлава, которая тоже решила шесть задач, но имела лучшее штрафное время.

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

Четвертьфинал в этом подрегионе проходит в Дальневосточном государственном университете (ДВГУ). Организация на должном уровне, атмосфера замечательная. Эти поездки были, несомненно, одними из самых ярких моментов в студенческую пору. В первый день соревнований по графику регистрация команд, торжественное открытие, а вечером пробный тур, на котором предлагается решить три задачи и, главное, освоиться с системой автоматической проверки решений. Система у них своя, разработана местными умами. Кстати, находится в свободном доступе по адресу http://imcs.dvgu.ru/cats/, можно заходить и практиковаться, есть архив задач, результаты прошедших чемпионатов.

Во второй день непосредственно соревнования. Каждой команде выделяется один ПК, дают ручки, бумагу. С собой ничего приносить нельзя :). В середине действа подают чай с бутербродами. В системе Cats есть возможность задать вопрос жюри по условию задачи, но формулировка вопроса должна подразумевать ответ “да/нет”. Ах да, сами условия на английском языке. Есть также страница статистики в реальном времени, которая к последнему часу соревнований “замораживается” для сохранения интриги и “размораживается” уже на торжественном закрытии.

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

На этом, я думаю, стоит закончить с вводной информацией. Тематика раздела, я думаю, понятна и интересна многим посетителям Винкода. До встречи!