Google Code Jam 2008 – kolo 2

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

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

Google Code Jam pokračuje druhým kolem.

Binární strom

ukázka stromu s označením uzlů, které lze změnit Zadání: Máme binární strom, který má v listech hodnotu 0 nebo 1. V uzlech je buď operátor AND nebo OR s tím, že u některých uzlů je možné operátor prohodit. Naším úkolem je zjistit minimální možný počet změn, který do kořene dostane zadanou hodnotu. Řešení

Obsah trojúhelníku

Zadání: Naším úkolem je zjistit, jestli existuje trojúhelník s celočíselnými souřadnicemi z daného rozsahu, jehož obsah je zadaný. Řešení

Hvězdné války

xyzp
0001
1201
3401
2101

Zadání: Ve vesmíru je rozmístěno několik lodí, z nichž každá má přijímač daného výkonu (u každé lodi může být jiný). Mezi tyto lodě je potřeba umístit vysílač, ze kterého zachytí signál všechny lodě. Naším úkolem je zjistit minimální možný výkon tohoto vysílače, umístit ho můžeme na libovolné místo. Potřebný výkon vysílače je definován jako (|xi – x| + |yi – y| + |zi – z|) / pi, kde (x, y, z) je umístění vysílače a (xi, yi, zi, pi) je umístění a výkon přijímače jednotlivých lodí. Řešení

RLE permutace

PermutaceVstupVýstup
3, 1, 2, 4abcdcabd

Zadání: Máme algoritmus, který nejprve provede permutaci nad bajty zadaného vstupu a potom výsledek zkomprimuje algoritmem RLE. Naším úkolem je navrhnout permutaci dané délky, která pro zadaný vstup vrátí co nejmenší počet skupin stejných bajtů (jedná se o zjednodušení algoritmu RLE), a vrátit tento počet. Např. v posloupnosti aaaabbcaaa jsou čtyři skupiny stejných bajtů. Řešení

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

Diskuse

honza:

tohle jsou dost zajímavý úlohy, tak nějak jsem doufal že tohle v php nebude :D nikdy mi nešly tyhle úlohy....

Tom:

Tyhle úlohy ani tak nesouvisí s PHP, jako spíš s logickým myšlením a schopností z textového zadání sestavit vzorec/postup.
Tohle bych spíš než na Google Jam očekával na IQ testech, nebo tak něčem...

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.