Google Code Jam 2008 – kolo 3

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

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

Google Code Jam pokračuje třetím kolem.

Velikost kapes

mapa procházky Zadání: Máme zadaný tvar pravoúhelníka (všechny souřadnice jsou celočíselné) a naším úkolem je zjistit velikost jeho „kapes“. Bod v kapse je definován tím, že jednak neleží uvnitř pravoúhelníka a jednak existuje hranice vlevo i vpravo nebo nahoře i dole. Naším úkolem je zjistit velikost těchto kapes. Řešení

Portál

mapa bludiště Zadání: Kdekoliv v bludišti a všude kolem něj jsou rozmístěny zdi (všechny souřadnice jsou celočíselné). Zadaná je naše pozice v tomto bludišti a pozice dortu, ke kterému se chceme dostat. Kromě běžných pohybů můžeme na zdech vytvářet portály dvou druhů – žlutý a modrý (když vytvoříme už existující portál, tak původní zmizí). Vstupem do žlutého portálu se objevíme v modrém a naopak. Naším úkolem je zjistit minimální počet pohybů, kterými se můžeme dostat k dortu. Za pohyb se považuje posun nahoru, dolů, doleva nebo doprava a vstup do portálu. Naopak vytvoření portálu je zdarma. Řešení

Bez podvádění

podvádějící student Zadání: Učebna je plná židlí, některé z nich jsou ale rozbité. Naším úkolem je posadit na tyto židle co nejvíc studentů tak, aby nemohli podvádět při písemce. Student totiž vidí doleva a doprava ve své a předchozí řadě. Řešení

Tahy koněm

možné tahy koněm Zadání: V levém horním rohu obrovské šachovnice stojí šachový kůň. Jeho cílem je dostat se do pravého dolního rohu. V každém tahu musí kůň postoupit k cíli (takže může skákat buď doprava a dolů nebo dolů a doprava). Na šachovnici jsou ale některá políčka rozbitá, takže na ně kůň nemůže stoupnout (může je ale přeskočit). Naším úkolem je spočítat počet možných cest, kterými se kůň k cíli může dostat, pokud jsou zadané rozměry šachovnice a pozice rozbitých políček. Protože výsledek může být obrovský, stačí vrátit zbytek po dělení číslem 10007. Řešení

Jakub Vrána, Výuka, 2.9.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.