🥇«Сражение в прямом эфире»: финал ICPC в Порту

Сегодня в португальском городе Порту пройдет финал международных соревнований по программированию ICPC 2019. В нем примут участие представители Университета ИТМО и другие команды из вузов России, Китая, Индии, США и других стран. Расскажем подробнее.

icpcnews / Flickr / CC BY / Фото с финала ICPC-2016 в Пхукете

Что такое ICPC

ICPC — это международные соревнования по программированию среди студентов. Они проводятся более 40 лет — первый финал прошел в далеком 1977 году. Отбор проводится в несколько этапов. Вузы разбивают по регионам (Европа, Азия, Африка, Америка и др). В каждом из них устраивают промежуточные этапы, в частности, полуфинал Северной Евразии проходил в нашем университете. Победители региональных этапов принимают участие в финале.

На ICPC командам из трех участников с помощью одного компьютера (не подключенного к интернету) предлагается решить ряд задач. Таким образом, помимо навыков программирования проверяются и навыки командной работы.

Команды Университета ИТМО завоевывали главный приз ICPC семь раз. Это абсолютный рекорд, который держится уже долгие годы. В битве за кубок ICPC 2019 схлестнутся 135 коллективов со всей планеты. Университет ИТМО в этом году представляют Илья Подуременных, Станислав Наумов и Роман Коробков.

Как будет проходить финал

На время соревнования команды получат один компьютер на троих. Он работает под управлением Ubuntu 18.04 и имеет предустановленные редакторы vi/vim, gvim, emacs, gedit, geany и kate. Писать программы можно на Python, Kotlin, Java или C++.

Когда команда решает задачу, она пересылает её тестирующему серверу, который оценивает код. Участники не знают, какие именно тесты проводит машина. Если все они проходят успешно, команда получает призовые очки. В противном случае генерируется ошибка, и студенты отправляются корректировать код.

По правилам ICPC побеждает команда, решившая больше всех задач. Если таких команд несколько, то победитель определяется по наименьшему штрафному времени. Участники получают штрафные минуты за каждую решенную задачу. Количество минут равно времени от начала соревнования до принятия задачи тестовым сервером. Если команда нашла решение, то она получает еще двадцать минут штрафа за каждую неправильную попытку её сдать.

«Сражение в прямом эфире»: финал ICPC в Порту
icpcnews / Flickr / CC BY / Фото с финала ICPC-2016 в Пхукете

Примеры задач

Задачи чемпионата требуют от команд слаженности действий и концентрации. Дополнительно они проверяют знания отдельных математических алгоритмов. Вот пример задания, которое предлагалась участникам ICPC 2018:

В типографии существует термин «река» — это последовательность пробелов между словами, которая образуется из нескольких строчек текста. Некий эксперт по рекам (настоящим) желает выпустить книгу. Он хочет, чтобы при печати моноширинным шрифтом на странице «образовывались» самые длинные типографские реки. Участникам нужно было определить ширину полей, при котором это условие будет выполняться.

На входе программа получала целое число n (2 ≤ n ≤ 2 500), определяющее количество слов в тексте. Далее, вводился текст: слова на одной строке разделялись одним пробелом и не могли состоять более чем из 80 символов.

На выходе программа должны была показать ширину полей, при которой образуется самая длинная «река», и длину этой реки.

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