Сьогодні у португальському місті Порту пройде фінал міжнародних змагань із програмування ICPC 2019. У ньому візьмуть участь представники Університету ІТМО та інші команди з вузів Росії, Китаю, Індії, США та інших країн. Розкажемо докладніше.
icpcnews /Flickr/ CC BY / Фото з фіналу ICPC-2016 у Пхукеті
Що таке ICPC
ICPC - це міжнародні змагання з програмування серед студентів. Вони проводяться понад 40 років – перший фінал пройшов далекого 1977 року. Відбір проводиться у кілька етапів. ВНЗ розбивають по регіонах (Європа, Азія, Африка, Америка та ін). У кожному з них влаштовують проміжні етапи, зокрема півфінал Північної Євразії. проходив у нашому університеті. Переможці регіональних етапів беруть участь у фіналі.
На ICPC командам із трьох учасників за допомогою одного комп'ютера (не підключеного до інтернету) пропонується вирішити низку завдань. Таким чином, крім навичок програмування, перевіряються і навички командної роботи.
На час змагання команди отримають один комп'ютер на трьох. Він працює під керуванням Ubuntu 18.04 і має встановлені редактори vi/vim, gvim, emacs, gedit, geany та kate. Писати програми можна на Python, Kotlin, Java чи C++.
Коли команда вирішує завдання, вона пересилає її серверу, що тестує, який оцінює код. Учасники не знають, які тести проводить машина. Якщо вони проходять успішно, команда отримує призові очки. А якщо ні, то генерується помилка, і студенти відправляються коригувати код.
За правилами ICPC перемагає команда, яка вирішила найбільше завдань. Якщо таких команд кілька, то переможець визначається за найменшим штрафним часом. Учасники одержують штрафні хвилини за кожне вирішене завдання. Кількість хвилин дорівнює часу від початку змагання до прийняття завдання тестовим сервером. Якщо команда знайшла рішення, вона отримує ще двадцять хвилин штрафу за кожну неправильну спробу її здати.
icpcnews /Flickr/ CC BY / Фото з фіналу ICPC-2016 у Пхукеті
Приклади завдань
Завдання чемпіонату вимагають від команд злагодженості дій та концентрації. Додатково вони перевіряють знання окремих математичних алгоритмів. Ось приклад завдання, яке пропонувалося учасникам ICPC 2018:
У друкарні існує термін «річка» — це послідовність прогалин між словами, що утворюється з кількох рядків тексту. Якийсь експерт з річок (справжнім) бажає випустити книгу. Він хоче, щоб під час друку моноширинним шрифтом на сторінці «утворювалися» найдовші друкарські річки. Учасникам потрібно було визначити ширину полів, за яких ця умова виконуватиметься.
На вході програма отримувала ціле число n (2 ≤ n ≤ 2), що визначає кількість слів у тексті. Далі вводився текст: слова на одному рядку розділялися одним пробілом і не могли складатися з більш ніж 500 символів.
На виході програма мала показати ширину полів, коли він утворюється найдовша «річка», і довжину цієї річки.