Čtvrtá série dvacátého prvního ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

• Termín série: 30. 3. 2009
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak sepsat řešení: viz Návod na teoretické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

Zadání úloh

• 21-4-1: Dláždění šachovnice
• 21-4-2: Dosah kouzla
• 21-4-3: Stavění robota
• 21-4-4: Heslo
• 21-4-5: Znaky
• 21-4-6: Nejtěžší číslo

Jaro je sice ještě daleko před námi, ale medvědi i jiní pilní organizátoři KSP se již probudili z tradičního zimního spánku a přinášejí Vám další sérii úložek.

Čtvrtá série dvacátého prvního ročníku KSP

V tmavém sklepě se mihotalo světlo svíček. Průvan si hrál s jejich ohňem a stíny vrhaly podivuhodné tvary. Všude vládlo mrtvolné ticho, přerušované jen tichým dýchaním, občasným krysím zapištěním a …zachřestěním kostek?

„Zase pětka? Nemůžu mít ještě jeden pokus?“

„Ne, tady to máš v pravidlech – 'Každý hráč si na začátku hry naháže schopnosti postavy. Háže se dvacetistěnnou kostkou a jsou na to dva pokusy, z nichž si hráč vybere ten lepší'. Tak už přestaň kňourat ať popojedem, nemáme na to celou noc!“

„Ale síla 5? Kdo to kdy viděl, aby měl trpaslík sílu pět?“

„Ale to je jenom ve hře, Boendale, to jako nejseš ty …
Koukni, jaké sis zvolil povolání?“

Trpaslík se podíval do svých poznámek. „Haa-keř“, oznámil po chvíli.

„No vidíš, hackři nejsou moc silní. Zato jsou ale hodně inteligentní,“ snažil se Barun dál přesvědčovat hráče.

„Ale jak jako udržím svou sekyru, když budu tak slabej?“ Nemělo to cenu …

Všechno začalo asi před týdnem, když mezi starými magickými svazky svého mistra našel tu podivuhodnou knížku: CnH – Computers and Hackers. Zpočátku ji moc nechápal, popisovala jakýsi tuze zvláštní svět. Byl obydlen jenom lidmi, kteří nejenže neovládali magii, ale dokonce v ni ani nevěřil i! Místo toho v laboratořích stvořili jakési podivné zařízení, takzvané Počítače, které se pak naučili ovládat pomocí určitých příkazů a tyto se pak staly neoddělitelnou součástí jejich světa. Vypadalo to jako nějaká propaganda těch zatracených alchymistů. Ti se taky vrtali v různých strojích, místo aby se věnovali studiu magie. Už už se chystal knížku zaklapnout, když ho zaujal velký nápis: „Hra roku 2 149 třetího věku! Doporučuje 9 z 10 elfů!“ Ahá, takže hra! No to jsem zvědavý, co na to řeknou Boendal s Mírielem …

„Takže projdeme si pravidla ještě jednou, jo? Na začátku hry si každý hráč zvolí povolání. Řekněte mi popořadě, co jste si kdo zvolil.“

„Haa-keř,“ zamumlal mrzutě Boendal, ještě stále zklamaný z toho, že v herním světě s sebou nemůže nosit sekyru.

„Správce sítě. Hele, a můžu mít na sobě alespoň svoji modro-zelenou košilku?“ zeptal se s nadějí v hlase elf Míriel.

„Ne, tady jasně stojí – 'Pro správce sítě je typické vytahané, měsíc neprané, každodenně nošené tričko se vzorem tučňáka, případně ďáblíka.' Hele, hraj postavu, jo? Jinak ti strhnu body!“, sprdnul ho Barun. „Tak jo, další postava?“

„Uaargh!“

„Cože?“

„UAARGH!“

„Říká, že chce hrát algebraického topologa,“ překládal Míriel, „hele, já za to nemůžu, že mně teta hodila na krk hlídání bratrance. To víš, sehnat chůvu pro mladého trolla je dnes docela drahá záležitost …“

„No jo, no jo, chápu. Hele, tak já začnu. Takže, nacházíte se…třeba na přednášce ve škole - jste teď ještě jenom učňové, jo? Sedíte každý u svého Počítače, když tu najednou Boendalovi přijde ímejl.“

„Cože mi to přišlo?“ zeptal se polekaně Boendal.

„Něco jako dopis. Prostě zpráva. Každopádně když to otevřeš, tak zjistíš, že je to nějaká hra. Co uděláš?“

„Tak si zahrajem, ne?“ navrhnul Míriel a Barun začal vysvětlovat pravidla.

21-4-1 Dláždění šachovnice (8 bodů)

Hra je velice jednoduchá. Hráč na začátku dostane čtvercový plánek, něco jako šachovnici, o hraně velikosti 2^N políček. Jedno políčko ale chybí (libovolné). Úkolem je pokrýt šachovnici útvary podobnými písmenu L složenými ze tří kostiček. L-ka je povoleno otáčet. Vaším úkolem je nalézt algoritmus, jak pokrýt takovýhle plánek, ať je chybějící políčko na libovolném místě. Na obrázku je jedno z možných pokrytí pro N=3.

„Tak jo. Jakmile jste dohráli, objevila se na obrazovce zpráva: `Právě jste splnili kvalifikační test na soutěž o Nejlepšího crackera roku 2009!'“

„To jsem se právě kvalifikoval na sušenku?“ vyděsil se Boendal.

„Ach jo, na crackera, ne na krekr.“

„Fuul mít hlad!“ ozval se mladý troll a začal kolem sebe máchat rukama.

Míriel si povzdechl, zamával rukama, zamrmlal si něco pod nosem a krysa v rohu místnosti začala vonět pečeným masem. Fuul se po ní nedočkavě vrhl, pak se usadil a o poznání veselejší pozoroval zbytek družiny. Barun se ujal slova: „Tak co děláte dál?“

Řešení

21-4-2 Dosah kouzla (9 bodů)

Kouzlit, to není jen tak. Nejenže to vyžaduje hluboké vědomosti a určitou dávku energie, ale taky má každé kouzlo svůj dosah působnosti. Jaký do sah by muselo mít Mírielovo kouzlo, aby úspěšně zasáhlo krysu, ať by stála v kterémkoli rohu místnosti? On sám seděl taky v rohu místnosti a sklep má půdorys konvexního n-úhelníku. Na vstupu dostanete konvexní n-úhelník (n vrcholů popsaných souřadnicemi [x, y]) a vaším úkolem je najít dva nejvzdálenější vrcholy.

„Ne, pořád to nechápu“, trval na svém Boendal.

„Je to prostě taková skřínka a k ní je připojená jiná skřínka a k ní ještě jedna. Vidíš, tady to je na obrázku,“ Barun píchnul prstem do knížky. Už půl hodiny se snažil kamarádům vysvětlit, jak vlastně vypadá takový počítač a co obnáší programování.

„Takže když jako praštím do tady tý skřínky, tak na tamtý se něco objeví?“

„No, v podstatě nějak tak,“ povzdechl si Barun.

„Hele, a co je tady ten `Robot'?“ vyzvídal dál.

„Robot? To je takové mechanické zařízení, které za tebe dělá nějakou práci,“ vysvětloval Barun.

„Něco, co maká za mně? To zní hodně zajímavě …“ zalesklo se Boendalovi v oku a pustil se do čtení pravidel.

„Tak ty kabely zapojím tady!“ prohlásil vítězoslavně Boendal.

„No, když myslíš …Robot vstal, začal tancovat po okolí, vyházel pár hrníčků od kafe ven z okna, pak zalil kytku a sám se vypnul,“ popsal situaci Barun.

„Paráda, už to skoro funguje!“ těšil se Boendal.

„Hm, možná by jsme to neměli jenom tak zkoušet,“ snažil se zapojit do debaty Míriel.

„Ty se do toho nepleť. Už jenom pár pokusů a budeme mít prvního robota na zaplétaní vousů na světě! Nedovedeš si představit, jaká je to otrava dělat to každý den ručně …“

Řešení

21-4-3 Stavění robota (10 bodů)

Boendalova technika stavění robota je vskutku originální. Prostě si vybere nějaké vstupy na základní desce, a ty pak připojí kabely ke zdroji. Při různém propojení dělá robot různé věci. Boendala by zajímalo, kolik různých věcí dokáže robot dělat, když má N výstupů a K kabelů. Nejjednodušší způsob, jak daný problém vyřešit, je spočítat kombinační číslo

(	N	)
	K

, což se dá rozepsat jako

N·(N-1)·...·(N-K+1)

K·(K-1)·...·1

.

Příklad 1: Vstup: 6 2 100 Výstup: 15

Příklad 2: Vstup: 1000 400 1270 Výstup: 1040

Tato úložka je praktická, což znamená, že řešení budete odevzdávat výhradně formou odladěného zdrojového kódu. Přesnější zadání a formulář na odevzdání kódu naleznete jako vždy v CodExu. Nevíte-li, co praktická úložka je a jak přesně postupovat, podívejte se do zadání úlohy 21-1-2 „Optimalizace kotlů“.

„BUUM!, ozvalo se v školní laboratoři. Právě jste zničili kus budovy. Z tohohle bude pořádný průšvih …“ popisoval situaci Barun.

„Tak zdrháme, ne?“ navrhnul trpaslík.

„No, to teda nebylo moc rozumné. Stejně na vás přišli a …jste podmíněně vyloučeni. Jo, to by mohl být adekvátní trest,“ oznámil jim Barun.

„Hm,“ zamyslel sa Míriel, „a kde jsou uloženy školní záznamy?“

„Myslím, že záznamy jsou uloženy výhradně v elektronické podobě, na centrálním školním počítači. Proč se ptáš?“

„Hehe, jsme přeci nějací hackři, nebo ne?“ usmál se na Baruna elf.

„Napiš tam `heslo'! To bude určitě fungovat!“ povzbuzoval Míriela Boendal, „nebo `pás-vord'!“

Už hodinu se snažili dostat se na speciální stránky školního systému, ale zatím bez úspěchu.

„Hele, když to nejde logicky, vem větší sekyru. Zkusíme tam napsat postupně všechna možná hesla,“ navrhnul Boendal.

„To zní dobře, ale netrvalo by to příliš dlouho?“ pochyboval Míriel.

„Hm …Ale mohli bychom tam zkusit zadat každé páté možné heslo, nebo každé sedmé.“

Řešení

21-4-4 Heslo (10 bodů)

Heslo, to je vlastně permutace nějakých znaků, z nichž se některé můžou opakovat. Řekneme, že permutace p₁ je lexikograficky menší než permutace p₂, pokud první znak, ve kterém se liší (bráno zleva doprava) je na i-té pozici a platí p₁[i] < p₂[i]. Příklad: Mějme znaky 1, 2, 3 a 3. Pak jejich permutace 2133 je lexikograficky menší než permutace 2313. Permutace jsou seřazeny lexikograficky, pokud jsou seřazeny od nejmenší po největší. Pokud vygenerujeme všechny možné permutace určitých znaků a seřadíme je lexikograficky, pak permutace o K větší než zadaná permutace je permutace na pozici o K větší.

Na vstupu dostanete permutaci cifer (cifry se mohou opakovat) a číslo K a vaším úkolem je najít permutaci o K větší.

Příklad: Vstup: 1234 3    Výstup: 1423 (protože po permutaci 1243 následuje permurace 1324, pak 1342, no a o 3 větší je permutace 1423).

„Gratuluju, tak jste se právě dostali do Školního informačního systému! Na obrazovce se objevily nějaké znaky – a vy jim vůbec nerozumíte. Vypadá to, že stránka je šifrovaná,“ oznámil družině Barun. „Co uděláte?“

„Hm, asi by to chtělo nějak líp prostudovat ty znaky. Jak vypadaj?“ zajímal se Míriel.

„No, je to velice jednoduché,“ zalesklo se Barunovi v očích a začal popisovat znaky šifry …

Řešení

21-4-5 Znaky (10 bodů)

Znak je reprezentován čtvercem o hraně délky N pixelů, ve kterém je přesně N pixelů vybarvených. Platí ale, že v každém vodorovném, svislém i šikmém směru je vybarvený maximálně jeden pixel. Míriel si ale všimnul, že některé čtverce se opakují a že by se mu hodilo vědět, kolik různých znaků se to vlastně v šifře používá.

Na vstupu dostanete přirozená čísla N a K, a pak K čtverců popsaných výše. Čtverce budou reprezentovány jako dvourozměrné pole integerů: 1 znamená, že pixel je vybarvený, 0 že není. Vaším úkolem je zjistit počet unikátních čtverců, tak, aby váš algoritmus měl co nejmenší paměťové nároky (reálné, nejen asymptotické).

„Výborně! Povedlo se vám rozluštit ty znaky a na obrazovce čtěte nápis …“

„Míííriéééli! Kde to zase vězíš?! Večeře je už hotová a ty jsi ještě nenakrmil draka!!“

„A jeje, máma,“ povzdechl si Míriel.

„Sakra, to mi připomíná, že bych měl taky pomalu jít. Slíbil jsem bráchovi, že mu pomůžu se skládáním hudby k jeho nejnovějšímu hitu `Zlato, zlato, zlato!'.“

„Hm, tak pro dnešek asi konec. Dohrajem to někdy příště,“ usmál se Barun a uklidil knížku k sobě do batohu.

A tak se družina rozešla – Míriel šel nakrmit draka, Boendal komponovat hudbu a Fuul se vyvalovat v jeskynním jezírku. A Barun? Hned na druhý den si šel k alchymistům půjčit pár knížek. Pár dní na to se několik sousedů stěžovalo na hluk v okolí magické laboratoře, a asi za týden byl spatřen, jak za bouřky chytá blesky do velké černé krabice …

Řešení

21-4-6 Nejtěžší číslo (12 bodů)

Tuto úlohu musíte řešit v programovacím jazyce RAPL, jehož popis najdete v zadání úlohy 21-1-6 z první série.

Tentokrát budeme ovšem místo nejkratšího programu hledat program nejrychlejší. Nebude nás ale zajímat asymptotická časova složitost programu, nýbrž skutečný počet provedených instrukcí RAPL.

Vše se bude točit okolo vážení čísel. Vahou čísla nazveme počet jedniček v jeho dvojkovém zápisu. Nula má tedy váhu 0 (a je to jediné číslo s nulovou vahou), mocniny dvojky mají váhu 1 a třeba takové číslo 1 000 je těžké 6 jednotek, protože jeho dvojkový zápis je 1111101000.

a) Napište co nejrychlejší program, který je spuštěn s číslem v registru x a odpoví jeho vahou uloženou v registru w.

b) Vymyslete co nejrychlejší program, který dostane n čísel A[1] až A[n] (1≤ n≤ 2³²-1) a odpoví v registru y nejtěžším z těchto čísel. Pokud je nejtěžších čísel více, může si vybrat libovolné jedno z nich.

Řešení