Täna Portugali linnas Portos peetakse rahvusvahelise programmeerimisvõistluse ICPC 2019 finaal, millest võtavad osa ITMO ülikooli esindajad ja teised meeskonnad Venemaa, Hiina, India, USA ja teiste riikide ülikoolidest. Räägime teile üksikasjalikumalt.
icpcnews /Flickr/ CC BY / Fotod ICPC-2016 finaalist Phuketis
Mis on ICPC
ICPC on rahvusvaheline programmeerimisvõistlus õpilaste seas. Neid on peetud üle 40 aasta – esimene finaal möödus tagasi aastal 1977. Valik viiakse läbi mitmes etapis. Ülikoolid on jagatud piirkondade kaupa (Euroopa, Aasia, Aafrika, Ameerika jne). Igaüks neist võõrustab vaheetappe, eelkõige Põhja-Euraasia poolfinaale toimus meie ülikoolis. Finaalis osalevad piirkondlike etappide võitjad.
ICPC-l palutakse kolmeliikmelistel meeskondadel lahendada mitmeid probleeme, kasutades ühte arvutit (pole Interneti-ühendust). Seega pannakse lisaks programmeerimisoskustele proovile ka meeskonnatöö oskused.
Võistluse ajal võistkonnad saab ühe arvuti kolmele inimesele. Sellel töötab Ubuntu 18.04 ja sellele on eelinstallitud vi/vim, gvim, emacs, gedit, geany ja kate. Saate kirjutada programme Pythonis, Kotlinis, Javas või C++ keeles.
Kui meeskond probleemi lahendab, saadab ta selle edasi testimisserverisse, mis hindab koodi. Osalejad ei tea, milliseid teste masin teeb. Kui kõik need õnnestuvad, saab võistkond boonuspunkte. Vastasel juhul genereeritakse viga ja õpilased saadetakse koodi parandama.
ICPC reeglite kohaselt võidab meeskond, kes lahendab kõige rohkem probleeme. Kui selliseid võistkondi on mitu, selgub võitja väikseima karistusaja järgi. Osalejad saavad iga lahendatud probleemi eest trahviminuteid. Minutite arv võrdub ajaga, mis kulub võistluse algusest kuni ülesande vastuvõtmiseni testserveri poolt. Kui meeskond leiab lahenduse, saab ta iga vale söötmiskatse eest veel paarkümmend minutit trahvi.
icpcnews /Flickr/ CC BY / Fotod ICPC-2016 finaalist Phuketis
Näidisprobleemid
Meistrivõistluste eesmärgid nõuavad meeskonna koordineerimist ja keskendumist. Lisaks testivad nad teadmisi üksikute matemaatiliste algoritmide kohta. Siin on näide ülesandest, mida pakuti ICPC 2018 osalejatele:
Tüpograafias on termin "jõgi" - see on sõnadevaheline tühikute jada, mis moodustatakse mitmest tekstireast. Teatud jõeekspert (päris) tahab raamatut välja anda. Ta soovib, et ühekohalise kirjatüübiga printimisel tekiksid lehel pikimad tüpograafilised jõed. Osalejad pidid määrama väljade laiuse, mille puhul see tingimus oleks täidetud.
Programm sai sisendis täisarvu n (2 ≤ n ≤ 2), mis määrab sõnade arvu tekstis. Järgmisena sisestati tekst: ühe rea sõnad eraldati ühe tühikuga ja need ei võinud koosneda rohkem kui 500 tähemärgist.
Väljundis pidi programm näitama nende väljade laiust, kuhu moodustub pikim “jõgi”, ja selle jõe pikkust.