Třetí série dvacátého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 28. ledna 2008. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh

I hroši létají, když fouká

Třetí série dvacátého ročníku KSP

„Á, konečně jsem to našel,“ zvolal mág nadšeně a vítězoslavně pozvedl knihu nad hlavu. „Tady se píše, že se musíme vydat směrem k Lávové hoře.“

Mág položil knihu na stůl a už se chystal provést složité kopírovací kouzlo, když se do věci vložil Felix: „Tak to vám tedy opravdu nezávidím. To budete mít docela štreku.“

„Kráá?“ ozval se nechápavě Kiri.

„Hm, na tom něco bude. Lávová hora není zrovna za rohem a létat na koštěti, to už na mě není. Průvan mi nedělá dobře na klouby.“

„No vidíte! Já říkal hned, že jsme měli zůstat doma,“ pochvaloval si kocour náhlou změnu plánu. Mág mu ale hbitě zkazil náladu: „Vildo, zajdeš na trh a pořídíš koně. Já tu zatím zkopíruji tu knihu, ať můžeme vyrazit ještě dnes!“

Vilda zašel k místnímu handlíři. Mezi dveřmi mu kývl na pozdrav a hned přešel k věci: „Rád bych si pořídil jednoho koně. Nemusí jezdit moc rychle, ale musí vydržet dlouhou cestu. Jo, a taky aby se neplašil, pokud uvidí něco neobvyklého.“

Handlíř vypadal velmi vyděšeně při pohledu na nazelenalého zákazníka. Byl by vzal nohy na ramena, ale z jedné strany mu v tom bránila zeď a mezi dveřmi stál Vilda.

„T-t-třeba t-t-tohohle?“ zakoktal handlíř, když se mu vrátila řeč a ukázal přitom prstem na krásného bělouše.

„A v černé by nebyl?“

„B-bílý táhne první. To je výhoda, ne?“ vyblekotal handlíř první argument, který mu přišel na mysl. V tu chvíli si ale Vildy všiml i bělouš, vzepjal se na zadní a málem tak převrhl koryto s vodou.

„Máte pravdu, tento není ten pravý,“ změnil handlíř názor.

Ale jak se ukázalo, žádný z přítomných koní nebyl dostatečně klidný, aby snesl pohled na Vildu. „Možná bych to mohl ještě stihnout, než…“ zamumlal si handlíř pod vousy a zmizel v přilehlém uzenářství. Za chvíli se vrátil a táhl za sebou něco, co budeme z nedostatku lepší terminologie nazývat koněm.

Kůň nevypadal, že by snesl cestu třeba jen za město, ale Vildův vzhled mu zřejmě nevadil. Dokonce se mu přiblížil natolik, že mu dokázal vytáhnout z kapsy svačinu.

„Ale vždyť je slepý na jedno oko!“ všiml si Vilda.

„Ano. A ani za to nebudu chtít příplatek.“

„Prosím?“

„Když uvidíte něco opravdu neobvyklého, prostě okolo toho projdete zleva.“

Netrvalo dlouho a obchod byl uzavřen. Ale když došlo k placení, nastal problém. Cena nepředstavovala žádné potíže, na té se shodli k oboustranné spokojenosti. Zato se ukázalo, že vybrat správné mince je těžký úkol.


20-3-1 Platba koně (12 bodů)


Je zadán obnos peněz P, požadovaný za koně, a dvě hromádky mincí (jedna Vildova a jedna handlířova). V každé hromádce mincí jsou mince různých hodnot a od každé hodnoty může být více mincí. Na Vildově hromádce je celkem N mincí, na handlířově M. Každá hodnota je desetinné číslo s přesností na 2 desetinná místa. Vaším úkolem je nalézt způsob, jak zaplatit přesně P na co nejmenší počet vyměněných mincí, nebo zjistit, že to provést nelze.

Pozn: Hodnoty mincí nemusí tvořit žádný systém běžných platidel ani být jinak „rozumné“.

Příklad: Pro P=15,00, Vildovu hromádku obsahující dvě mince o hodnotách 20,00 a 45,73 a handlířovu hromádku s mincemi o hodnotách 5,00 a 15,00 je správné řešení takové, že Vilda použije minci o hodnotě 20 a handlíř mu vrátí 5. Pro P=16,16 a stejné hromádky mincí řešení neexistuje.

Řešení

Naložili koně, mág se nechal vysadit do sedla a vyrazili na cestu. Cestovali dva dny, když se v křoví vedle cesty ozvaly hlasy. Družinka se zastavila a všichni pozorně naslouchali.

„Dneska byl nějaký nesdílný. Asi mi už nevěří,“ stěžoval si první hlas.

„Taky? Prý máme přepadat u severní cesty. Ale číslo stromu mi neřekl. Za prvním se nedá schovat, ale od druhého až k devadesát devátému je to stále ještě hrozně moc možností,“ rozumoval někdo další.

První si přisadil: „Hm, mně řekl jen součet čísel stromů.“

„Mně součin. Ale to mi moc nepomůže, z toho se nedají určit,“ kňoural druhý.

„I z toho součtu mi bylo hned jasné, že součin nikomu k ničemu nebude,“ souhlasil první.

„To ti z toho bylo jasné? Tak to já už vím, která čísla to jsou! Jdu si pro luk,“ zajásal druhý.

„Vážně? Tak v tom případě to vím také, kam jen jsem dal meč?“ pookřál první.

Mág sesedl z koně a celá družinka se ukryla za nedalekým kamenem. Sotva se jim podařilo přimět koně, aby si lehl, vyskočili lupiči na cestu.

„Už odešli. Tak bychom mohli jít také,“ prohlásil Felix, kterému se celá záležitost vůbec nelíbila.

„Ano, ale potřebujeme jít okolo nich,“ zaškaredil se Vilda.

„Vildo, ty jsi nezabalil čaj!“ postěžoval si mág, když se prohraboval sedlovou brašnou. „No, co se dá dělat. Vypadá to, že je budu muset proměnit v ježky.“

„Stejně tak, jako všechno ostatní, co se u každého stromu jen pohne?“ neodpustil si rýpnutí Felix. Kiri při představě proměny zděšeně opustil strom, na kterém seděl, a s mírným žuchnutím přistál vedle koně.

„No tak ježků je tu stejně málo, tak by to tak moc nevadilo. Ale alespoň bych si ušetřil práci, kdybych věděl, za kterými stromy jsou…“


20-3-2 Dva lupiči (8 bodů)


Úkolem této úlohy je najít všechny možné dvojice stromů, za kterými mají lupiči čekat. Nestačí řešení pouze najít, je třeba také zdůvodnit, proč je správné a proč žádné další dvojice neexistují.

Pozn: předpokládejme, že lupiči jsou dokonalí matematici (mají cvik v počítání lupu) a jsou z takových informací opravdu schopni zjistit svá čísla stromů v podstatě okamžitě. Tedy prohlášení: „Tak to já už vím, která čísla to jsou,“ není myšleno ironicky, ale opravdu znamená, že z dostupných informací dokáže odvodit ona čísla.

Pro případ, že by vám nějaké drobnosti utekly, uvedeme zde všechny informace ještě jednou: Velitel lupičů si myslí dvě celá čísla mezi 2 a 99. Lupiči A prozradí jejich součin, lupiči B prozradí jejich součet. Navíc A ví, že B zná součet, jen neví, kolik to je (a naopak). Rozhovor pak probíhá následovně:

A: „Nevím, jaká čísla si myslí náš velitel.“
B: „Věděl jsem, že to nebudeš vědět.“
A: „Opravdu? V tom případě už vím, co je to za čísla.“
B: „V tom případě to vím taky.“

Řešení

Felix opovržlivě přičichl ke zlatě, které vyplašení ježci nechali za sebou při zoufalém úprku. Ani tolik spěchat nemuseli, mezi našimi hrdiny nebyl nikdo ochotný běhat a mág prohlásil, že bodliny na zádech jako jejich trest zcela stačí.

„Tak to bychom měli,“ pochvaloval si mág potěšen, že se mu tak složité kouzlo podařilo.

„A dej si patentovat tenhle způsob výroby ostnatého drátu,“ navrhl Felix, který si při pozorování zlata všiml žížaly, která se nemohla zahrabat, protože měla po celém těle bodliny.

„Tomu se říká aktivní obranný systém. Teď ji alespoň nesezobne kos,“ vysvětlil mág a začal listovat v knize. „Utáboříme se tu na noc,“ dodal po chvíli čtení.

Vilda rozdělal oheň, vybalil deky a uvařil večeři. Noc uběhla rychle a až na vzdálené dupání ježků nic nerušilo mírumilovné ticho. Vildu ráno probralo sluníčko a rosa.

„Vaše Mágstvo, kam pokračujeme dál?“ zeptal se Vilda, sotva si protřel oči. Podíval se na mága a znejistěl: „Vždyť vypadáte jako kdybyste celou noc nespal!“ A opravdu. Mág měl červené oči, které držel sotva otevřené. Seděl u ohniště a okolo sebe měl rozloženou hromadu papírů popsanou divnými symboly.

„Uáááh, cožeto?“ zívl ospalý mág. „Aha, cesta. To je právě ten problém. Tady v knize sice píšou, že musíme najít Svítící bažinu. Ale celé je to popsané těmi starodávnými hádankami, takže nemám ponětí, kam dál.“

Hádanka Vildovi tak tajemná nepřipadala. Stálo v ní: „Cesta nejdelší – stále z kopce, jen osmkrát vykročit nahoru. A na konci cesty té, stoč se vpravo k obzoru.“

„A já nevím, jak takovou nejdelší cestu, co vede stále z kopce, jen osmkrát kousek do kopce, najít. A věštění nepomohlo,“ postěžoval si smutně mág.

„To se divím. Posledně se ty vosy vykouřit podařilo,“ ohodnotil jeho věštecké schopnosti Felix.

Kiri se probudil a slétl z větve, na které spal. Dopadl doprostřed papírů a vytvořil v nich malý kráter. Zoufale krákal a máchal křídly, aby se z té hromady dostal. Vzduch se naplnil poletujícími papíry a havraním peřím.

Vilda se natáhl, aby havrana vytáhl, když v tom mu přímo na nose přistál papír s nějakými čísly. Byly na něm vypsané výšky jednotlivých bodů na cestě.

„Ale vždyť stačí vybrat nejdelší takovou posloupnost čísel na tomhle papíru,“ zaradoval se a začal počítat.

„Kdybych nebyl tak ospalý, tak bych na to přišel sám…“ zamumlal mág, když usínal.


20-3-3 Cesta z kopce (8 bodů)


Je zadána posloupnost A obsahující N čísel a nějaké číslo k. Úkolem je nalézt indexy a, b (a ≤ b) takové, že b-a je největší možné a posloupnost Aa, … , Ab obsahuje maximálně k dvojic těsně po sobě jdoucích prvků Ai, Ai+1 takových, že Ai < Ai+1. Pro všechny ostatní dvojice platí Ai ≥ Ai+1. Tedy až na k míst je posloupnost nerostoucí.

Příklad: Pro k = 1 a posloupnost 9, 7, 6, 4, 8, 6, 3, 9, 1 je správným výsledkem a = 1 a b = 7, tj. podposloupnost 9, 7, 6, 4, 8, 6, 3.

Řešení

„Tady to vypadá strašidelně,“ postěžoval si Vilda, když se blížili k bažině.

„Samá voda. Alespoň nějaká lávka, kdyby tu byla,“ remcal Felix.

„Lávka tu sice není, ale jsou tu provazové mosty. A kolik,“ pochvaloval si mág.

A opravdu. Mezi stromy vedly stovky provazových mostů. Mág ze své kopie knihy vytáhl mapu Svítící bažiny a s pomocí ostatních se vydrápal na nejbližší most.

Procházeli bažinou křížem krážem, od jednoho stromu k druhému. Felix několikrát navrhl, že na ně počká na té či oné křižovatce, než se na ni zase vrátí.

„Rozhled na rašelinu bude z tamté křižovatky sice nádherný, ale klidně si ho nechám ujít.“

Když i mágovi došla trpělivost a konstatoval unaveně: „Ta mapa je špatně. Tady už jsme byli nejméně šestnáctkrát a na tamté křižovatce třináctkrát. Bloudíme mezi nimi stále tam a zpět. Mezi támhletou zatracenou křižovatkou a tímhle prokletým ztrouchnivělým stromem vede určitě nejvíce cest v celé bažině. Ale nemůžu je najít na mapě.“

„To bude tím, že ta mapa je pěkně stará. Provazové mosty zůstaly natažené mezi stejnými stromy, ale tohle je bažina a ty stromy v ní nedrží. Prostě se od té doby přemístily,“ mudroval Vilda a strčil do nejbližšího stromu. Strom se posunul o dobrý metr.

„V tom případě stačí zjistit, mezi kterými vede nejvíce různých cest. Z toho pak dokážu zorientovat mapu…“


20-3-4 Orientace na mapě (10 bodů)


Na vstupu váš program dostane popis orientovaného grafu znázorňujícího mapu. Víte, že tento graf neobsahuje žádný orientovaný cyklus, čili že neexistuje žádná orientovaná cesta délky alespoň 1, která by začínala a končila ve stejném vrcholu. Úkolem programu je vypsat dvojici vrcholů, mezi kterými vede nejvíce různých cest v celém grafu. Za různé jsou považovány libovolné dvě cesty, které se liší alespoň jednou hranou. Pokud je takových dvojic vrcholů více, stačí libovolná z nich.

Příklad: Pro tento graf je řešením dvojice vrcholů A a D:

Ukázka mapy

Řešení

Základní kouzlo

Konečně vylezli z bažiny na správnou stranu. Zajásali, rozvázali nebohého koně a mág z něho sňal levitační kouzlo. Vyškrábali se na nejbližší kopec a rozhlédli se po okolí. V dálce spatřili dýmající horu zahalenou v temných mracích. Lávová hora byla konečně na dohled…


20-3-5 Asfaltování (11 bodů)


Milí řešitelé a řešitelky,

Praktická úložka

blíží se zima a CodEx už se těší na vaše dárečky k Vánocům v podobě řešení úlohy třetí série. Způsob odevzdávání a všechny ostatní detaily zůstávají stejné, jako v minulých sériích. Takže pokud jste zapomněli, jak to v praktické úložce chodí, nebo jste se do řešení KSP zapojili teprve teď, podívejte se na úložku 20-1-5 z první série, kde naleznete potřebné informace.

Zadání:

Obyvatelé Hipopotámie si již dlouho stěžovali na nekvalitní silnice. Když si jednou i vrchní cestář při cestě do práce v kočáře vyrazil zub, rozhodl se k radikální akci. Doslechl se, že v sousední zemi začali na cesty používat novinku zvanou asfalt, a myšlenka na vyasfaltování všech silnic v Hipopotámii byla na světě. A jak si vrchní cestář usmyslel, tak se i stalo. Při realizaci nápadu se ale nižší cestáři museli potýkat s nemilým problémem: asfalt se dovážel ze sousední země v ohromných barelech, ve kterých bylo asfaltu tak akorát na dvě cesty (byly to opravdu ohromné barely). Potíž byla v tom, že jakmile se barel narazil a asfalt z něj začal vytékat, nedal se už proud asfaltu ničím zastavit a bylo tedy nutné vyasfaltovat najednou dvě na sebe navazující cesty. Jenže jak rozvrhnout asfaltování, aby cestáři neskončili ve městě s poloplným barelem a se všemi cestami vedoucími do města už vyasfaltovanými? Důsledky zalití náměstí a několika přilehlých čtvrtí do asfaltu by byly pro cestáře jistě nemilé...

Napište program, který pro zadané propojení měst cestami rozhodne, zda je možno cesty podle popsaných pravidel vyasfaltovat, a pokud ano, vypíše jednu z možností, jak rozvrhnout, která dvojice cest bude asfaltována ze kterého barelu.

Na prvním řádku vstupního souboru asfalt.in se nacházejí dvě celá čísla N a M oddělená mezerou (1 ≤ N ≤ 10 000 a 1 ≤ M ≤ 40 000), kde N určuje počet měst a M počet cest v Hipopotámii. Dále ve vstupním souboru následuje M řádků popisujících jednotlivé cesty. Každý řádek obsahuje dvě celá čísla A a B oddělená mezerou – čísla měst (města číslujeme od jedné do N), mezi kterými cesta vede. Předpokládejte, že mezi každými dvěma městy se lze po cestách dostat (pokud ne přímo, tak přes jiná města).

Výstupní soubor asfalt.out bude buď obsahovat jediný řádek s textem no, pokud neexistuje způsob, jak vyasfaltovat všechny cesty a neskončit s poloplným barelem v nějakém městě, nebo bude obsahovat M/2 řádků s popisem postupu asfaltování. Každý řádek postupu bude popisovat využití jednoho barelu s asfaltem, tj. bude obsahovat tři celá čísla oddělená mezerou, která představují po řadě: číslo města, ve kterém má asfaltování začít, číslo města, do kterého se má pokračovat a číslo města, ve kterém má asfaltování skončit.

Nezapomeňte, že každá cesta má být vyasfaltována právě jednou!

Příklad 1:

asfalt.in

 3 3
 1 2
 2 3
 3 1
asfalt.out
 no

Příklad 2:

asfalt.in

 5 8
 1 5
 1 4
 1 3
 1 2
 3 2
 3 4
 4 5
 4 2
asfalt.out
 5 1 4
 5 4 3
 4 2 3
 3 1 2

Řešení


20-3-6 Hrady, hrádky, hradla (12 bodů)


Milí řešitelé, nyní už víme, jak vlastně obvody fungují, jak jsou rychlé a energeticky náročné. V dnešním pokračování našeho seriálu si povíme něco o reprezentaci dat v binární podobě, tj. pomocí jedniček a nul.

Reprezentací dat zde myslíme nějaký způsob, jakým převést čísla nebo i jiné údaje do nul a jedniček, se kterými už umíme pracovat. Nejednodušší způsob, jak to udělat je dvojková neboli binární číselná soustava. Čísla se pak mezi desítkovou a dvojkovou soustavou převádějí následovně:

Dvojková Desítková

Vezmeme číslo zapsané ve dvojkové soustavě a budeme postupně brát cifry po jedné zprava doleva. Každou z nich vynásobíme dvojkou umocněnou na počet cifer, které jsou od aktuální cifry vpravo. Pro číslo 101010 to bude vypadat následovně: 0·20 + 1·21 + 0·22 + 1·23 + 0·24 + 1·25 = 2 + 8 + 32 = 42.

Jelikož a0·20 + a1·21 + a2·22 + … + an·2n lze přepsat jako a0 + 2(a1 + 2(a2 + 2(… + 2an )… ))), funguje i následující jednodušší převodní algoritmus: začneme nejlevější číslicí, znásobíme ji dvěma, přičteme další číslici, výsledek znásobíme dvěma, a tak dále.

Desítková Dvojková

Pokud je zadané číslo sudé, zapíšeme si nulu, v případě, že číslo je liché, zapíšeme jedničku a od čísla jedničku odečteme. Pak číslo vydělíme dvěma a postup zopakujeme. Jedničky a nuly budeme zapisovat zprava doleva tak dlouho, až se naše číslo stane nulou. Číslo 13 bychom převáděli takto:

číslo desítkovéčíslo dvojkovévýpočet
131(13-1)/2
6016/2
3101(3-1)/2
11101(1-1)/2

Všimněte si, že tento postup je vlastně předchozí postup pro převod z dvojkové soustavy spuštěný pozpátku.

Jiný používaný způsob, jak kódovat čísla do jedniček a nul, je kód BCD (Binary Coded Decimal). Myšlenka je následující: Když se rozhodneme trochu plýtvat, klidně můžeme kódovat desítková čísla po číslicích. Přitom na každou číslici použijeme 4 bity, a to tak, že využijeme 10 kombinací z 16 možných. Číslo 1394 bychom zapsali jako 0001 0011 1001 0100. Díky mírnému plýtvání jsme si značně zjednodušili práci, tedy aspoň v případech, kdy čísla daleko častěji rozebíráme na číslice, než s nimi počítáme. (Pěkný příklad jsou třeba digitální hodinky – ty musí umět číslo zobrazovat na displeji, ale jinak stačí umět přičítat jedničku.)

Někdy se také potřebujeme vypořádat s tím, že pokud přenášíme nějaký údaj do jiného obvodu (třeba po počítačové síti, a nebo ho ukládáme na disk), může se cestou trochu poškodit – některé bity se mohou změnit z nul na jedničky nebo naopak. Tehdy se samozřejmě hodí umět chybu odhalit, nebo dokonce automaticky opravit. Zkusme si třeba na konec binárního čísla přidat nulu nebo jedničku tak, aby celkový počet jedniček v čísle byl sudý (tomu se říká paritní bit). Pokud v takovém čísle nastane jedna chyba, ihned ji odhalíme, jelikož vždy vznikne číslo s lichým počtem jedniček. Existuje spousta sofistikovanějších kódů, které dokáží detekovat nebo opravovat větší počty chyb, ale my si už místo dalšího povídání raději naservírujeme nové úložky.

Úložky

Vaším úkolem nyní bude vymyslet obvod na detekci chyb, který bude testovat dělitelnost třemi (taková kontrola chyb je o něco silnější než parita).

1) Navrhněte a nakreslete obvod, který pro číslo zadané v binární reprezentaci zjistí, zda je dělitelné třemi. [6 bodů]

2) Úkol je stejný, ovšem čísla jsou na vstupu v BCD reprezentaci. [6 bodů]

Řešení