Katedra počítačů ČVUT FEL & Czech ACM Chapter

Soutěž v programování 1999

Vážení soutěžící,

Jako každým rokem, i letos jsme pro vás připravili sadu úloh z reálného života. Tentokrát nám půjde o sestavení jedinečné Kolekce oblíbených kolektivních odborných, deskových a karetních her, ve zkratce KOKODáKH. Měla by obsahovat mnoho tradičních i méně známých her a očekáváme obrovský komerční úspěch po jejím uvedení na trh. Byli bychom rádi, kdybyste nám s realizací této ušlechtilé myšlenky (nezapomeňte, kdo si hraje, nezlobí) pomohli. Za odměnu vám slibujeme, že polovinu veškerých zisků, které nám nová kolekce přinese, rozdělíme mezi soutěžící v poměru počtu odevzdaných správných řešení. Máte tedy letos o motivaci více k tomu, abyste se s vervou pustili do řešení příkladů.

Vypracování uživatelského rozhraní bylo zadáno grafické firmě, proto nám jde již pouze o samotné algoritmy. Všechny programy, které máte vytvořit, budou číst vstupní data ze standardního vstupu a výsledky vypisovat na standardní výstup. V obou případech je nutné dodržet přesný formát, aby byla možná pozdější integrace s grafickým rozhraním. Je-li vstupem více hodnot na jednom řádku a není-li uvedeno jinak, jsou čísla oddělena právě jednou mezerou. Vstup ani výstup neobsahuje žádné přebytečné mezery, není-li v zadání příslušné úlohy uvedeno jinak.

Protože některé situace vyžadují dávkové zpracování více herních situací, musí být vámi vytvořené programy schopny řešit více instancí úlohy najednou. Obvykle je na prvním řádku uveden počet úloh, pak následují postupně všechna zadání. Přesný formát je uveden u každého příkladu. Pokud se v zadání vyskytují celá čísla a pokud není u konkrétní úlohy uvedeno něco jiného, pak je velikost čísel volena vždy tak, aby se všechna tato čísla i případné výsledky vešly do standardního typu integer.

Nyní nám již zbývá pouze vám popřát mnoho úspěchů při řešení těchto úloh.

Vaši organizátoři

Jack

(název programu: jack.c, jack.p, jack.C)

V kolekci KOKODáKH samozřejmě musí být alespoň jedna čistě počítačová hra. Jedna z nejtypičtějších, která se vyskytla snad již v miliónech různých variant, by se dala popsat jako ,,honička ve městě''. Usměvavý ksichtík, nazývaný v našem případě Jack, jezdí městem rozděleným na políčka, z nichž některá jsou zastavěna zdí a tedy se na ně nesmí. Sbírá přitom puntíky, za které získává body, a snaží se vyhýbat zákeřným monstrům, která se mu staví do cesty. Jestliže Jack pozře speciální tečku nebo hvězdičku, situace se na chvilku obrací a Jack může honit monstra. A tak dále, pořád dokola. Určitě jste takovou hru alespoň šestkrát viděli (a ještě alespoň šestkrát uvidíte).

Elektronický automat generuje město náhodně. Jack vždy začíná v levém horním rohu hrací plochy a ,,bonusová hvězdička'' je v pravém dolním rohu. V nejtěžší variantě hry je vše načasováno tak, aby hvězdička zmizela právě po takovém počtu kroků, za jaký se Jack dostane z rohu do rohu, pokud bude dělat pouze kroky doprava a dolů. Jakmile by udělal jediný krok jiným směrem, nemohl by již bonus stihnout. Přitom se však stále musí monstrům vyhýbat, je tedy potřeba vybrat správnou cestu. Vaším úkolem je určit, kolik takových cest v daném bludišti existuje.

Specifikace vstupu

Specifikace výstupu

Příklad vstupu

2
3 3
...
.#.
...
1 6
...#..

Příklad výstupu

Existuje 2 ruznych cest.
Existuje 0 ruznych cest.

Kaleidoskop

(název programu: kaleidoskop.c, kaleidoskop.p, kaleidoskop.C)

Předpokládáme, že s naší novou kolekcí KOKODáKH si budou hrát i nejmenší děti. Proto je v ní kromě všech možných her a hádanek také jedna hračka, k jejímuž používání není zapotřebí žádných znalostí ani dovedností. Přesto je velmi oblíbená nejen u dětí, ale i u dospělých. Touto hračkou je kaleidoskop. Jistě všichni znáte onu magickou rourku, do které lze zasněně hledět celé hodiny a hodiny a stále přitom nacházet nové a nové obrazce, které se nikdy neopakují. Dávejte však takové hračky do ruky malým dětem! Všechno hned zničí, každá rozbitná věc jim v nestřeženém okamžiku spadne z ruky na zem. Zvláště jemná soustava sklíček v kaleidoskopu je na takové zacházení velmi náchylná. Proto je kaleidoskop dodávaný v naší kolekci plně elektronický. Jeho hlavní výhodou je to, že je absolutně nerozbitný, nárazuvzdorný, ohnivzdorný, vlhkuvzdorný, ziměvzdorný, vodotěsný a nehořlavý. Kromě toho obsahuje speciální přepěťovou ochranu proti rozkousání. Umí totiž detekovat dotek chrupu na svém povrchu a každý takový pokus okamžitě trestá elektrošokem.

Zakladním problémem, který ale bylo nutné v elektronickém kaleidoskopu vyřešit, bylo generování obrazu. Aby dosahoval kvalit svého mechanického předchůdce, musí být obraz složen z podobných či stejných kousíčků, které se k sobě navzájem skládají pomocí otáčení a zrcadlení. Jak jistě mnozí z vás vědí, k otáčení, převracení, zvětšování, zmenšování a podobným hrátkám s obrazem se v oblasti grafiky používají transformační matice. Příslušná transformace se pak provede násobením matice maticí. Takto lze provést i velký počet transformací za sebou. Protože transformace v kaleidoskopu mohou být velmi složité, jsou rozměry matice někdy poměrně velké. Úkolem vašeho programu je právě vynásobení matice postupně řadou dalších matic.

Jestliže násobíme matici A o rozměrech m x p maticí B o rozměrech p x n dostaneme výslednou matici C s rozměry m x n. Každý prvek na souřadnicích i,j v této výsledné matici je skalárním součinem i-tého řádku matice A a j-tého sloupce matice B:

Specifikace vstupu

Vstup se skládá ze Z zadání. První řádek vstupu obsahuje právě jedno celé kladné číslo Z. Dále následují jednotlivá zadání. Každé zadání začíná řádkem s číslem X (1 <= X <= 10000) udávajícím počet matic, které je třeba vynásobit. Dále následuje X popisů matic. Popis matice začíná řádkem se dvěma čísly M a N (1 <= M,N <= 100), která udávají počet řádků a sloupců. Dalších M řádků odpovídá řádkům matice. Každý z nich obsahuje právě N čísel oddělených navzájem mezerou a udávajících prvky matice na daném řádku, zleva doprava. Je zaručeno, že matice bude možné násobit. Tedy s výjimkou první matice je číslo M každé matice rovno číslu N u matice předchozí. Velikost všech čísel je volena tak, aby se prvky výsledné matice vešly do standardního typu integer. Stejně tak by se do něj měly vejít prvky každé ,,mezivýsledné'' matice při postupném násobení v tom pořadí, v jakém jsou matice zadány.

Specifikace výstupu

Pro každé zadání vypíše program výslednou matici o rozměrech m x n. Výstup bude tvořen m řádky, na každém z nich bude n čísel oddělených mezerou. Za každým zadáním (včetně posledního) vytiskněte jeden prázdný řádek. Prázdný řádek obsahuje pouze znak ukončení řádku (newline). Jinak nesmí výstup obsahovat žádné přebytečné mezery a prázdné řádky.

Příklad vstupu

2
2
3 1
1
2
3
1 3
3 2 1
2
2 2
-1 1
-1 1
2 2
1 2
3 4

Příklad výstupu

3 2 1
6 4 2
9 6 3

2 2
2 2

Logik

(název programu: logik.c, logik.p, logik.C)

Součástí kolekce KOKODáKH je také logická hra ,,na lháře a poctivce'', kterou může hrát téměř libovolný počet hráčů a nejsou k ní třeba žádné speciální pomůcky. Pravidla jsou jednoduchá: na začátku si každý hráč hodí korunou a podle výsledku se určí, zda je lhářem nebo poctivcem. Všichni ostatní hráči to o něm vědí. Od chvíle, kdy se všichni takto rozlosují, musí poctivci za všech okolností mluvit pravdu a lháři musí vždy lhát. Kdo první toto jednoduché pravidlo poruší, hru zkazil a prohrává. Nevěřili byste, jak se někteří jedinci při hraní této hry náramně baví. S trochou praxe pak dovedou vyslovovat i velice komplikované výroky, o jejichž pravdivosti je často velmi obtížné rozhodnout. Špičkoví hráči pak dělají chyby jen velmi zřídka a jedno kolo tak může trvat i několik dní, během kterých otce rodin marně hledají ženy i děti.

Za největší zábavu je pak považováno, když do hrací místnosti vejde nezasvěcený pozorovatel. Hráči samozřejmě nepřestanou, spíše naopak. Snaží se zapůsobit na nově příchozího a vytvářejí věty, nad kterými zůstává rozum stát. Jedinou možností dotyčného nešťastníka je pak odhalit, kdo je lhářem a kdo poctivcem, aby se v konverzaci trochu vyznal. Ideální je pak přistihnout někoho při omylu, protože tím hra končí. Bohužel, toto odhalení není vůbec jednoduché. Vaším úkolem je napsat program, který vyslechne debatu hráčů a pokusí se určit, kdo je kdo.

Specifikace vstupu

Vstup se skládá ze Z zadání. První řádek vstupu obsahuje právě jedno celé kladné číslo Z. Dále následují jednotlivá zadání.

Každé zadání začíná jedním prázdným řádkem, který jej odděluje od předchozího textu. Dále je na samostatném řádku uvedeno číslo P (1 <= P <= 10) udávající počet hráčů. Pak následuje P řádků, na každém jedno jméno hráče. Jméno se vždy skládá pouze z písmen, první písmeno je velké, ostatní malá. V celém zbytku vstupu jsou pak jména uváděna přesně v tomto tvaru, ve kterém byla poprvé uvedena. Jméno hráče má minimálně 1 a maximálně 10 znaků, nikdy nemůže být tvořeno řetězcem "Lharu" ani "Poctivcu".

Dále je na samostatném řádku číslo M (0 <= M <= 500) udávající počet pronesených výroků. Poté je uvedeno M řádků, každý z nich dodržuje přesně tento tvar: jméno hráče, dvojtečka, jedna mezera, příslušný výrok a tečka. Žádný řádek není delší než 1000 znaků. Výroky mohou mít následující tvar (X,Y,Z jsou celá nezáporná čísla; H,F jsou jména hráčů; V,W jsou výroky). Všimněte si, že výrok 4 je ukončen tečkou, ostatní výroky nikoli:

1.

X + Y = Z

2.

H je poctivec

3.

H je lhar

4.

H rika "V".

5.

H rika "V" a je to opravdu tak

6.

H rika "V", ale neni to pravda

7.

Poctivcu je mene nez X

8.

Poctivcu je vice nez X

9.

Poctivcu je alespon X

10.

Lharu je mene nez X

11.

Lharu je vice nez X

12.

Lharu je alespon X

13.

(V) a zaroven (W)

14.

(V) nebo (W)

Výrok 4 je pravdivý, pokud hráč H mohl podle pravidel pronést výrok V (tj. pokud V není pravda a H je lhář, nebo pokud V je pravda a H je poctivec). Výroky 5 a 6 jsou vlastně dva nezávislé výroky (,,H říká V'' a ,,V platí/neplatí''). Pokud je tedy autor výroku lhář, musí být obě části nepravdivé, pokud je poctivec, musí být obě pravdivé. Takový výrok, kde by jedna z těchto částí platila a druhá ne, se nazývá nesplnitelný a nikdo jej nemůže vyslovit, aniž by tím porušil pravidla. Výroky 7 až 12 označují celkový počet lhářů či poctivců, tedy včetně hráče, který je pronesl. Výrok 13 je pravdivý, pokud jsou obě části současně pravdivé, a nepravdivý, pokud je alespoň jedna z nich nepravdivá. Výrok 14 je pravdivý, pokud je alespoň jedna z jeho částí pravdivá. Pokud je jedna z obou částí výroku typu 13 nebo 14 nesplnitelná, přihlíží se k ní, jako by byla nepravdivá. Dva nesplnitelné výroky spojené spojkou a zaroven nebo nebo dávají tedy výsledek nepravdivý, nikoli nesplnitelný. Lhář tedy takový výrok smí vyslovit.

Specifikace výstupu

Pro každé zadání vypíše program nejprve řádek "Hra cislo X:", kde X je pořadové číslo daného zadání, počítáno od jedničky.

Nejprve je třeba předpokládat, že nikdo z hráčů neporušil pravidla, tedy že lháři říkají nepravdivé výroky a poctivci pravdivé. Pokud existuje takové rozdělení hráčů na lháře a poctivce, při kterém by mohly být všechny dané výroky proneseny, říkáme množině výroků splnitelná. Jestliže byla na vstupu splnitelná množina, musí program vypsat roli všech hráčů, u kterých ji lze s určitostí zjistit. Každé takové tvrzení musí být na samostatném řádku a má buď tvar "H je lhar." nebo "H je poctivec.". Je-li tvrzení více, musí být uvedena v tom pořadí, v jakém byli zadáni hráči na vstupu. Pokud nelze s určitostí zjistit zařazení žádného hráče, bude výstupem řádek "Neda se nic zjistit.".

Jestliže je daná množina výroků dle pravidel nesplnitelná, je zřejmé, že někdo pravidla porušil, hru zkazil a tím i prohrál. V takovém případě je třeba odhalit, kdo to byl. Předpokládá se, že se to stalo pouze jedinému hráči. Jestliže hráč F porušil pravidla, je třeba přestat brát v úvahu všechny výroky, které on sám pronesl. Všechny ,,vnořené výroky'' typu ,,F říká V'' však zůstávají zachovány a mají stále smysl, neboť jejich sémantika je ,,F by mohl říct V, aniž by tím porušil pravidla''.

Pokud existuje právě jeden hráč F takový, že po vyškrtnutí všech jeho ,,hlavních'' výroků vznikne splnitelná množina, bude výstupem jediný řádek s textem: "F prohral.". Pokud existuje více takových hráčů F, pro které platí, že po vyškrtnutí všech jejich výroků bude množina splnitelná, vypíše program jediný řádek: "Prohral nektery z techto hracu: F1, F2, F3.".

Jestliže neexistuje žádný hráč, jehož výroky stačí vyškrtnout, abychom dostali splnitelnou množinu, vypíše program řádek: "Pravidla porusilo vice hracu.".

Za každým zadáním (včetně posledního) vypište jeden prázdný řádek. Prázdný řádek obsahuje pouze znak ukončení řádku (newline).

Příklad vstupu

2

3
Petr
Josef
Marie
1
Petr: Petr je lhar.

3
Petr
Josef
Marie
1
Josef: Marie rika "Marie je lhar" a je to opravdu tak.

Příklad výstupu

Hra cislo 1:
Petr prohral.

Hra cislo 2:
Josef je lhar.
Marie je poctivec.

Mocnění

(název programu: mocneni.c, mocneni.p, mocneni.C)

Lidé jsou různí. Někteří v noci potajmu čtou časopisy se zvláštními obrázky slečen, jiní potajmu staví ve sklepě atomovou bombu, další rádi používají Windows a někteří se dokonce baví složitými matematickými hříčkami. Poslední marketingový výzkum ukázal, že tento segment trhu byl dosud značně podceňován a takových her je zatím velký nedostatek. Proto bylo rozhodnuto do edice KOKODáKH také takovou hru zahrnout. Její pravidla jsou následující:

Každý hráč si sám vymyslí dvojici čísel A_i a B_i a napíše ji na papírek tak, aby ji ostatní neviděli. V daný okamžik všichni najednou své papírky ukáží ostatním. Úkolem hráčů je nyní určit součet všech výrazů A_i^B_i od všech hráčů včetně sebe a zjistit zbytek tohoto součtu po dělení předem daným číslem M. Kdo první stanoví správný výsledek, vyhrál. Podle zkušenosti hráčů lze snadno volit obtížnost zvětšováním daných čísel.

Vaším úkolem je napsat program, který spočítá výsledek a umožní tak hráčům zjistit, kdo z nich vyhrál.

Specifikace vstupu

Vstup se skládá ze Z zadání. První řádek vstupu obsahuje právě jedno celé kladné číslo Z. Dále následují jednotlivá zadání. Každé zadání začíná řádkem s celým číslem M (1 <= M <= 45000), kterým se má výsledek dělit. Na dalším řádku je počet hráčů H (1 <= H <= 45000). Dále následuje přesně H řádků, na každém z nich jsou právě dvě celá čísla A_i a B_i oddělená mezerou (0 <= A_i,B_i <= 2000000). Nikdy nejsou obě čísla současně rovna nule.

Specifikace výstupu

(A₁^B₁ + A₂^B₂ + ... + A_H^B_H) mod M.

Příklad vstupu

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

Příklad výstupu

2
13195
13

Nejvyšší zisky

(název programu: nejvyssi.c, nejvyssi.p, nejvyssi.C)

Tento program nebude přímo součástí kolekce KOKODáKH, ale možná je dokonce i důležitější než samotné hry. Má totiž sloužit pracovníkům marketingu, aby nalezli vhodný postup při propagaci a prodeji hotové kolekce. Proto si na něm dejte obzvášť záležet.

Rozsáhlá případová studie z oboru marketingu se snažila prokázat, že celkové výnosy z prodeje výrobku jsou polynomiální funkcí počtu spokojených zákazníků. Experimenty prokázaly, že sice výsledky podle této hypotézy nejsou v přímé korelaci se skutečností, ale přesto se tato metoda hojně používá. Pravděpodobně proto, že se zatím nikomu nepodařilo nalézt lepší postup. Jestliže tedy označíme počet spokojených zákazníků písmenem y, můžeme zisky (označené x) vyjádřit jako

x = P(y) = a₀ + a₁.y + a₂.y² + ... + a_m.y^m

Počet spokojených zákazníků přitom záleží na ceně výrobku a opět existuje hypotéza, že tato závislost je polynomiální. Jestliže označíme cenu jako z, můžeme tedy psát

y = Q(x) = b₀ + b₁.z + b₂.z² + ... + b_n.zⁿ

Koeficienty a_i a b_i jsou silně závislé na ročním období, fázi měsíce, kupní síle obyvatelstva, míře inflace a další stovce parametrů. Mimo jiné samozřejmě také na druhu výrobku a jeho kvalitě. Jejich empirickým výzkumem se však zabývalo již velké množství vědeckých prací, proto jsou pro různé kombinace vstupních parametrů uvedeny v Pyšvejcových marketingových tabulkách. Není tedy problém jejich hodnotu zjistit. Problémem však je, že stupeň obou polynomů je obvykle poměrně vysoký, a tak není snadné oba vzorce do sebe navzájem dosadit a spočítat závislost zisku na ceně. A tato závislost nás většinou zajímá nejvíce, abychom mohli nasadit optimální cenu výrobku.

Vaším úkolem je tedy napsat program, který dokáže dosadit polynom Q do polynomu P a určit výsledný polynom R udávající závislost zisku na ceně:

x = R(z) = c₀ + c₁.z + c₂.z² + ... + c_p.z^p

Specifikace vstupu

Vstup se skládá ze Z zadání. První řádek vstupu obsahuje právě jedno celé kladné číslo Z. Dále následují jednotlivá zadání. Každé zadání je tvořeno právě třemi řádky. Na prvním řádku jsou dvě celá čísla m a n (0 <= n,m <= 100) oddělená mezerou. Tato čísla udávají stupně polynomů Q a P. Na druhém řádku je m+1 celých čísel a₀ až a_m, která určují koeficienty polynomu P. Na třetím řádku je n+1 celých čísel b₀ až b_n. Vždy je a_m <> 0 a b_n <> 0. Koeficienty a_i a b_i jsou navzájem odděleny jednou mezerou a jejich velikost je volena tak, aby se každý z výsledných koeficientů c_i vešel do standardního typu integer.

Specifikace výstupu

Pro každé zadání vypíše program právě jeden řádek, na kterém bude p+1 čísel udávajících koeficienty výsledného polynomu c₀ až c_p. Koeficienty musí být odděleny mezerou a řádek nesmí obsahovat žádné přebytečné mezery navíc. Koeficient v nejvyšším řádu (c_p) musí být nenulový.

Příklad vstupu

3
0 0
7
-2
1 1
6 6
9 -6
3 3
-3 6 -5 1
0 3 -3 1

Příklad výstupu

7
60 -36
-3 18 -63 123 -156 138 -86 36 -9 1

Osmisměrka

(název programu: osmismerka.c, osmismerka.p, osmismerka.C)

Co by to bylo za soustavu her a hádanek, kdyby v ní chyběla slavná a dobře známá osmisměrka! Proto i KOKODáKH musí zákonitě tuto hříčku obsahovat. Klasická osmisměrka se skládá z obdélníkového pole vyplněného písmeny a ze seznamu slov. Tato slova je třeba uvnitř pole najít a všechna jejich písmena vyškrtnout. Vyškrtnutím se písmeno z pole neztrácí, stále může sloužit jako součást některého z dalších slov (slova se tedy mohou různě křížit i překrývat). Po vyškrtnutí všech slov ze seznamu zbydou v obrazci písmenka, která se po řádcích přečtou a vytvoří tak tajenku. Slova je možno nalézat ve všech osmi směrech (odtud název), mohou tedy běžet i šikmo.

Je jasné, že KOKODáKH musí i do této známé hry přinést jistou inovaci. Proto zavedl nové pravidlo, že slovo může ,,překročit'' hranice pole a pokračovat na jeho protější straně. Horní řádek tedy vlastně sousedí se spodním a levý sloupec s pravým. Pokud očíslujeme řádky čísly 0 až R-1 a sloupce čísly 0 až S-1, můžeme jednotlivá políčka s písmeny značit pomocí souřadnic. Například (0,0) odpovídá levému hornímu rohu. Slovo začínající na pozici (x,y) tedy může být tvořeno posloupností znaků se souřadnicemi (x,y), ((x+i+R) mod R, (y+j+S) mod S), ((x+2i+R) mod R, (y+2j+S) mod S) atd. Namísto i a j lze libovolně dosadit čísla -1, 0 a +1, pouze nesmějí být obě nulová.

Specifikace vstupu

Vstup se skládá ze Z zadání. První řádek vstupu obsahuje právě jedno celé kladné číslo Z. Dále následují jednotlivá zadání. Každé zadání se skládá z pole vyplněného písmeny a ze seznamu slov, které je třeba vyhledat. Popis pole začíná řádkem se dvěma celými čísly R a S oddělenými mezerou, 1 <= R,S <= 200. R je počet řádků osisměrky, S počet sloupců. Dále následuje R řádků, každý z nich obsahuje přesně S znaků malé abecedy, tedy pouze písmena a až z. Na dalším řádku je celé číslo K (0 <= K <= 1000) udávající počet slov, která se v osmisměrce hledají. Dále následuje K řádků, na každém z nich je právě jedno slovo. Maximální délka slova nepřesahuje 20 znaků. Slovo se v osmisměrce nemusí vůbec vyskytnout a může se vyskytnout i vícekrát. V takovém případě se vyškrtávají všechny jeho výskyty. Slova se v seznamu mohou opakovat.

Specifikace výstupu

Příklad vstupu

1
3 7
kroksun
pranyra
cmakrom
7
syr
kra
kroksunkrok
pranyr
rak
mak
makro

Příklad výstupu

acm

Patnáctka

(název programu: patnactka.c, patnactka.p, patnactka.C)

Snad každý dobře zná populární hlavolam nazývaný patnáctka. Je tvořen patnácti očíslovanými kameny, které jsou umístěny ve čtvercové krabičce s rozměry 4 x 4, jedna pozice je volná. Cílem je pomocí opakovaného přesouvání sousedních kamenů na tuto volnou pozici přeskupit kameny v krabičce tak, aby byly uspořádány podle svého čísla. Kámen s číslem 1 má být v levém horním rohu a další kameny seřazeny vzestupně po řádcích. Poslední pozice v krabičce (v pravém dolním rohu) zůstane v koncovém uspořádání prázdná.

Také KOKODáKH obsahuje variantu této hry. Vzhledem k tomu, že kolekce je určena pro pokročilé hráče, nevystačíme si samozřejmě s patnácti kameny a můžeme zvolit téměř libovolný rozměr hracího pole. Vaším úkolem je napsat program, který bude simulovat činnost tohoto hlavolamu. Pro zadanou výchozí pozici musí umět provést libovolnou sekvenci platných tahů a zobrazit koncový stav skládačky. Platným tahem je pouze přesun kamene na sousední volnou pozici vpravo, vlevo, nahoru nebo dolů. Všechny ostatní tahy jsou neplatné.

Specifikace vstupu

Popis stavu začíná řádkem, na kterém jsou dvě celá čísla R a S (2 <= R,S <= 1000) oddělená mezerou. R udává počet řádků a S počet sloupců skládačky. Poté následuje R řádků vstupu popisujících R řádků skládačky postupně shora dolů. Každý z těchto řádků obsahuje právě S celých čísel navzájem oddělených jednou až deseti mezerami. Na začátku řádku může (ale nemusí) být až deset mezer, které by měly být ignorovány. Na konci řádku žádné mezery nejsou. Každé číslo udává číslo jednoho kamene v daném řádku postupně zleva doprava. První číslo prvního řádku tedy odpovídá levému hornímu rohu skládačky. Všechna čísla jsou z intervalu 0 až R.S-1 a každé číslo se vyskytuje právě jednou. Nula se v popisu pozice vyskytuje také právě jednou a udává polohu prázdného pole.

Dále následuje seznam tahů, který může být i prázdný. Každý tah je uveden na samostatném řádku a je tvořen jedním číslem T (0 < T <= R.S-1), které představuje číslo kamene, kterým se má tah provést. Za seznamem je řádek obsahující pouze číslici 0. Tato nula pouze ukončuje vstup a není součástí seznamu tahů.

Specifikace výstupu

Pro každý tah v seznamu program zjistí, zda je takový tah platný. Tah je platný, pokud se vedle kamene s daným číslem vyskytuje prázdné pole. Pro každý platný tah vypíše program na samostatný řádek větu: "Kamen T presunut KAM.", kde T je číslo kamene a KAM je právě jeden z řetězců "doprava", "doleva", "nahoru" nebo "dolu". Pokud je daný tah neplatný, vypíše se věta "Neplatny tah kamenem T.".

Po skončení seznamu tahů vypíše program koncový stav skládačky v podobném formátu, jaký byl použit na vstupu. Výstup musí být tvořen R řádky, na každém z nich bude právě S čísel. Jediným rozdílem oproti vstupu je to, že čísla musí být oddělena právě jednou mezerou a na začátku řádku nesmí být žádné přebytečné mezery. Za každým zadáním (včetně posledního) pak program vypíše jeden prázdný řádek. Prázdný řádek obsahuje pouze znak ukončení řádku (newline).

Příklad vstupu

2
4 4
 1  2  3  4
 5  6  7  8 
 9 10 11 12
13 14 15  0
15
11
7
0
4 4
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14  0 15
1
0

Příklad výstupu

Skladacka cislo 1:
Kamen 15 presunut doprava.
Kamen 11 presunut dolu.
Kamen 7 presunut dolu.
1 2 3 4
5 6 0 8
9 10 7 12
13 14 11 15

Skladacka cislo 2:
Neplatny tah kamenem 1.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15

Quorf

(název programu: quorf.c, quorf.p, quorf.C)

Aby KOKODáKH dostála slůvku ,,karetních'' ve svém názvu, obsahuje také jednu méně známou karetní hru nazvanou Quorf. Jsou k ní potřeba tři stejné balíčky karet. Druh karet přitom může být téměř jakýkoli, stačí například i očíslované kartičky, důležité však je, že se každá karta smí v každém balíčku vyskytovat pouze jednou. Hra probíhá tak, že dva hráči připraví úkol třetímu a ten se jej snaží vyřešit. Velkou výhodou této hry je to, že se dá za jistých okolností provozovat i jako Solitér, tedy hra pro jednoho hráče. A právě tuto variantu má KOKODáKH obsahovat. Počítačový program, který máte za úkol napsat, bude vlastně zastávat úlohu obou ,,připravujících'' hráčů.

Princip hry je velmi jednoduchý. Každý ze dvou připravujících hráčů vybere z jednoho balíčku libovolné karty a ty zamíchá do náhodného pořadí, které se již nesmí měnit. Hlavní hráč má potom možnost si oba balíčky rychle prohlédnout a seřadit svůj třetí balíček do libovolného pořadí. Samozřejmě se jej snaží zvolit tak, aby v nadcházející hře vyhrál.

Samotná hra probíhá tak, že oba soupeři (které v našem případě představuje program) otočí vrchní kartu ze svého balíčku a položí ji na stůl. Hlavní hráč pak postupně bere karty z vrchu svého balíčku a postupně je také otáčí a ukazuje. Pokud přitom narazí na kartu, kterou má některý z jeho soupeřů otočenu na stole, vypadává tato karta ze hry a dotyčný soupeř musí otočit další. Pokud mají oba soupeři stejnou kartu a hráč ji vytáhne ze svého balíčku, vypadávají obě jejich karty a oba musí otočit další. Hra pokračuje tak dlouho, dokud hlavnímu hráči nedojde jeho balíček karet. Jestliže některému z protihráčů zbyla alespoň jedna karta, hráč prohrál. Pokud ani jeden z nich již žádnou kartu nemá, hráč vyhrál.

Roli protihráčů má tedy zastupovat program. Vygenerování obsahu obou balíčků není nijak náročná záležitost. Horší je to se zjištěním, zda hráč má možnost vyhrát. Vaším úkolem je napsat program, který bude schopen tuto skutečnost ověřit.

Specifikace vstupu

Specifikace výstupu

Příklad vstupu

2
4 4
1 2 3 4
4 3 2 1
4 4
1 3 5 7
2 4 6 8

Příklad výstupu

Spatne usporadani.
Hrac ma sanci vyhrat.