Google Code Jam 2008 – finále

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

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

Poslední sada úloh letošního Google Code Jam byla zadaná ve finále. Některé úlohy jsou již obtížnější, ale jiné se stále soustředí spíše na rychlé vymyšlení jednoduchého algoritmu. Na stránkách soutěže se také objevil oficiální klíč k řešení všech dosud zveřejněných soutěžních úloh, kde lze najít podrobnější vysvětlení řešení problémů.

Džus

Zadání: Na párty jsme pozvali daný počet lidí. Každý z těchto lidí má rád džus namíchaný z přísad A, B a C. Problém je, že každému vyhovuje jiné množství těchto přísad. Naším úkolem je stanovit takové množství těchto přísad, abychom uspokojili co nejvíc lidí. U každého člověka máme zadáno, kolik které přísady minimálně chce, aby mu džus chutnal (maximální součet přísad je stanoven jako číslo 10000). Řešení

Pingpongové balónky

schéma Zadání: Ve veliké místnosti zadaných rozměrů jsou na všech políčcích totožné pasti na myši. Každá past je nabita dvěma balónky, které se při aktivaci vystřelí na relativně zadané políčko a aktivují past, která na cílovém políčku leží. Naším úkolem je zjistit, kolik pastí se celkem aktivuje, pokud jako první aktivujeme past na určeném políčku. Řešení

Minové pole

schéma Zadání: Na minovém poli jsou rozmístěny miny. Nevíme přesně, kde miny jsou, ale u každého políčka víme, kolik je na něm a v jeho okolí min (celkem na devíti políčcích). Naším úkolem je zjistit, kolik min může být maximálně v prostřední řadě políček (počet řad je vždy lichý). Řešení

Stavitelé mostů

schéma Zadání: Máme zadanou mapu, kde je na každém čtverečku les, voda nebo pole. Mezi čtverečky je voda. Naším cílem je propojit tyto ostrovy pomocí mostů, které z daného políčka můžou vést vždy jen na horní, dolní, levý nebo pravý ostrov. Mosty se staví ze dřeva nalezeného v lese a postavit most trvá člověku tolik hodin, jaká je vzdálenost od nejbližšího lesa k propojovanému ostrovu. Na mapě na začátku nejsou žádné mosty a začínáme v levém horním rohu, kde je vždy les. Naším úkolem je propojit všechny ostrovy za minimální počet člověko-hodin a vrátit tento počet. Řešení

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

Vložit komentář

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2018 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.