Matematická olympiáda – kategorie P

ústředního kola 48. ročníku

Pavel Töpfer, MFF UK Praha

Letošní celostátní kolo 48. ročníku MO kategorie P (programování) se konalo ve dnech 14.-17.4.1999 v Novém Městě na Moravě. Zúčastnilo se ho 29 z třiceti pozvaných nejúspěšnějších řešitelů oblastních kol MO-P z celé republiky. O organizaci celé akce se pečlivě starali pracovníci gymnázia Vincence Makovského v Novém Městě na Moravě, odbornou stránku soutěže zajišťovali členové center MO kategorie P z Matematicko-fyzikální fakulty Univerzity Karlovy v Praze, z Matematicko-fyzikální fakulty Univerzity Komenského v Bratislavě a z Fakulty informatiky Masarykovy univerzity v Brně. Ti společně připravili soutěžní příklady, testovací data pro praktické úlohy, vyhodnocovací programové vybavení a také na místě celou soutěž zabezpečovali a opravovali odevzdaná řešení úloh. Všechny organizátory akce potěšil i velmi vstřícný postoj řady oslovených firem, které se jako sponzoři soutěže podílely zejména na zajištění odměn pro úspěšné řešitele. Z více než dvaceti sponzorů jmenujme alespoň několik nejznámějších firem - Microsoft, Inprise (Borland), Hewlett-Packard, IDG Publishing.

Celostátní kolo MO kategorie P se skládá ze dvou soutěžních dnů, z nichž první je teoretický a druhý praktický. Soutěžící tak mohou předvést své znalosti a schopnosti skutečně ze všech stránek. V prvním soutěžním dnu řešili účastníci písemně tři teoretické úlohy. Všechny tři soutěžní úlohy navazovaly na obdobné úlohy zadané již v domácím a oblastním kole soutěže. První z nich se tématicky týkala kódování textů pomocí mřížky, z hlediska algoritmického šlo však spíše o grafovou úlohu (základem řešení bylo stanovení počtu komponent souvislosti vhodného grafu). Druhá zadaná úloha spočívala v hledání výherní strategie jedné konkrétní varianty hry typu NIM, tzn. hry, v níž dva hráči podle stanovených pravidel střídavě odebírají zápalky z hromádek. Konečně poslední teoretická soutěžní úloha bývá tradičně věnována práci v nějakém netradičním výpočetním prostředí, s nímž jsou studenti seznámeni prostřednictvím studijního textu již v domácím a v oblastním kole soutěže. Letos se jednalo o Markovovy algoritmy. Studenti měli za úkol vyřešit ve formalismu Markovových algoritmů dvě úlohy - výpočet dvojkového logaritmu kladného celého čísla zadaného v unární soustavě a testování dělitelnosti třemi celého čísla zadaného ve dvojkové soustavě.

Druhý soutěžní den byl věnován praktickým úlohám. Každý řešitel měl ke své práci přidělen osobní počítač se základním programovým vybavením (překladače Pascalu a C/C++). Dvě praktické soutěžní úlohy měl pak na počítači vyřešit během čtyř hodin. První praktický příklad se tématicky týkal kombinování zvýhodněných cenových nabídek v obchodním domě pro dosažení minimální ceny požadovaného nákupu, z hlediska algoritmického to byla úloha na dynamické programování, přičemž bylo možné napsat i snadnější, ale o něco méně efektivní řešení založené na vhodně ořezaném prohledávání do hloubky. Druhá praktická úloha čerpala z problematiky kryptoanalýzy, tzn. hledání použitého šifrovacího klíče, známe-li zašifrovaný text, slovník přípustných slov a použitou metodu šifrování. Na rozdíl od teoretických úloh ve druhém soutěžním dnu opravovatelé vůbec neprohlížejí napsaný zdrojový text programu, ale pouze testují funkčnost vytvořeného programu pomocí sady předem připravených testovacích dat. Body jsou pak přidělovány podle počtu úspěšných testů. Součástí každého testu je i časový limit, v němž musí program dát výsledky. Tím je zajištěno ohodnocení odevzdaných programů i z hlediska časové efektivity. Přesně stejným způsobem jsou hodnocena řešení úloh i na mezinárodních olympiádách v informatice.

Každá z pěti úloh byla hodnocena maximálně 10 body. Celkem šestnáct soutěžících, kteří získali alespoň 13 bodů, bylo vyhlášeno úspěšnými řešiteli. Prvních šest z nich s alespoň 22 body se stalo vítězi celostátního kola 48. ročníku matematické olympiády - kategorie P.

Na základě výsledků celostátního kola MO-P byla vybrána reprezentační družstva České Republiky pro mezinárodní programátorské olympiády studentů středních škol. Celosvětová mezinárodní olympiáda v informatice IOI'99 se bude letos konat v první polovině října v Turecku, středoevropská olympiáda v informatice CEOI'99 určená pro mladší úspěšné řešitele se uskuteční v září v Brně.