Šodien Portugāles pilsētā Porto risināsies starptautiskā programmēšanas konkursa ICPC 2019 fināls, kurā piedalīsies ITMO universitātes pārstāvji un citas komandas no Krievijas, Ķīnas, Indijas, ASV un citu valstu augstskolām. Pastāstīsim sīkāk.
icpcnews /flickr/ CC BY / Fotogrāfijas no ICPC-2016 fināla Puketā
Kas ir ICPC
ICPC ir starptautisks programmēšanas konkurss studentu vidū. Tās tiek rīkotas vairāk nekā 40 gadus – pirmais fināls pagājis vēl 1977. gadā. Atlase tiek veikta vairākos posmos. Universitātes ir sadalītas pa reģioniem (Eiropa, Āzija, Āfrika, Amerika utt.). Katrā no tām notiek starpposmi, jo īpaši Ziemeļeirāzijas pusfināls notika mūsu universitātē. Novadu posmu uzvarētāji piedalās finālā.
ICPC komandām trīs dalībnieku sastāvā tiek lūgts atrisināt vairākas problēmas, izmantojot vienu datoru (nav savienots ar internetu). Tādējādi papildus programmēšanas prasmēm tiek pārbaudītas arī komandas darba prasmes.
Sacensību laikā komandas saņems vienu datoru trim personām. Tajā darbojas Ubuntu 18.04, un tajā ir iepriekš instalētas programmas vi/vim, gvim, emacs, gedit, geany un Kate. Varat rakstīt programmas Python, Kotlin, Java vai C++ valodās.
Kad komanda atrisina problēmu, tā pārsūta to uz testēšanas serveri, kas novērtē kodu. Dalībnieki nezina, kādus testus mašīna veic. Ja visi ir veiksmīgi, komanda saņem bonusa punktus. Pretējā gadījumā tiek ģenerēta kļūda un studenti tiek nosūtīti labot kodu.
Saskaņā ar ICPC noteikumiem uzvar komanda, kas atrisina visvairāk problēmu. Ja šādas komandas ir vairākas, tad uzvarētājs tiek noteikts pēc mazākā soda laika. Par katru atrisināto problēmu dalībnieki saņem soda minūtes. Minūšu skaits ir vienāds ar laiku no sacensību sākuma līdz uzdevuma pieņemšanai testa serverī. Ja komanda atrod risinājumu, tad par katru nepareizu piespēles mēģinājumu tā saņem vēl divdesmit minūšu sodu.
icpcnews /flickr/ CC BY / Fotogrāfijas no ICPC-2016 fināla Puketā
Problēmu paraugi
Čempionāta mērķi prasa komandas koordināciju un koncentrēšanos. Turklāt viņi pārbauda zināšanas par atsevišķiem matemātiskajiem algoritmiem. Šeit ir piemērs uzdevumam, kas tika piedāvāts ICPC 2018 dalībniekiem:
Tipogrāfijā ir termins “upe” - tā ir atstarpju secība starp vārdiem, kas veidojas no vairākām teksta rindām. Kāds upes eksperts (pa īstam) vēlas izdot grāmatu. Viņš vēlas, lai lapā “veidotos” garākās tipogrāfiskās upes, drukājot ar vienpusīgu fontu. Dalībniekiem bija jānosaka lauku platums, kurā šis nosacījums tiks izpildīts.
Programma ievadē saņēma veselu skaitli n (2 ≤ n ≤ 2), kas nosaka vārdu skaitu tekstā. Tālāk tika ievadīts teksts: vārdi vienā rindā tika atdalīti ar vienu atstarpi, un tie nedrīkstēja sastāvēt no vairāk par 500 rakstzīmēm.
Programmai izejā bija jāparāda to lauku platums, pie kuriem veidojas garākā “upe”, un šīs upes garums.