Šiandien Tarptautinio programavimo konkurso ICPC 2019 finalas vyks Portugalijos mieste Porte. Jame dalyvaus ITMO universiteto atstovai bei kitos komandos iš Rusijos, Kinijos, Indijos, JAV ir kitų šalių universitetų. Papasakokime išsamiau.
icpcnews /flickr/ CC BY / Nuotraukos iš ICPC-2016 finalo Pukete
Kas yra ICPC
TIPK yra tarptautinis programavimo konkursas tarp studentų. Jie rengiami daugiau nei 40 metų – pirmasis finalas praėjo dar 1977 m. Atranka atliekama keliais etapais. Universitetai skirstomi pagal regionus (Europa, Azija, Afrika, Amerika ir kt.). Kiekviename iš jų vyksta tarpiniai etapai, ypač Šiaurės Eurazijos pusfinaliai vyko mūsų universitete. Finaluose dalyvauja regioninių etapų nugalėtojai.
ICPC trijų dalyvių komandų prašoma išspręsti daugybę problemų naudojant vieną kompiuterį (neprijungtą prie interneto). Taigi, be programavimo įgūdžių, tikrinami ir komandinio darbo įgūdžiai.
Varžybų metu komandos gaus vieną kompiuterį trims asmenims. Jame veikia Ubuntu 18.04 ir yra iš anksto įdiegtos vi/vim, gvim, emacs, gedit, geany ir kate. Galite rašyti programas Python, Kotlin, Java arba C++ kalbomis.
Kai komanda išsprendžia problemą, ji persiunčia ją į testavimo serverį, kuris įvertina kodą. Dalyviai nežino, kokius bandymus atlieka mašina. Jei visi jie yra sėkmingi, komanda gauna papildomų taškų. Priešingu atveju sugeneruojama klaida ir studentai siunčiami taisyti kodo.
Pagal ICPC taisykles laimi ta komanda, kuri išsprendžia daugiausiai problemų. Jei tokių komandų yra kelios, tai nugalėtojas nustatomas pagal mažiausią baudos laiką. Už kiekvieną išspręstą problemą dalyviai gauna baudos minutes. Minučių skaičius yra lygus laikui nuo varžybų pradžios iki užduoties priėmimo bandomajame serveryje. Jei komanda randa sprendimą, ji gauna dar dvidešimt minučių baudos už kiekvieną neteisingą bandymą jį perduoti.
icpcnews /flickr/ CC BY / Nuotraukos iš ICPC-2016 finalo Pukete
Примеры задач
Čempionato tikslai reikalauja komandos koordinavimo ir susikaupimo. Be to, jie tikrina žinias apie atskirus matematinius algoritmus. Štai užduoties, kuri buvo pasiūlyta ICPC 2018 dalyviams, pavyzdys:
Tipografijoje yra terminas „upė“ - tai tarpų tarp žodžių seka, sudaryta iš kelių teksto eilučių. Tam tikras upės žinovas (tikrai) nori išleisti knygą. Jis nori, kad spausdinant vienarūšiu šriftu puslapyje „susiformuotų“ ilgiausios tipografinės upės. Dalyviai turėjo nustatyti laukų plotį, kuriame ši sąlyga bus įvykdyta.
Įvedime programa gavo sveikąjį skaičių n (2 ≤ n ≤ 2 500), kuris lemia žodžių skaičių tekste. Tada buvo įvestas tekstas: žodžiai vienoje eilutėje buvo atskirti vienu tarpu ir negali būti sudaryti iš daugiau nei 80 simbolių.
Išėjime programa turėjo parodyti laukų, kuriuose susidaro ilgiausia „upė“, plotį ir šios upės ilgį.