Matematická olympiáda – kategorie P

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

Pavel Töpfer, MFF UK Praha

Ve dnech 27.-30.4.1994 se v Jevíčku konalo celostátní kolo 43. ročníku MO - kategorie P (programování). Již tradičně navázalo na celostátní kolo kategorie A, které se uskutečnilo na stejném místě a ve stejném týdnu. Soutěž v kategorii P letos probíhala již podeváté.

Novinkou letošních celostátních kol MO byla skutečnost, že se poprvé oddělilo pořádání soutěže v České republice a ve Slovenské republice. Výborná spolupráce s našimi slovenskými kolegy však nadále trvá, v obou zemích probíhala všechna kola matematické olympiády ve stejných termínech a se stejnými soutěžními úlohami. Podobnou spolupráci plánujeme i na příští léta. Rozdělení soutěže se promítlo do počtu účastníků a trochu i do kvality soutěže, konkurence v menší zemi je pochopitelně menší. Do celostátního kola MO kategorie P bylo pozváno 30 nejlepších řešitelů z oblastních kol, z nich 28 přijelo na celou soutěž a jeden opožděně pouze na druhý soutěžní den.

V Jevíčku se konalo velmi zdařilé a dobře připravené celostátní kolo matematické olympiády již v loňském školním roce. Také letos místní organizátoři naprosto bezchybně zajistili celou soutěž a všem účastníkům navíc vytvořili velmi milé a přátelské prostředí k práci. O úspěch celé akce se nejvíce zasloužil ředitel gymnázia v Jevíčku dr. Dag Hrubý, poděkování patří také všem pracovnicím Domova mládeže, které se podílely na přípravě ubytování, stravování i na organizačním zabezpečení soutěže.

Odborným garantem 43. ročníku MO kategorie P bylo pražské centrum MO-P působící na matematicko-fyzikální fakultě Univerzity Karlovy v Praze. Pracovníci tohoto centra připravili soutěžní úlohy všech tří kol včetně komentářů a vzorových řešení, provedli celostátní koordinaci výsledků oblastních kol soutěže a výběr postupujících do celostátního kola. Společně s kolegy z brněnského centra soutěže také na místě v Jevíčku opravili odevzdaná řešení a sestavili konečné výsledky.

Pro úlohy letošního ročníku MO-P bylo typické, že dosti úzce na sebe navazovaly úlohy jednotlivých kol. První úloha v každém kole byla algoritmická úloha na zpracování zadané posloupnosti čísel. Tato úloha byla silně zaměřena na efektivitu vytvořeného programu. Druhou úlohou byl pokaždé některý ze standardních grafových algoritmů - v domácím kole nalezení minimální kostry v ohodnoceném grafu, v oblastním kole test, zda je daný graf bipartitní, v celostátním kole určení všech mostů v grafu. Ve třetí úloze soutěžící nevytvářeli program, ale měli za úkol nalézt a analyzovat jistý algoritmus. Jednalo se o různé hry se zápalkami typu NIM a hledání vítězných strategií v těchto hrách. Konečně pro čtvrtou úlohu byl vytvořen zvláštní model konečného automatu s několika vstupními a jednou výstupní páskou, který sloužil k provádění jednoduchých aritmetických výpočtů s čísly zadanými na vstupních páskách. Jednotlivá soutěžní kola se lišila zvoleným způsobem zobrazení čísel. V domácím kole se pracovalo pouze s kladnými čísly zapsanými ve dvojkové soustavě, v oblastním kole se používal doplňkový kód pro zobrazení všech celých čísel, v celostátním kole jsme pak zavedli poněkud neobvyklou číselnou soustavu o základu (-2).

Při opravování odevzdaných řešení se ukázalo, že úlohy byly co do obtížnosti velmi dobře navrženy. Každá úloha byla v soutěži hodnocena maximálně 10 body. Celkový bodový průměr dosažený při hodnocení každé z úloh se příliš nelišil od optimálního středního počtu 5 bodů, ve většině úloh se objevila jak řešení za 0, tak i za 10 bodů. Z 29 účastníků celostátního kola 43. ročníku MO kategorie P bylo 14 vyhlášeno úspěšnými řešiteli soutěže. Byli to všichni, kdo získali alespoň 20 bodů, tj. polovinu ze 40 možných bodů. Z nich 5 nejlepších bylo označeno za vítěze. Výsledky celostátního kola ukazuje závěrečná tabulka.

Na základě výsledků dosažených v celostátním kole a s přihlédnutím k hodnocení zejména prvních dvou algoritmických úloh v oblastním kole byla hned na místě v Jevíčku vybrána reprezentační družstva pro dvě mezinárodní programátorské soutěže středoškoláků. Vrcholnou soutěží bude 6. mezinárodní olympiáda v informatice, která se bude konat ve Švédsku ve dnech 3.-10.7.1994. Právo účasti na olympiádě získali Martin Mareš ze 3.r. gymnázia U libeňského zámku v Praze 8, Daniel Škarda ze 4.r. gymnázia Zborovská v Praze 5, Petr Novák ze 4.r. gymnázia na tř. kpt. Jaroše v Brně a Robert Špalek ze 2.r. stejného gymnázia. Letos poprvé se navíc uskuteční ještě jedna mezinárodní soutěž trochu menšího rozsahu. V Rumunsku se bude konat ve dnech 26.-31.5.1994 středoevropská soutěž středoškoláků v informatice, jakási přípravná mezinárodní olympiáda v malém pro soutěžící z regionu střední Evropy. Na této soutěži nás budou reprezentovat Jiří Hájek ze 3.r. gymnázia Zborovská v Praze 5, Petr Kaňovský ze 3.r. gymnázia na tř. kpt. Jaroše v Brně, Jan Kratochvíl z 1.r. gymnázia U libeňského zámku v Praze 8 a David Stanovský ze 3.r. gymnázia Dašická v Pardubicích.