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

Termín odeslání Vašich řešení této série jest určen na 4. března 2019 v 8:00. Ř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.

Odměna série: Sladkou odměnu si vyslouží ten, kdo z každé úlohy série získá alespoň 2 body.

Zadání úloh

Ilustrace: Hroch vytírá podlahu

Bylo nebylo, za sedmero horami, devatero řekami, dvanáctero městy a dvacatero nukleonovými urychlovači stálo jedno malé hospodářství, ve kterém bydlel otec s dcerou. Matka jim nedávno zemřela, a tak se jal otec znovu oženiti. Jeho druhá žena do domu přivedla také své dvě dcery. Tím však pro ubohou dívku nastaly zlé časy.

Nevlastní sestry ji nutily tvrdě pracovat, uklízet, vařit, … prostě vše, co si umanuly. A protože dívenka mívala často tváře umouněné od popela, začaly jí říkat Popelka. Na rozdíl od Popelky její nevlastní sestry doma nehnuly ani prstem a zajímaly se jen o drahé šaty a šperky. Chudák otec pak musel každý druhý týden na nákupy do města.


Teoretická úloha31-3-1 Shánění látky (10 bodů)


Ve městě se nachází spousta obchodů nabízejících látky. Každý obchod však prodává jeden metr látky za jinou cenu. Kromě toho cestování také něco stojí, jelikož se na všech cestách vybírá mýtné. Nevlastní dcery posílají otce na nákup často, jenomže pokaždé chtějí koupit jiné množství látky. Pravidelné nákupy jsou poměrně finančně náročné, proto se otec snaží pokaždé naplánovat trasu tak, aby zaplatil co nejméně peněz. Chudák už je ale z toho všeho plánování zoufalý.

Město si můžeme představit jako neorientovaný graf, kde vrcholy jsou obchody a hrany jsou cesty mezi nimi. Každá hrana je ohodnocená cenou, kterou zaplatíme, když přes ni pojedeme. Každý vrchol je ohodnocen cenou za jeden metr látky. Jeden z vrcholů je označen jako výchozí, v něm otec s dcerami bydlí a vždy po nákupu se tam chce vrátit. Navrhněte algoritmus, který pomůže otci vyřešit jeho problém s plánováním. Algoritmus si nejprve něco předpočítá a pak bude dostávat dotazy typu „Jak nejlevněji pořídit metrů látky?“ Zajímá nás jak doba předvýpočtu, tak časová složitost jednoho dotazu. Můžete předpokládat, že dotazů bude řádově tolik, co obchodů, a že v každém obchodě lze koupit libovolné množství látky.

Jakmile otec dorazil domů, nevlastní dcery se na nakoupené látky slétly jako včely na med, začaly si je zkoušet a nakrucovat se před zrcadly. Popelka šla otce také pozdravit. Všimla si, že má ve vlasech zamotanou lískovou větvičku. Musela se mu tam dostat cestou z města… Vymotala ji a odnesla do svého kamrlíku. Sestry by otci nedovolily přivézt Popelce z města žádné cennosti, ale lískovou větvičku Popelce nechaly. Alespoň má od otce také nějaký dárek.

Jen co se sestry dostatečně nabažily pohledů na látky, vytáhl otec z brašny ještě jedno překvapení: zlaté náhrdelníky. Ve zdejším království se totiž chystal veliký ples, na kterém si prý mladý princ měl vybrat jednu dívku, kterou si vezme za ženu. Otec proto chtěl, aby se dcery mohly dostatečně vyparádit.


Teoretická úloha31-3-2 Cennější náhrdelník (13 bodů)


Kuchařková úloha

Obě nevlastní dcery dostaly od otce krásný zlatý náhrdelník. Protože jsou sestry velmi závistivé, hned se začaly dohadovat, čí náhrdelník je vzácnější. Hádaly se spolu do té doby, než se jedna z nich urazila a zavřela se do svého pokoje. Jediný, s kým je ochotna komunikovat, je jeden ze služebníků.

Sestry chtějí prostřednictvím služebníka zjistit, který náhrdelník je dražší. Na každém náhrdelníku je sice cenovka, ale protože spolu v současné době odmítají komunikovat napřímo, chtějí minimalizovat množství informací, které si spolu vymění. Naštěstí má každá z nich v pokoji výdobytek moderní doby – generátor náhodných čísel, který funguje tak trochu magicky. Generuje náhodná čísla tak, že i-té náhodné číslo první sestry je shodné s i-tým náhodným číslem druhé sestry. Vymyslete způsob, jakým sestry s pravděpodobností alespoň 75 % dokáží zjistit, čí náhrdelník je dražší.

Jak je v kryptografii běžným zvykem, pojmenujeme si sestry Alice a Bob. Každá má jedno binární číslo délky N a zázračný generátor, který jim oběma generuje stejná náhodná čísla. Cílem je s pravděpodobností alespoň 75 % zjistit, která ze sester má větší číslo, a to na co nejmenší počet vyměněných bitů.

Lehčí variantaLehčí varianta (za 8 bodů): Zjistěte jen, zda jsou oba náhrdelníky stejně drahé.

Několik týdnů se sestry připravovaly na ples, nechaly si ušít z látek nádherné šaty a učesat ohromující účesy. Všichni se na ples moc těšili. Když konečně nastal den D a sestry se nachystaly k odchodu, velmi je překvapilo, že Popelka chce jít taky. Vždyť tu má ještě spoustu práce! Popelka však tvrdila, že má vše hotové. Poslední týden tvrdě pracovala, aby měla nyní volno. To sestry naštvalo. Vzaly popel a hrách a sesypaly ho na zem.

Popelka byla celá zoufalá. „Vždyť tohle nemůžu v nějakém konečném čase stihnout roztřídit!“ „Ťuk, ťúúúk, ťúúúk, ťuk“ ozvalo se najednou. To na okno ťukal malý holoubek. Popelka, která byla zběhlá v luštění morseovky, pochopila, že se jí holoubek snaží nabídnout pomoc.


Praktická opendata úloha31-3-3 Přebírání hrachu (9 bodů)


Na podlaze se nachází sesypaný hrách s popelem a mezi tím poskakuje několik holoubků a vrabčáků. Chtějí Popelce pomoct vysbírat všechen hrách. Pro každou kuličku hrachu chceme zjistit, zda ji nějaký ptáček dokáže sezobnout a přenést do ošatky. Holoubci i vrabčáci se však pohybují každý jinak. Vrabčáci poskakují rovně dopředu, dozadu, doleva i doprava, zato holoubci chodí šikmo do všech čtyř stran.

Celou situaci si lze představit jako rozmístění figurek na šachovnici. Holoubci představují černé střelce, vrabčáci černé věže a kuličky hrachu pak bílé pěšáky. Pro každou bílou figurku chceme zjistit, zda ji dokážeme v jednom tahu nějakou černou figurkou vyhodit.

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku vstupu se nachází dvě čísla B a C, a to počet kuliček hrachu (neboli bílých figurek) a počet ptáčků (neboli černých figurek). Na dalších B řádcích se nachází souřadnice kuliček hrachu jako dvojice čísel oddělených mezerou, číslo řádku a číslo sloupce udávajících, kde se kulička nachází. Na dalších C řádcích se pak nachází pozice ptáčků – každý takový řádek obsahuje znak H nebo V a dvojici čísel udávajících řádek a sloupec, kde ptáček stojí (opět vše oddělené mezerami). Znak H značí holoubka (pohybuje se jako střelec) a znak V vrabčáka (pohybuje se jako věž). Figurky na vstupu mohou být seřazené náhodně.

Formát výstupu: Na B řádků výstupu vypište (ve stejném pořadí, jako na vstupu) pro každou kuličku hrachu ANO nebo NE podle toho, jestli existuje nějaký holoubek nebo vrabčák, který může tuto kuličku hrachu jedním tahem sezobnout.

Ukázkový vstup:
4 3
0 1
0 2
0 3
2 2
V 0 0
H 1 3
V 3 3
Ukázkový výstup:
ANO
ANO
NE
ANO
Šachovnice s příkladem
Poznámka: Všimněte si, že stejnou černou figurkou (střelcem) můžeme vzít dva bílé pěšce. Naopak bílého pěšce vpravo nahoře nemůžeme vzít ani spodní věží (v cestě stojí střelec), ani levou věží (v cestě stojí jiné bílé figurky).

Ilustrace: Hrošice před zrcadlem

Sestry netušily, že si Popelka rozumí s ptáčky, a měla tak vše za chviličku hotové. Ples by ještě stihla, ale kde teď narychlo sehnat šaty? Rozesmutnila se a rozběhla se do svého kamrlíku, kde se rozplakala. Proč jen má takové závistivé sestry, které jí nedovolí ani podívat se na ples! Rozhodla se, že si spraví náladu jídlem, a vzpomněla si na lískový oříšek od otce. „Ten bude určitě velice chutný,“ pomyslela si. Když ho však rozlouskla, nemohla uvěřit svým očím. Zevnitř vykukoval cíp šatů! Popelka zatáhla a z oříšku vypadly tak nádherné šaty, jaké ještě nikdy neviděla.

Když Popelka dorazila na ples, všichni byli okouzleni její krásou. Nevlastní sestry ji nepoznaly, protože doma nenosila nic jiného než otrhané šaty umazané od popela. Popelky si všiml dokonce i samotný princ a začal se prodírat davem tanečníků, jen aby si s ní mohl zatančit.


Teoretická úloha31-3-4 Dláždění sálu (11 bodů)


Ples se odehrává v největším a nejhonosnějším sálu na zámku, který nedávno prošel rekonstrukcí. Podlaha je nyní vydlážděná krásně barevnými dlaždicemi. Občas spolu ale sousední dlaždice neladí. Uměli byste sál vydláždit lépe?

Sál má obdélníkový půdorys o rozměrech K × N metrů a každá z jeho čtyř stěn je obarvená jednou barvou. Naším úkolem je sál vydláždit barevnými dlaždicemi o rozměrech 1 × 1 metr. K tomu jich máme dispozici hned několik druhů, přičemž každý druh dlaždice má pevně určené obarvení hran. Z estetických důvodů také s dlaždicemi nemůžeme otáčet, tj. každý druh dlaždice má určeno, která hrana bude otočená na sever. Od každého druhu můžeme použít neomezeně dlaždic. Umíme sál vydláždit, aby přiléhající hrany sousedních dlaždic a hrany sousedící se stěnami sálu barevně ladily? Zajímá nás časová a paměťová složitost pouze vzhledem k N, můžete předpokládat, že hodnota K a seznam povolených druhů dlaždic jsou pevně dané.

Znázornění ukázkového příkladu

V příkladu máme k dispozici šest druhů dlaždic, z nichž čtyři se od sebe liší jenom otočením (my však dlaždicemi otáčet nemůžeme, takže je považujeme za různé). Znázorněn je sál s K = 2N = 4 a jeho (jediné) vydláždění. Rozmyslete si, že pro K = 2, tyto druhy dlaždic a obarvení stěn umíme vydláždit právě všechny sály se sudou šířkou.

Když už se blížila půlnoc, Popelka si uvědomila, že se musí dostat domů dříve než její sestry, aby nikdo nepoznal, že na plese byla taky. Omluvila se tedy princi a zamířila ke schodům vedoucím ven z paláce. Princ se však během plesu stihl do Popelky zamilovat, a tak nezaváhal ani vteřinu a okamžitě se za ní rozběhl. „Neodcházej! Vždyť já ani neznám tvé jméno!“ zavolal za Popelkou. Jak se Popelka na schodech za princem ohlédla, ztratila na chvilku rovnováhu a nedopatřením se jí vyzul jeden střevíček. Princ jí však byl natolik v patách, že nechala střevíček střevíčkem a vyběhla ven z paláce.

Princ byl tuze smutný, že mu právě prchla největší láska jeho života. Jediné, co mu po ní zůstalo, byl onen střevíček. Rozhodl se, že pomocí něj neznámou princeznu vypátrá.


Teoretická úloha31-3-5 Hledání princezny (11 bodů)


Princ chce zjistit, komu střevíček padne. Jeho království je ale opravdu rozlehlé, a tak není v jeho silách zajít za každým osobně. Naštěstí však království o každém poddaném eviduje spoustu informací, včetně adresy bydliště a velikosti nohy (čirou náhodou je celý soupis seřazený zrovna podle velikosti nohy). Navíc je dvorní švec schopen podle předlohy vyrobit střevíček na chlup stejný jako originál. Výroba jednoho takového střevíčku trvá přibližně jednu hodinu.

Princ dostal nápad: Nechal po celém království vyhlásit, že každou hodinu pošle jednomu z poddaných střevíček, aby si ho vyzkoušel a v odpovědi poslal, zda mu je malý, velký, nebo akorát. Princ, znalý binárního vyhledávání, počítal s tím, že tak svou lásku dokáže najít v čase logaritmickém k počtu poddaných. To se ale přepočítal! Královská pošta už má svá nejlepší léta za sebou, a tak poslání střevíčku poddanému a následné doručení odpovědi trvá K hodin, kde K může (ale nemusí) být závislé na počtu poddaných v království. Jak má princ postupovat?

Trošku formálněji řečeno: Máme setříděné pole N čísel, ve kterém chceme najít konkrétní hodnotu. Dotaz můžeme poslat jednou za hodinu, ale trvá K hodin, než nám zpátky přijde odpověď. Dotazů můžeme mít na cestě více. Najděte časově efektivní algoritmus v závislosti na K.

Pátrání trvalo už několik týdnů a princ už začínal být celý zoufalý, že svou lásku nikdy nenajde. Až byl jednoho dne poslán střevíček také Popelce. Nevlastní sestry si byly jisté, že Popelce střevíček patřit nemůže, a tak jí ho ani nechtěly dát vyzkoušet. Otec se však (poprvé za celý svůj život) postavil proti jejich vůli a střevíček Popelce přinesl.

Jak byli všichni překvapeni, když Popelce střevíček padl jak ulitý. Princ nechal pro Popelku okamžitě poslat kočár a odvezl si ji k sobě na zámek. Za necelý týden se pak konala velkolepá svatba.

A žili spolu šťastně až do smrti…

Zuzka Urbanová & Klárka Tauchmanová

Ilustrace: Hroši a střevíček

Seriálová úloha31-3-6 Seriál (15 bodů)


Seriál chystáme a brzy se objeví.