Команда МГУ на чемпионате мира по программированию ACM ICPC в Пекине: Григорий Резников, Михаил Ипатов, Владислав Макеев, Елена Андреева. Фото: Randy Piland / icpcnews.com
На прошлой неделе в Пекине закончился 42-й ежегодный студенческий чемпионат мира по спортивному программированию под эгидой и по правилам ACM (Association for Computing Machinery – это старейшая, созданная в 1947 году, ассоциация ученых, исследователей и практиков в сфере ИТ). Чемпионами мира стали ребята из МГУ, они единственные за отведенное время успешно решили девять задач из 11 предложенных жюри. По восемь задач решили студенты МФТИ, а также университетов Пекина и Токио; по семь – еще девять команд, в том числе две российских (СПбИТМО и УрФУ), две китайских, две американских (включая и легендарный MIT). Всего в соревнованиях в Пекине принимали участие команды из 140 университетов со всех континентов. Из последних 19 чемпионатов (с 2000 года) российские команды выиграли 13, а СПбИТМО – семикратные чемпионы мира – официально является самым титулованным в мире. Прошлогодний чемпионат (он проходил в США, в Рэпид-Сити) выиграли тоже они, но в этом году остались лишь девятыми.
Что это за соревнования такие, в чем их смысл и престижность и почему успехами российских спортивных программистов стоит гордиться?
Правила игры
С 1977 года в правилах чемпионатов удивительным образом изменилось не так уж и много. Три студента (только один из них может быть старшекурсником, двое других – не старше бакалавриата; кроме того, участвовать в финале чемпионата мира каждый конкретный человек может не более двух раз), пять часов, один компьютер, несколько (раньше 6–8, в последние годы – 10–12) алгоритмических задач со строго поставленными условиями. Решением является программа на любом из нескольких допустимых языков программирования, проверка решений носит автоматизированный характер: жюри запускает программу, написанную участниками, на определенном наборе заранее заготовленных тестов, одинаковых для всех участников, и засчитывает решение только в том случае, если программа выдаст правильный ответ на всех тестах (а вот как именно она это сделает – никого не волнует; у задачи вполне может быть несколько совершенно разных правильных решений). Хотя бы одна ошибка – решение не засчитывается; команда может исправить его и послать на проверку снова, но каждая неудачная попытка обойдется в 20 штрафных минут, почти как в биатлоне. Таблица результатов доступна всем участникам и зрителям в режиме реального времени (что придает состязанию азарта и зрелищности), кто больше решил задач – тот и победил, а при равенстве выше в таблице оказывается команда, нахватавшая меньше штрафа.
