8. až 15. augusta 2009 sa v Plovdive v Bulharsku konal 21. ročník Medzinárodnej olympiády v informatike. Zúčastnilo sa ho vyše 300 súťažiacich z 83 krajín.

Slovenskú výpravu tvorili súťažiaci vybraní na základe výsledkov celoštátneho kola Olympiády v informatike a týždenného výberového sústredenia:

 

• Tomáš Belan, Škola pre mimoriadne nadané deti a gymnázium Bratislava,

• Peter Csiba, Škola pre mimoriadne nadané deti a gymnázium Bratislava,

• Peter Fulla, SPŠ strojnícka Spišská Nová Ves,

• Martin Šrámek, Gymnázium Košice, Alejová 1.

Zľava: Peter Csiba, Tomáš Belan, Peter Fulla, Martin Šrámek

Výpravu ďalej tvorili ako vedúci Andrej Blaho a Vladimír Boža (ktorých úlohou bolo hlavne preložiť zadania z angličtiny do slovenčiny), ako člen medzinárodnej odbornej komisie Michal Forišek a ako hosť Viera Blahová.

Samotná súťaž pozostáva z dvoch súťažných dní. Každý deň súťažiaci riešia 4 úlohy, na ktoré majú 5 hodín času. Ako riešenie úlohy sa odovzdáva program, ktorý rieši zadaný problém. Po ukončení súťaže nasleduje hodnotenie programov, ktoré prebieha aicky. Program dostane vstupné dáta, ktoré má spracovať, a na základe zadania úlohy vypíše výsledok. Pokiaľ vypíše správny výsledok v dostatočne krátkom čase a nepoužije viac pamäte, ako je dovolené, tak získava istý počet bodov. Takýchto testov prebehne niekoľko a každý program môže získať nanajvýš 100 bodov. Tieto vstupné dáta súťažiaci počas súťaže vo väčšine prípadov nemajú k dispozícii.

Vo voľnom čase boli pre účastníkov naplánované rôzne ako aktivity ako jazda na motokárach, návšteva aquaparku, výlet na pláž a pod.

Súťaž končila udeľovaním medailí. Najlepších 26 súťažiacich dostalo zlatú medailu, ďalších 50 striebornú a 73 dostalo bronzovú medailu. Z našich obsadili Tomáš Belan 43. miesto, Peter Fulla 47. miesto, čo znamenalo zisk striebornej medaily, Peter Csiba obsadil 78. miesto a získal bronzovú medailu (strieborná medaila mu unikla len o 2 miesta).

Ukážka jednej zo súťažných úloh – Najímanie

Máme N uchádzačov o prácu. O každom vieme jeho minimálny požadovaný plat S a jeho kvalifikáciu Q (kvalifikácia je vyjadrená celým číslom). Vieme, že platy našich zamestnancov musia byť v pomere ich kvalifikácií (t. j. ak má jeden zamestnanec plat 2 a kvalifikáciu 10, tak ak má druhý kvalifikáciu 20, tak musí mať plat 4). Náš celkový platový strop (koľko najviac môžeme zamestnancom dokopy zaplatiť) je W. Chceme najať čo najviac zamestnancov. Pokiaľ je viac možností, tak treba najať tých, ktorých celkový plat bude čo najnižší. Napíšte program, ktorý pre zadané hodnoty (N, W, minimálne platy a kvalifikácie uchádzačov) vypočíta, ktorých ľudí treba najať. Poznámka: N môže nadobudnúť hodnotu až 500 000.

Náčrt možných riešení

Všimnime si, že keď jednému zamestnancovi určíme plat, tak plat ostatných je jednoznačne určený. Ale jednoduché riešenie typu „Určím plat jednému zamestnancovi (jeho najnižší možný), potom určím platy ostatných a vyberiem tých najlacnejších možných,“ nedostane 100 bodov (konkrétne v tejto úlohe by to bolo iba 50 bodov). Dôvodom je to, že na vyskúšanie jedného zamestnanca je potrebné určiť plat všetkých ostatných. Takto potrebujete prejsť všetkých, čo vyžaduje približne N^2 operácií (čo je pri hodnote N 500 000 priveľa). Rýchlejšie riešenie vyžaduje utriedenie zamestnancov podľa pomeru požadovaná cena:kvalita a ďalšiu prácu s týmto utriedeným zoznamom.

Užitočné odkazy

www.ioi2009.org – stránka tohtoročnej Medzinárodnej olympiády v informatike

www.ioinformatics.org – stránka Medzinárodnej olympiády v informatike

www.ksp.sk/oi – stránka slovenskej Olympiády v informatike

Vladimír Boža

Prehliadka mesta