Dnes V portugalském městě Porto se bude konat finále mezinárodní programátorské soutěže ICPC 2019. Zúčastní se ho zástupci ITMO University a další týmy z univerzit v Rusku, Číně, Indii, USA a dalších zemích. Pojďme si to říct podrobněji.
icpcnews /flickr/ CC BY / Fotografie z finále ICPC-2016 v Phuketu
Co je ICPC
ICPC je mezinárodní programátorská soutěž mezi studenty. Konají se již přes 40 let – první finále prošel zpět v roce 1977. Výběr se provádí v několika fázích. Univerzity jsou rozděleny podle regionů (Evropa, Asie, Afrika, Amerika atd.). Každý z nich hostí mezistupně, zejména severoeurasijské semifinále se konala na naší univerzitě. Vítězové krajských stupňů se účastní finále.
Na ICPC jsou týmy tří účastníků požádány, aby vyřešily řadu problémů pomocí jednoho počítače (bez připojení k internetu). Kromě programátorských dovedností se tedy testují i dovednosti týmové práce.
Během soutěže týmy obdrží jeden počítač pro tři osoby. Běží na něm Ubuntu 18.04 a má předinstalované vi/vim, gvim, emacs, gedit, geany a kate. Programy můžete psát v Pythonu, Kotlinu, Javě nebo C++.
Když tým vyřeší problém, předá jej testovacímu serveru, který kód vyhodnotí. Účastníci nevědí, jaké testy stroj provádí. Pokud jsou všechny úspěšné, tým získává bonusové body. V opačném případě je vygenerována chyba a studenti jsou odesláni k opravě kódu.
Podle pravidel ICPC vyhrává tým, který vyřeší nejvíce problémů. Pokud je takových týmů několik, pak vítěze určí nejmenší penaltový čas. Za každý vyřešený problém dostávají účastníci trestné minuty. Počet minut se rovná času od zahájení soutěže do přijetí úkolu testovacím serverem. Pokud tým najde řešení, dostane dalších dvacet minut trestu za každý nesprávný pokus o jeho přihrávku.
icpcnews /flickr/ CC BY / Fotografie z finále ICPC-2016 v Phuketu
Příklady úkolů
Cíle šampionátu vyžadují týmovou koordinaci a koncentraci. Navíc si ověřují znalosti jednotlivých matematických algoritmů. Zde je příklad úkolu, který byl nabídnut účastníkům ICPC 2018:
V typografii existuje termín „řeka“ - jedná se o posloupnost mezer mezi slovy, která se skládá z několika řádků textu. Jistý znalec řeky (skutečně) chce vydat knihu. Chce, aby se na stránce při tisku v jednoprostorovém písmu „vytvořily“ nejdelší typografické řeky. Účastníci měli určit šířku polí, na kterých bude tato podmínka splněna.
Na vstupu program obdržel celé číslo n (2 ≤ n ≤ 2 500), které určuje počet slov v textu. Dále byl zadán text: slova na jednom řádku byla oddělena jednou mezerou a nesměla obsahovat více než 80 znaků.
Na výstupu měl program ukázat šířku polí, na kterých se tvoří nejdelší „řeka“, a délku této řeky.