Google Code Jam 2008 – semifinále

Školení, která pořádám

Článek vyšel na serveru Programujte.com.

Google Code Jam se blíží do finále, kterému předcházelo asijské, americké a evropské semifinále. Přiznám se, že některé úlohy už byly nad mé síly, v tomto článku proto uvádím pouze výběr úloh z Asie a Evropy.

Co jsou ptáci?

VýškaHmotnostZvíře
10001000pták
20001000pták
10002000pták
15002010nepták

Zadání: Snažíme se přijít na to, která zvířata v lese jsou ptáci a která ne. Víme, že pokud má zvíře výšku a hmotnost v určitém intervalu, tak je to určitě pták, tyto dva intervaly nicméně bohužel neznáme. Vědci nám dali alespoň seznam zvířat s danou výškou a hmotností a u každého uvedli, zda je to pták nebo ne. Na základě tohoto seznamu následně u ostatních zvířat můžeme zjistit, zda jde s jistotou o ptáka nebo to určitě pták není nebo zda to na základě zadaných dat nelze určit. Řešení

Barvení plotu

BarvaZačátekKonec
modrá16000
červená400010000
oranžová30008000

Zadání: Máme plot s 10000 laťkami a chceme ho nabarvit. K dispozici máme několik nabídek na nabarvení jednotlivých částí plotu různými barvami. Naším úkolem je zjistit, jestli lze celý plot nabarvit nejvíce 3 barvami a pokud ano, tak vrátit minimální počet nabídek, které za tím účelem musíme přijmout. Řešení

Milionář

Zadání: Byli jsme pozváni do soutěže s daným počtem kol, kde v každém kole můžeme vsadit libovolný obnos, který máme k dispozici. S předem známou pravděpodobností tento obnos buď zdvojnásobíme nebo o něj přijdeme. Naším cílem je vsázet tak, abychom s co největší pravděpodobností vyhráli jeden milion. Hru začínáme s určitým obnosem a naším úkolem je určit pravděpodobnost, že vyhrajeme kýžený milion, pokud budeme sázet optimálně. Řešení

Autobusové zastávky

Zadání: Na Marsu je N autobusových zastávek v řadě za sebou, vzájemně od sebe vzdálených 1 km. K dispozici máme K autobusů a naším úkolem je zjistit počet možných jízdních řádů, pokud jsou zadané následující podmínky

Takových jízdních řádů samozřejmě může existovat obrovské množství, proto nám stačí vrátit jen zbytek po dělení číslem 30031. Řešení

Jakub Vrána, Výuka, 28.12.2008, diskuse: 0 (nové: 0)

Diskuse je zrušena z důvodu spamu.

avatar © 2005-2024 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.