Ma A portugáliai Porto városában rendezik meg az ICPC 2019 nemzetközi programozási verseny döntőjét, amelyen az ITMO Egyetem képviselői, valamint Oroszország, Kína, India, USA és más országok egyetemeinek csapatai vesznek részt. Mondjuk el részletesebben.
icpcnews /flickr/ CC BY / Fotók az ICPC-2016 phuketi döntőjéről
Mi az ICPC
ICPC egy nemzetközi programozási verseny diákok körében. Több mint 40 éve rendezik – az első döntő voltam még 1977-ben. A kiválasztás több szakaszban történik. Az egyetemek régiók szerint vannak felosztva (Európa, Ázsia, Afrika, Amerika stb.). Mindegyikük ad otthont a köztes szakaszoknak, különösen az észak-eurázsiai elődöntőknek egyetemünkön zajlott. A döntőben a regionális szakaszok győztesei vesznek részt.
Az ICPC-n három fős csapatokat kérnek fel, hogy egy számítógépen (nem internetkapcsolattal) oldjanak meg számos problémát. Így a programozási készségek mellett a csapatmunka készségeit is tesztelik.
A verseny során csapatok egy számítógépet kap három személyre. Az Ubuntu 18.04 fut rajta, és előre telepítve van a vi/vim, a gvim, az emacs, a gedit, a geany és a kate. Programokat írhat Python, Kotlin, Java vagy C++ nyelven.
Amikor egy csapat megold egy problémát, továbbítja azt a tesztelő szervernek, amely kiértékeli a kódot. A résztvevők nem tudják, milyen teszteket végez a gép. Ha mindegyik sikeres, a csapat bónuszpontokat kap. Ellenkező esetben hiba keletkezik, és a tanulók elküldik a kód javítására.
Az ICPC szabályai szerint az a csapat nyer, amelyik a legtöbb problémát megoldja. Ha több ilyen csapat van, akkor a győztest a legkisebb büntetési idő határozza meg. A résztvevők minden megoldott probléma után büntetőpercet kapnak. A percek száma megegyezik a verseny kezdetétől a feladat tesztszerver általi elfogadásáig eltelt idővel. Ha a csapat megtalálja a megoldást, további húsz perc büntetést kap minden hibás passzkísérletért.
icpcnews /flickr/ CC BY / Fotók az ICPC-2016 phuketi döntőjéről
Minta problémák
A bajnokság céljai csapatkoordinációt és koncentrációt igényelnek. Ezenkívül tesztelik az egyes matematikai algoritmusok ismeretét. Íme egy példa egy feladatra, amelyet az ICPC 2018 résztvevőinek ajánlottak fel:
A tipográfiában van egy „folyó” kifejezés - ez a szavak közötti szóközök sorozata, amely több szövegsorból áll. Egy bizonyos folyószakértő (valóban) könyvet akar kiadni. Azt akarja, hogy a leghosszabb tipográfiai folyók „képződjenek” az oldalon, ha monospace-betűkkel nyomtat. A résztvevőknek meg kellett határozniuk azon mezők szélességét, amelyeknél ez a feltétel teljesül.
A bemeneten a program egy n egész számot kapott (2 ≤ n ≤ 2), amely meghatározza a szövegben szereplő szavak számát. Ezután beírtuk a szöveget: az egy sorban lévő szavakat egy szóköz választja el, és nem állhat több mint 500 karakterből.
A kimeneten a programnak meg kellett mutatnia azon mezők szélességét, amelyeknél a leghosszabb „folyó” keletkezik, és ennek a folyónak a hosszát.