První série desátého ročníku KSP

Zadání úloh

10-1-1 Hanojské věže (10 bodů)

Bylo-nebylo. V dalekém městě Hanoji od nepaměti stál staroslavný klášter. Mniši v tomto klášteře žijící udržovali již po několik tisíciletí pozoruhodnou tradici: V jedné místnosti na stole z drahocenného dřeva ležela stříbrná deska se třemi křišťálovými hroty, na nichž bylo navlečeno dohromady 64 zlatých disků různých velikostí. Na počátku byly prý všechny disky na prvním z hrotů, seřazeny od největšího (ten byl dole) k nejmenšímu (nahoře). Každého dne pak za zvuku zvonů přenesli mniši obřadně jeden z disků na jiný hrot, a to tak, že nikdy neležel disk větší na disku menším. Legenda praví, že až se jim podaří všechny disky přemístit na třetí hrot, nastane konec světa.

Vaším úkolem je vymyslet algoritmus a napsat program řešící zobecněný případ této úlohy: na prvním hrotu máte N různých disků a máte je přenést na hrot třetí s dodržením uvedené podmínky. Program dostane na vstupu číslo N a jeho výstupem je posloupnost tahů, každý z nich popsaný dvěma čísly hrotů: odkud a kam se disk přenáší (jelikož je možno hýbat vždy jen s nejvyšším diskem na daném hrotu, je tak postup popsán jednoznačně). Spočtěte, kolik tahů (v závislosti na N) váš algoritmus použije a dokažte, že lépe to nejde.

Příklad: Pro N=3 program odpoví: 1,3 1,2 3,2 1,3 2,1 2,3 1,3.

Řešení

10-1-2 Bílá paní (10 bodů)

Na jednom hradě žila již několik staletí jedna bílá paní. Civilizace se na ní bohužel výrazně podepsala – v posledních letech ze záře světel nedalekého města oslepla a navíc byla z návštěvníků hradu tak nervózní, že se už nedokázala ani soustředit na projití zavřenými dveřmi, takže se o to od jedné nepříjemné nehody ani nepokoušela.

Hrad se skládal ze samých komnat uspořádaných do tvaru čtverce a každá komnata měla 4 dveře vedoucí do komnat sousedních (obvodové zdi hradu si můžeme představovat jako dveře, které se doposud nikomu nepodařilo odemknout). Naše bílá paní neměla jenom smůlu, ale také kocoura, jenž jí čas od času utekl a zalezl do jedné z komnat a ona jej pak musela hledat. Ač byla slepá, dokázala chodit rovně, ale když narazila na zavřené dveře, odrazila se od nich jako míček (změnila se vždy ta složka vektoru rychlosti, která by ji posunula přes dveře). Navíc ještě dokázala poznat, jestli je její kocour u ní (v téže komnatě) či nikoliv.

Napište algoritmus a program, který zjistí, zda bílá paní může či nemůže svého kocoura najít, známe-li její pozici a směr pohybu, jakož i polohu kocoura v hradu (kocour tvrdě spí a při tom se naštěstí pohybovat neumí). Na vstupu dostanete rozměr hradu M, směr, jímž se paní pohybuje (0=sever, 1=jih, 2=východ, 3=západ) a též mapu hradu – to je pole znaků M×M, v němž `0' znamená otevřenou místnost, `1' uzavřenou místnost (dveře spojující dvě otevřené místnosti jsou otevřené, všechny ostatní pak uzamčené), `A' otevřenou místnost, v níž je bílá paní (ta je v mapě právě jedna) a `B' otevřenou místnost, v níž je kocour (též unikátní). Výstupem programu bude odpověď, zda paní svého kocoura najde a pokud ano, v kolikátém kroku se jí to povede (jeden krok odpovídá posunutí do sousední místnosti či odražení od dveří).

Řešení

10-1-3 Bermudský trojúhelník (10 bodů)

Na jednom z ostrovů bermudského souostroví se znenadání objevil následující hlavolam: je to trojúhelník složený z čísel (na prvním řádku je jedno číslo, na druhém dvě, …, až na N-tém jich je N) – například tedy takto:

1
2 3
1 0 1
3 1 5 3

Úkolem je nalézt takovou cestu vedoucí od vrcholu trojúhelníku k jeho základně (v každém kroku se dostáváme na nižší řádek a to buď o pozici doleva nebo doprava), na níž leží čísla o co největším součtu. Zkuste vymyslet takový algoritmus, aby se dal v rozumném čase realizovat za pomoci tužky a papíru (to jest nepotřeboval milony operací či ohromnou paměť) a zapište jej jako program. Vstupem budiž počet řádků N a jejich obsah, výstupem pak posloupnost znaků `-' a `+', která pro každý řádek říká, jdeme-li dále doleva či doprava. Je-li nejlepších cest více, stačí vypsat pouze jednu.

Příklad: Pro výše uvedené zadání je jednou ze správných odpovědí `++-'.

Řešení

10-1-4 No to snad ne! (10 bodů)

Jistě již všichni znáte, jak funguje dvojková, trojková a jiné číselné soustavy: Každé číslo zapsané v soustavě o základu b číslicemi dkdk-1… d1d0 má hodnotu

V = ∑
k
n=0
dnbn.

Pro zapisování čísel záporných ovšem potřebujeme před číslo ještě přidat znaménko minus. Nešlo by to bez něj?

Murphyho zákon sice říká, že končí-li novinový titulek otazníkem, odpověď zní "Ne!", ale v tomto případě lze opravdu odpovědět kladně a dokonce ani nebudeme lhát: stačí totiž za základ soustavy b zvolit nějaké záporné číslo (například -2) a použít tytéž číslice jako pro původní kladný základ. Je až k podivu, že v takovéto šílené soustavě (váhy jednotlivých řádů vycházejí 1, -2, 4, -8 atd.) se dá zapsat libovolné celé číslo bez použití znaménka… (0 →0, 1 →1, 2 →110, 3 →111, 4 →100, -1 →11, -2 →10 atd.).

Na tomto místě se samozřejmě okamžitě nabízí zadat jako úlohu napsání programu pro převod mezi desítkovou a touto soustavou, jakož i zpětně. Ale tak snadné to samozřejmě nebude…

Napište program, který na vstupu dostane číslo r v desítkové soustavě (1 ≤ r ≤ 100) a číslo x v minus-dvojkové soustavě (pozor, toto číslo může být nepříjemně dlouhé – až miliony cifer) a zjistí, zda je číslo x dělitelné číslem r.

Řešení