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

Termín odeslání Vašich řešení této série jest určen na 16. dubna 2018. Ř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ží každý, kdo vyřeší alespoň 4 úlohy na alespoň polovinu bodů.

Zadání úloh

Zkouškové na Matfyzu? Ne, že by to byla taková hrůza, spíš nezávidím svému trávicímu systému. Zítra mám zkoušku v devět hodin ráno (ráno, snad jste si na matfyzácké pojetí času už zvykli) a kromě obědů v menze jsem zbytek svého stravování řešil bagetami. Ono je to tak hrozně praktické, koupíte je na vrátnici kolejí, je na ně studentská sleva a nemusíte nic vařit. Ale určitě bych na kombinaci sýrových a šunkových baget nechtěl přežít celé zkouškové, i když prý jsou někteří přeživší, kterým se to povedlo.

Venku se už setmělo a je čas na večeři. V kuchyňce si otevřu ledničku, sáhnu po bagetě a chci se vrátit zpátky do pokoje, když vtom se to stane.

Najednou se mi zatočí hlava a před očima se mi udělají mžitky. Chci se chytit dveří, abych nespadl, ale místo toho mávnu rukou do prázdna. Chvíli jsem úplně zmatený a bezmocný. To se mi určitě z těch pitomých baget udělalo špatně… Pak ucítím, jak ležím na pevné zemi. Nejdřív si myslím, že jsem prostě omdlel. Jenže pak zaslechnu divné zvuky, které na matfyzácké koleje moc nepatří.

Nejdřív ucítím silný vítr s podivnou vůní. Pak zaslechnu šumění vln, které naráží na… pobřeží? Otevřu oči. Moje nezdravá strava mi zřejmě musela způsobit nějaké divné halucinace. Jinak si nedovedu vysvětlit, proč teď ležím na písečné pláži a přede mnou je širé moře.

Ať tohle přestane! Než se zase vrátím do normálu, sednu si a budu počítat přicházející vlny, abych se trochu uklidnil.


Praktická opendata úloha30-3-1 Vlnění (9 bodů)


Uvažujte čtvercovou síť představující vodní plochu. Z levého spodního pole se do ostatních polí šíří střídavě bílé a černé vlny. Podívejte se na obrázek, kde tečky jsou části bílých vln a dvojité mřížky jsou části černých vln:

####
...#
##.#
.#.#

Čtvercová síť má v levém spodním poli počátek a směrem doprava a nahoru je nekonečná (obrázek představuje jen malý výřez). Vaším úkolem je zjistit počet čtverců, které představují černé vlny, v zadané obdélníkové oblasti sítě.

Program dostane na vstupu souřadnice levého spodního rohu a horního pravého rohu obdélníku, vždy nejprve číslo sloupce a poté číslo řádku. Číslujeme od nuly a počátek je pochopitelně ve spodním levém poli. Protože zadaný obdélník může být potenciálně rozsáhlý, chceme znát hodnotu výstupu modulo 1000000007 (tedy zbytek po dělení výsledku tímto číslem).

Ukázkový vstup:
1 0
2 3
Ukázkový výstup:
4

Z počítání vln mě vytrhne nějaký hlas. „Ty jsi org KSPčka?“ „Ano, to jsem já.“ „Vítám tě v Japonsku. Jestlipak víš, kdo jsem?“

Pozoruji člověka, který se tu právě objevil. Má úplně plešatou hlavu. Říká, že tohle je Japonsko, že by to byl nějaký zenový mnich? Ale pak si prohlédnu jeho oči a dojde mi to. Je to pan Nápověda! Musel si ostříhat vlasy a celkově změnit svoji vizáž, jinak bych ho hned poznal.

„Podle tvého výrazu usuzuji, že už to chápeš. Jsme v Japonsku a všichni Japonci jsou takoví mírní a úslužní, takže tady nechci žádnou zbytečnou potyčku. Stačí, abych ti ukázal, že nemáš šanci utéct.“

Instinktivně se chci otočit a zahájit úprk (i když je otázkou kam), ale s hrůzou zjistím, že to nejde. Vůbec se nemůžu pohnout, ani nohama, ani rukama, nijak! Jako kdybych vězel v nějaké svěrací kazajce. V Nápovědově ruce se objeví drobná černá krabička.

„Tohle se mi tady podařilo sehnat. Dokáže to na docela velkou dálku zmrazit pohyby jakéhokoliv člověka. Dýchat ti to dovolí, ale nic dalšího. Umí to zmrazit i víc lidí najednou.“


Teoretická úloha30-3-2 Zmrazovač (10 bodů)


Pan Nápověda pověřil dva ze svých agentů, aby znehybnili co nejvíce nepřátel. Nepřátelé stojí na rovné cestě o celkové délce K a pro každého z nepřátel znáte jeho pozici P, 0 ≤ P ≤ K, P ∈N. Každý z agentů má k dispozici znehybňovací zařízení, které zmrazí jakéhokoliv nepřítele, jehož vzdálenost k agentovi je menší nebo rovna X.

Máte zadané parametry K, X a pozici každého nepřítele s tím, že nepřátelé jsou už na vstupu seřazeni podle své pozice. Najděte dvě celočíselné pozice na cestě, kam si mohou stoupnout agenti, aby znehybnili co největší množství nepřátel.

Příklad ukazuje úlohu s K = 14X = 2. Dokážeme zmrazit všechny nepřátele, pokud umístíme agenty na polohy 6 a 10 (vyznačené trojúhelníčkem).

Příklad úlohy

Pro jistotu ještě opakujeme: pozice nepřátel i agentů jsou celočíselné.

„Ale jak jsem se sem, do háje, dostal?“ ptám se. Nápověda se zasměje. „Že sis vzal něco na památku z mého bunkru?“ „No, zkoumali jsme nějaké věci, které se tam našly. Já si vzal na kolej takové divné těžítko, chtěl jsem to, až skončí zkouškové, rozebrat…“

„To tvoje těžítko byl experimentální teleportér,“ vysvětlí mi. „Asi se nějakým omylem zapnul. Můžeš být vlastně rád, že jsi naživu a že tě to neposlalo třeba na zemskou oběžnou dráhu – někteří zvědavci, kteří to zkoušeli, skončili takhle ošklivě. Poslední firmware, který se tam nahrál, teleportoval lidi do blízkosti mé osoby, proto jsi skončil tady. Kdyby to zařízení bylo trochu přesnější a spolehlivější, hodně by mi to ušetřilo přesuny.“


Teoretická úloha30-3-3 Teleportér (9 bodů)


Pan Nápověda kdysi vybudoval řadu N tajných základen. Ty jsou očíslované a platí, že jediná cesta z i-té do (i+1)-té základny vede tunelem o délce Di, což je kladné číslo. Pro cestu mezi dvěma vzdálenějšími základnami je tedy nutné projít všechny tunely mezi nimi. Hlavní sídlo pana Nápovědy se nachází v první základně a uvažujeme veličinu Mi jako délku nejkratší cesty z i-té do první základny.

Spočtení Mi je při tomto zadání triviální (prostě sečteme délky všech tunelů mezi základnami). Výzkumnému týmu se však podařilo vyrobit teleportér. Chtějí vybrat dvě základny, mezi kterými bude možnost okamžitého přesunu – jako bychom mezi ně přidali nový tunel s délkou 0. Při cestách mezi jinými základnami je samozřejmě na část cesty možné teleport využít také.

Pan Nápověda chce umístit teleportér takovým způsobem, aby se co nejvíce zrychlila cesta do první základny. Vyberte, do jakých dvou základen umístit teleportér, aby maximum všech Mi (pro všechny základny) bylo co nejmenší.

Pozor, zvláště v této úloze chceme důkaz správnosti vašeho řešení.

Na obrázku vidíte zadání úlohy s jediným správným řešením – nejdelší cesta vede z vrcholu mezi tunely délky 3 a 5, kdy musíme projít tunelem délky 5 a potom teleportérem.

Příklad úlohy

Nápověda si otráveně povzdychne, jako by ten rozhovor trval až moc dlouho. „Když jste zničili můj bunkr, přišel jsem o všechno. Pomocí jednoho teleportéru jsem se přenesl do Tokia, kde jsem měl aspoň nějaké kontakty. Nic z mých vynálezů se ale nezachovalo. Zmohl jsem se na útok s tím počítačovým virem, ale jinak musím celé své impérium vybudovat znovu… Proč ti to vlastně říkám? Taky nemusíš vědět všechno,“ usměje se. Znovu vytáhne znehybňovací krabičku, stiskne na ní tlačítko a já omdlím, tentokrát opravdově.

* * *

Když přijdu k sobě, jsem v nějaké temné kobce, jen spoře osvětlené poblikávající zářivkou. Začínám mít dojem, že tu zítřejší zkoušku nestihnu.

Jsou tady dveře, ale samozřejmě zamčené. V rohu místnosti se nachází stůl, židle a na stole zapnutý notebook. Na displeji se postupně zobrazují červené a zelené tečky. V rohu svítí nápisy: hmotaantihmota. Pak začne blikat jiný nápis: odděl je! Tak si sednu a začnu to řešit. Nemůžu si pomoci, skoro to vypadá, že mě Nápověda přihlásil do nějaké programátorské soutěže.


Teoretická úloha30-3-4 Hmota a antihmota (12 bodů)


Kuchařková úlohaJednomu z pracovních týmů pana Nápovědy se podařilo najít způsob, jak od sebe oddělit částice hmoty a antihmoty. Protože se ale stále jedná o experiment, potřebovali by ověřit, zda jsou od sebe odděleny skutečně dokonale. Pro jednoduchost budeme uvažovat jen částice ve dvourozměrném prostoru.

Dostanete k dispozici seznamy částic hmoty a částic antihmoty. Každá částice je popsána dvěma čísly, které představují její souřadnice. Hledáme přímku, která rozdělí plochu tak, že všechny částice hmoty jsou na jedné straně a všechny částice antihmoty na druhé straně. Zjistěte, zda taková přímka vůbec existuje, a pokud ano, určete její pozici.

Lehčí variantaLehčí varianta (za 7 bodů): Zjistěte jen, zda přímka existuje, nebo ne.

Tohle mi nějaký čas zabralo. Jakmile jsem poslal řešení, notebook potemněl. Nic nenasvědčuje tomu, že bych měl teď něco dělat. Slyším, že za dveřmi neustále někdo prochází. Nejspíš to je nějaká frekventovaná chodba. Vůbec, jak může být tahle základna velká? A kolik lidí tu pracuje? Pokud takové skupině velí zločinec, jak si zařídí, aby se jeho podřízení třeba nevzbouřili?


Teoretická úloha30-3-5 Rozbití skupin (8 bodů)


Pan Nápověda velí japonské tajné základně, kde se nachází velké množství personálu z různých částí země. Protože ale své podřízené dvakrát nerozmazluje co se týče jídla a volného času, má obavy ze vzpoury proti své osobě. Taková vzpoura by vyžadovala součinnost více lidí a Nápověda si všiml, že nejvíce si na základně rozumí lidé se stejným místem původu. Chtěl by proto snížit pravděpodobnost toho, že se takoví lidé budou často setkávat.

Základnu tvoří jedna dlouhá chodba, na níž se za sebou nachází N stolů, každý stůl připravený pro jednoho zaměstance. Každý zaměstanec může pocházet právě z jednoho z P různých míst původu. V aktuální situaci jsou některé stoly neobsazené, jiné jsou obsazeny zaměstancem, jehož místo původu známe.

Nápověda chce přijmout zaměstance na každé zatím neobsazené pracovní místo, přičemž u každého místa si může vybrat, z jakého místa původu bude pocházet nový pracovník. Aby se však zaměstanci nemohli tak snadno domluvit na převratu, má Nápověda požadavek: nikdy nesmí dojít k tomu, aby vedle sebe sedělo více než M zaměstanců se stejným místem původu. Zároveň ale nechce přesouvat zaměstance, kteří už na základně pracují.

Pro zadané N, M, P a popořadě popis každého stolu (neobsazený/obsazený zaměstancem s nějakým místem původu) zjistěte, kolik existuje různých možností, jak doobsadit prázdné stoly, aby byl zachovaný Nápovědův požadavek. Dvě možnosti doobsazení jsou různé, pokud se alespoň u jednoho zaměstance liší místo původu.

Příklad: Máme N = 7, M = 2, P = 2, a chodbu zadanou takto: ABB.AB. (AB označují dvě různá místa původu, tečka prázdné místo). Existují dvě různá řešení: ABBAABAABBAABB. Prázdné místo nalevo musí být doplněné „áčkem“, protože by se jinak vyskytla tři „béčka“ vedle sebe. Prázdné místo napravo může být doplněné jakkoliv.

Ozve se divné plácnutí a já uvidím, že na zem spadla nějaká věc. No ne! To je bageta, kterou jsem měl na koleji! Jak se tady asi vzala?

Odpověď přijde vzápětí. Z rohu naproti místu, kde sedím, přijde záblesk a do cely se vkutálí Jirka. Další záblesk a vedle něj přistane Filip. Mám tu zachránce!

„Já jsem měl tušení, že to tvoje těžítko byl nějaký teleportér,“ řekne Filip, „ale nevěřil jsem tomu, že by se Nápověda dostal technicky takhle daleko. Když jsi zmizel, tak ten teleportér zůstal na tvém stole. Rychle jsem ho rozebral a trochu zbastlil, aby dokázal přenášet lidi do tvé blízkosti. Pak jsem poslal bagetu, abych si ověřil, že to funguje.“

„Ale jak se dostaneme zpátky?“ zajímá mě. Jirka z kapsy vytáhne předmět o velikosti těžítka, podobný tomu mému. „Naštěstí byl ve věcech z bunkru ještě jeden teleportér. Vezme nás zpátky do Prahy na koleje. Ale není čas na nějaké řeči, hned musíme pryč!“ Jirka natáhne ruku, aby byl teleportér mezi námi, a chce ho spustit, když vtom se otevřou dveře a v nich stojí Nápověda. V ruce drží povědomou krabičku a já znovu cítím, jak mám ztuhlé a nehybné nohy. Jirkovi vypadne teleportér z ruky a spadne na zem. Nestihli jsme to!

„Vida, další návštěva z Prahy,“ řekne. „Moc díky za vyřešení úlohy,“ obrátí se na mě. „To je poslední věc, která ještě byla potřeba pro dokončení antihmotové bomby. Určitě víš, co se stane, když se srazí hmota s antihmotou – uvolní všechnu svoji energii.“

Nápověda si všimne teleportéru, který Jirkovi spadl na zem. „Výborně, tímhle jste se chtěli dostat domů? Technologie na výrobu teleportérů se vyrábí dost těžko a jen tak bych si ji tu neobstaral… ale vy jste mi o mnoho ulehčili práci.“

Za Nápovědou se objeví člověk poměrně malého vzrůstu, není mu moc v tom šeru pořádně vidět do tváře. Předá Nápovědovi podivný, kulatý předmět. „Co asi bude dělat tahle krabička?“ ptám se.

„Tahle krabička dokáže vyhodit do vzduchu pár budov v centru města. Nic moc? Tak ji zvětšíme na dvojnásobek a už dokáže srovnat se zemí celou městskou čtvrť. Další pokračování si jistě dokážete představit. A když už tady máte ten zbastlený teleportér, rovnou tu bombu pošlu přes něj. Bude to taková malá zkouška.“

To je konec, dívám se na Jirku. Co by nám teď mohlo pomoci?

Temnotu místnosti přeruší záblesk. Z něj se prudce vyřítí další člověk. To je Janka! Jak nemůže zastavit, porazí Nápovědu na zem. Zmateně na nás zamžourá.

„Na stole ste mali také divné…“

„Nemusíš nic vysvětlovat,“ přeruší ji Jirka. Jak Nápověda spadl, muselo se mu něco stát se zmrazovačem. Už se zase můžeme hýbat. Na nic nečekám a chňapnu po teleportéru, který byl až dosud v držení pana Nápovědy. Předám ho Jirkovi, ten zakřičí: „Vezměte se za ruce!“ Všímám si, že bomba, která taky vypadla padouchovi z rukou, začala slabě zářit a bzučet. Ale to už Jirka zapnul teleportér a mizíme pryč, do bezpečí!

* * *

Nedaleko Tokia došlo k podzemnímu výbuchu, japonská armáda tvrdí, že o ničem neví, čtu na displeji telefonu. Oblast prý byla uzavřena a je pod přísnou ochranou, některým novinářům se ale přece jenom podařilo proniknout dovnitř a nafotit zbytky něčeho, co vypadá jako tajná základna.


Teoretická úloha30-3-6 Střežení oblasti (11 bodů)


Japonská policie se snaží zamezit vstupu do ohraničené oblasti, kde se vyskytovala základna. Má ale málo personálu, a tak chce posílat své lidi jen na ty části hranice, kam zrovna vyjeli zvědaví novináři. To se navíc může v čase měnit.

Představte si hranici jako nekonečnou přímku s počátkem, jakýkoliv bod na přímce lze jednoznačně určit podle vzdálenosti od počátku (ta je kladná, pokud je bod napravo od počátku, nebo záporná, pokud je nalevo). Na tuto hranici posíláme hlídkovat stráž. Jejich velitel po sobě zadává N instrukcí, každá buď „hlídejte hranici mezi body AB“, nebo „přestaňte hlídat hranici mezi body AB“. A je vždy menší než B (tj. bod určující A je vždy nalevo od B). Na začátku se nehlídá žádná část hranice.

Může se stát, že kvůli první instrukci se sloučí dva nebo víc hlídaných úseků do jediného dlouhého úseku, naopak druhá instrukce může rozdělit jeden souvislý úsek do menších úseků. Také lze nařídit hlídání oblasti, která už (třeba jen zčásti) hlídaná je, nebo zastavit hlídání oblasti, která (třeba jen zčásti) hlídaná není.

Chceme, abyste po každé instrukci odpověděli, kolik je souvislých oblastí, které jsou střežené.

Například můžete dostat následující řadu instrukcí. Vpravo od instrukce se nachází počet souvisle střežených oblastí po provedení instrukce.

Hlídejte [0,1] 1
Hlídejte [2,4] 2
Hlídejte [1,3] 1
Hlídejte [10,20] 2
Přestaňte hlídat [15,16] 3

Tohle dobrodružství mi zabralo skoro celou noc. Cítím se jako zombík a podobně asi vypadám, ale je dost možné, že jsme Nápovědu konečně zničili. Za chvíli mi začíná ta zkouška, na kterou jsem se učil, tak uvidíme, jaký bude výsledek. Nemá někdo po ruce bagetu?

Kuba Maroušek


Seriálová úloha30-3-7 Pokračování seriálu (15 bodů)


Pokračování seriálu připravujeme a co nejdříve ho zveřejníme.