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

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

Zadání úloh

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

Vánoce jsou tady

Dnes sáhneme do trochu jiného soudku. Po dvou vydařených reportážích jsme se rozhodli zařadit trochu oddychovější téma. O pár řádků níže se můžete zakousnout do krátké sci-fi povídky s nádechem cyberpunku, kterou pro vás připravil Martin „Bobřík“ Kruliš. Měli jste někdy sen, který vypadal jako skutečný? Co když to není jen zdání a sen začne žít vlastním životem …?

„Zase jsem měl ten sen.“

„Opravdu? A který?“ pozvedl doktor obočí a dál čmáral cosi do svého poznámkového bloku. Sám nevím, jestli je to vlastnost všech psychologů, nebo zda to dělá jen ten můj, ale občas mám pocit, že vám vůbec nevěnují pozornost a snaží se jen udržovat konverzaci hloupými dotazy.

„Ten o těch lidech,“ řekl jsem unaveně. „Vyspělá civilizace, utopická společnost a tak dále. Už ani nevím, kdy se mi naposledy zdálo něco jiného.“

„A zdá se vám pokaždé to samé, nebo pozorujete drobné rozdíly?“ zeptal se s dobře hraným výrazem neutuchajícího zájmu.

„Je to pokaždé …trochu jiné. Skoro jako seriál – každý sen je o něčem novém, ale zároveň stále o tom samém …“

Opět mi neřekl nic převratného. Stále ty samé řeči o přepracování a stresu. Nemyslím, že by to byl zrovna můj případ. Jmenuji se Harold a tohle je můj život. Pracuji na pozici řadového úředníka v účetní firmě. Procházím formuláře a počítám nejrůznější statistiky. Můj život je klidný a předvídatelný. Největší vzrušení jsem zažil, když kolega z kanceláře ztratil sešívačku a celá směna úředníků mu ji pomáhala hledat. Takže jak jsem říkal – s tím stresem se doktor trochu netrefil.

Po návštěvě ordinace mě čekala práce. Celý den proběhl poklidně – ostatně jako každý jiný den. Žádné vzrušení. Žádný stres. Kancelář jsem opustil přesně v 17 hodin a zamířil do podzemky. Byla ošklivě přeplněná, ale takový už je život. Stálo mě to zpoždění dlouhé přesně tři minuty a čtyřicet pět vteřin.

Doma následovala obvyklá večerní rutina. Nakrmit rybičky, večeře a televizní zprávy na kanálu 6. Dělám to tak každý den. Do postele jsem ulehl s rozečtenou knihou a pomalu se ukolébal čtením.

Pohled na město byl nádherný. Táhlo se od obzoru k obzoru a stříbrně lesklé výškové budovy šplhaly k nebi. Každý den vyrostla alespoň jedna nová. A mezi nimi na různých letových hladinách proplouvala vznášedla. Úchvatný pohled, a přitom nic neobvyklého. Běžná denní doprava. Lidé jedou do práce, děti do školy …

V jedné nevýznamné budově na okraji města uvnitř velikého sálu mezitím pobíhali lidé v bílých pláštích a křičeli na sebe nesrozumitelné věci. Podobali se mravencům, kterým právě někdo šlápl do mraveniště. Shlukovali se do skupinek a vášnivě debatovali. Co chvíli se zase rozprchli do všech směrů a vytvořili nové skupinky. Hluk sílil a s ním i zoufalství pobíhajících lidí.

Místnost prořízl ostrý pískavý zvuk. Všichni jako na povel utichli a obrátili se k řečnickému pultu, ke kterému právě z davu vystoupil postarší muž s plnovousem. Opatrně přejel ostatní nervózním pohledem a napjatou atmosféru ještě vylepšil váhavým odkašláním.

„Vážení kolegové,“ začal rozechvělým hlasem, „není o tom již nejmenších pochyb. Všechny naše hypotézy se potvrdily sérií nezávislých experimentů, a tak zbývá jediné rozumné vysvětlení …“ Na chvíli se odmlčel, aby si osušil pot z čela, a pak pokračoval: „Žijeme ve snu! Celá naše civilizace byla vytvořena snem někoho jiného! Navíc nejsme schopni určit, kdy tento sen –“

Probudil jsem se. Byly čtyři hodiny ráno a na okno tiše bubnoval déšť. Poslední útržky snu pomalu zahaloval mrak zapomnění. Oči se prodíraly tmou a postupně rozeznávaly obrysy nábytku mého pokoje. Posadil jsem se na posteli a snažil se uklidnit. Nešlo to. Uběhla skoro hodina a já stále nehybně seděl. Hlavou se mi honily nejrůznější myšlenky a paměť se snažila sen uspořádat. Únava mě přemáhala, ale strach mě držel vzhůru. Nakonec mě ukolébal déšť a já spal až do rána.

Budík zazvonil ve čtvrt na osm. Z rozespalosti mě probudila až studená sprcha společně s teplou kávou a dvěma croissanty. Začetl jsem se do ranních novin. Titulní stranu opět zdobil článek o nějakém vědeckém objevu. Oči byly zaměstnány čtením, ale mou mysl ovládaly vzpomínky na muže v bílých pláštích, na jejich experimenty a teorie …Z rozjímání mě probral pohled na hodiny. K čertu, prolétlo mi hlavou. Následovalo ještě mnoho slov. Nepěkných slov.

Do práce jsem dorazil s velkým zpožděním. Stálo mě to napomenutí nadřízeného a ostudu před všemi kolegy. První zameškání po tolika letech. Bohužel to nebyl jediný problém, který mě čekal. Má mysl se potulovala kdesi daleko. Soustředit se bylo extrémně těžké a práce mi nešla od ruky. V poledne mě můj nadřízený poslal domů, protože jsem za celé dopoledne nevyplnil jediný formulář správně.

Doma ale také nebylo k vydržení. Chodil jsem nervózně po svém bytě sem a tam. Únava mne pronásledovala a já se jí snažil unikat. Nakonec mě ale přece jen přemohla. Krátký spánek během dne nemůže uškodit. Natáhl jsem se oblečený na postel a opatrně zavřel oči. Jen krátké zdřímnutí. Jen tak krátké, aby se mi nic nemohlo zdát …

Pohled na město byl nádherný. Právě zapadalo slunce a jeho odraz se zrcadlil na lesklém povrchu budov. Vzduch se lehce tetelil a podtrhával tak atmosféru letního večera.

„Máme to! Máme to!“ ozvalo se odkudsi. V malé pracovně jedné bezvýznamné budovy na kraji města se rozlétly dveře. Do nich se vřítila postava mladého muže v brýlích a bílém plášti, který nad hlavou vítězoslavně mával štosem papírů.

„Máme co?“ podíval se na něj postarší muž, kterému očividně ona pracovna patřila.

„Přišli jsme na to, jak modifikovat memgramy! Tím můžeme posílat informace přímo do mozku našeho Spáče!“

Zzzzzz

21-3-1 Kódování memgramů (9 bodů)

Memgram, tedy záznam nesoucí jednu myšlenku, si můžeme představit jako mřížku obsahující 8 ×8 polí. Každé pole může nabývat dvou hodnot – 0 a 1. Vědci se snaží memgramy modifikovat, aby pomocí nich mohli přenášet své informace. Otázka je, kolik informace můžou zakódovat do jednoho memgramu.

Posílání informace probíhá tak, že vědci dostanou memgram, který nese (z jejich pohledu) náhodnou informaci – tj. nelze dělat žádné předpoklady o tom, kde jsou jedničky a kde nuly. Tomuto memgramu můžou – ba co víc, dokonce musí – změnit jeden bit (jednu jedničku překlopí na nulu nebo obráceně). Mřížka se nesmí otáčet, tzn. políčka jsou jasně a jednoznačně očíslována.

Příjemce (mozek Spáče) pak dostane upravený memgram. Přitom ale neví, jak vypadal původní memgram, tedy ani který bit byl změněn. Protože nás zajímá maximální velikost přenášené informace, předpokládejte, že mozek umí informaci rozkódovat, ať je jakkoli zakódovaná (zná komunikační protokol).

Pro lepší představu si uveďme triviální příklad, na kterém si ukážeme, jak přenést jeden bit. Řekněme, že hodnota tohoto bitu se bude přenášet na pozici (1,1) a všechna ostatní políčka budou pro příjemce nepodstatná. Když přijde memgram, podíváme se na naši pozici. Buď tam přímo dostaneme hodnotu, kterou chceme přenést, a pak změníme libovolný jiný bit (vždy musíme něco změnit, tak sáhneme jinam, abychom si políčko (1,1) nerozbili). Pokud tam je opačná hodnota, změníme políčko (1,1) a tím ho nastavíme správně. Příjemci pak stačí přečíst toto políčko, aby získal posílanou informaci.

Vašim úkolem je určit, kolik nejvíce bitů informace lze takto přenést v jednom memgramu, a popsat, jak bude tato informace kódována.

Pokud úlohu vyřešíte i obecně pro memgram obsahující libovolný počet (N) bitů, případně pokud dokážete, že vaše řešení je nejlepší možné, bonusové body vás jistě neminou.

„To vypadá zajímavě,“ pokýval hlavou starší muž, když pročítal papíry mladšího kolegy. „A za jak dlouho může být zařízení připravené?“

„Když budeme všichni pracovat jen na tomto projektu, mohli bychom to stihnout už za pár dní.“

„Hmm, to není špatné. Ale pomyslel jste, pane kolego, na možnost, že se mezitím Spáč probudí?“

Probudil jsem se a posadil na posteli. Bylo pozdní odpoledne a venku se začínalo stmívat. Tyhle sny začínají být čím dál realističtější. A také děsivější. Musím přijít na jiné myšlenky! Krátká procházka by mi mohla vyčistit hlavu. Oblékl jsem se a vyrazil.

V parku se pohybovali nejrůznější lidé. Bylo to ideální místo na odpočinek, přestože o sobě dával podzim vědět vtíravým chladem a všudypřítomným zažloutlým listím. Posadil jsem se na lavičku, pohodlně se opřel. Večerní vánek mi lehce foukal do tváře. Bylo to příjemně osvěžující.

Kolem prošel muž v bílém plášti. Snažil jsem se mu nevěnovat pozornost. Každý přece může nosit bílý plášť! V opačném směru prošla dvojice lidí. Také v bílých pláštích. Vášnivě diskutovali nad nějakými dokumenty. Nedaleko se zastavila žena ve středních letech. Byla zahalená do bílého pláště a venčila malého bílého psa. Vypadal roztomile, ale něco na něm nebylo v pořádku. Bližší pohled odhalil, že pes není bílý. Byl oblečený do bílého oblečku, který nápadně připomínal plášť. Kdo může obléknout psa do něčeho takového?!

Mám snad vidiny, nebo se ti lidé okolo zbláznili? Vydal jsem se směrem domů a snažil se příliš nerozhlížet po lidech. Přepracování, stres, to bude určitě ono! Nic jiného to nemůže být.

Teplá sprcha, několik prášků na spaní a rychle do postele. Prostě se z toho vyspím a bude to! Už žádné sny o bílých pláštích. Usilovně jsem se snažil myslet na jiné věci a prášky pomalu zabraly …

Na rozlehlé, sytě zelené louce se pásly ovce. Uprostřed nich seděl bača a hrál na vlastnoručně vyřezanou píšťalku. Ovce klidně přežvykovaly trávu a sem tam se ozvalo zabečení. Bača odložil píšťalku a odkudsi vytáhl dížku na mléko. Sedl si na stoličku vedle nejbližší ovce a začal ji dojit.

Něco nebylo v pořádku. Ovce znervózněly a začaly pobíhat sem a tam. Hustá bílá vlna na nich poskakovala a vlála. Jako by v ní byly jen oblečené a mohly ji kdykoli shodit. Tráva se podivně leskla a její zelená barva vybledla a změnila se na stříbrnou. Jednotlivá stébla se přestala kývat ve větru a stála vzpřímeně kolmo k nebi jako výškové budovy. Ovce si stouply na zadní. Stále pobíhaly kolem a vášnivě spolu diskutovaly bečivými hlasy. Už na sobě neměly vlnu – byly to bílé pláště! Bača zmizel neznámo kam a z louky se stala obrovská prosvětlená místnost …

Jedna ovce – vědec se přitočil k jinému a do všeobecného hluku téměř zakřičel: „Už to můžeme spustit?!“

„Téměř! Právě provádíme kalibraci!“ odpověděl mu rovněž křikem druhý vědec.

Uprostřed místnosti stál přístroj, který vypadal jako jaderný reaktor zkřížený s obřím kávovarem. Okolo pobíhala hromada vědců v bílých pláštích, kteří usilovně pracovali na různých částech přístroje. Trvalo notnou chvíli, než dokončili všechny drobnosti.

„Jsme připraveni!“ zamával jeden vědec z vrcholu přístroje na kolegu u ovládacího pultu. Ten mu zamával nazpět a pomalu zatáhl za velkou páku. Navzdory všem předpokladům přístroj nezačal ani hučet, ani blikat, jen malá kontrolka signalizovala, že byl uveden do provozu. Vědci z celé místnosti se shromáždili u informační obrazovky, kde s napětím čekali na první výsledky. Číselné ukazatele se pohnuly a začaly stoupat. Ozvalo se hromadné oddechnutí a celý dav začal optimisticky švitořit.

„Výborně! A teď uložíme náš svět do dlouhodobé paměti Spáče,“ zavelel nejstarší vědec. Ostatní se rozprchli po nejbližším okolí a začali opět pilně pracovat.

Řešení

21-3-2 Nadposloupnost (10 bodů)

Vědci se snaží uložit informace o jejich světě do paměti Spáče. Problém je, že v paměti už některé věci jsou a žádné nesmí zmizet – to by mohlo mít nedozírné následky.

Paměť si představte jako uspořádanou posloupnost vzpomínek. Jednu vzpomínku budeme pro jednoduchost brát jako řetězec. Zároveň je dána posloupnost vzpomínek, které by vědci rádi do paměti uložili. Některé vzpomínky se můžou překrývat s těmi, které už v paměti jsou.

Cílem je najít nadposloupnost takovou, aby původní paměť i nové vzpomínky představovaly podposloupnosti této nadposloupnosti. Vzhledem k tomu, že paměť není svou kapacitou neomezená, měla by být nadposloupnost nejkratší možná, aby se minimalizovalo riziko zapomínání.

Příklad: V paměti je „snídaně“, „práce“ a „večeře“. Vědci chtějí přidat „večeře“, „sen“ a „snídaně“. Jeden z možných výsledků je „snídaně“, „práce“, „večeře“, „sen“ a „snídaně“. Vyškrtnutím snu a druhé snídaně dostaneme původní paměť a vyškrtnutím první snídaně a práce dostaneme posloupnost, kterou by rádi vědci do paměti dostali.

Probudilo mě drnčení budíku. Musel jsem spát opravdu tvrdě, protože zvonil už několik minut v kuse. Hlava byla čistá a celým tělem mi pulzovala energie. Byl to nádherný pocit. Stačilo pár minut, abych se osprchoval, nasnídal a vyrazil do kanceláře.

Práce mi šla od ruky. Formuláře, které se mi nahromadily za včerejšek, zmizely ještě před dopolední poradou a chvíli po poledni jsem měl splněné všechny povinnosti na dnešní den.

„Dobrá práce, Harolde!“ pochválil mě nadřízený přede všemi kolegy. „Vidím, že jsi překonal tu včerejší krizi.“

„Potřeboval jsem se z toho jen pořádně vyspat,“ odpověděl jsem ledabyle a přibral si další formuláře navíc od svých kolegů.

Práce mě úplně pohltila. Čas ubíhal a kancelář se postupně vyprazdňovala. Vyrušil mě až vrátný, když kontroloval, zda v budově nikdo nezbyl. To byl ale produktivní den! Musel jsem udělat práci nejméně za pět lidí! Cesta domů byla klidnější než obvykle. Podzemka byla poloprázdná. Aby také ne, v tuhle dobu.

Čekal mne pravidelný večerní rituál. Nakrmit rybičky, večeře a večerní zprávy. Můj přesčas v práci ale způsobil, že zprávy na kanálu 6 už dávno skončily. Na obrazovce pobíhala nějaká zvířata, zatímco hlas na pozadí vyprávěl odborné pikantnosti z jejich života. Zajímavé, ale ne zas tolik. Vypnul jsem televizi a šel si číst do postele.

Pohled na město byl nádherný. Vycházelo slunce a společně s ním se probouzeli lidé. Proudy vznášedel houstly a město pomalu ožívalo. Do jedné už ne tak bezvýznamné budovy na kraji města se sbíhali vědci. Přednáška na téma Snových světů se bude konat od devíti hodin ve Velké aule, informovaly všudypřítomné plakáty.

Aula se plnila a s přibývajícím množstvím lidí se zvyšoval i hluk. Šepot se brzy změnil v křik a v místnosti nebylo slyšet vlastního slova. K řečnickému pultu vystoupil starší muž s plnovousem. Chvíli počkal, než hluk v sále utichl na přijatelnou úroveň, a začal přednášet.

Mluvil dlouze o nejrůznějších věcech. Jak je možné žít ve snu a jaké filozofické problémy jsou s tím spojené. Kolik takových snových světů může existovat, jak jsou propojené a zda se dá mezi nimi cestovat. Zda mohou existovat snové světy vytvořené snem osoby, která je rovněž uvězněna ve snu. Jak mohou snové světy ovlivňovat reálné světy a naopak. A na závěr upozornil posluchače na vážný problém.

 „Jak jistě všichni víte, jsme uvězněni v mysli Spáče. Spuštěním přístroje na úpravu memgramů se nám podařilo zafixovat naši existenci přímo v jeho paměti a podvědomí, takže nehrozí, že by na nás v blízké době zapomněl. Ale stále tu existuje jeden problém …“ Přednášející se na chvíli odmlčel, prohrábl si plnovous a promítl další holografický obrázek. „Co když našeho spáče potká řekněme malá mozková příhoda? Co když ho zítra přejede cestou do práce auto? A i kdybychom měli štěstí a nic z toho se nestalo, spáč je jen obyčejný člověk. Za nějakých padesát, možná šedesát let stejně zemře přirozenou smrtí a naše civilizace zanikne s ním.“

Poslední věta visela ve vzduchu a v aule se rozhostilo úplné ticho. Po chvíli se mezi posluchači zvedla ruka těsně následovaná i jejím majitelem. Stoupl si, rozhlédl se po okolních posluchačích a pak se rozechvělým hlasem zeptal: „A myslíte, že s tím půjde něco udělat, pane profesore?“

„Upřímně řečeno, nevím. Stále nad tím bádáme. Pravděpodobně je naší jedinou možností vytvořit tunel mezi reálným a snovým světem. Problém je, že by si to vyžádalo obrovské množství energie a také úplnou znalost topologie všech snových světů Spáče.“

Aula začala tiše šumět vzrušenými debatami. O chvíli později se z davu zvedla jiná ruka. „Myslím, pane profesore, že bych pro vás mohl vyřešit to druhé …“

Řešení

21-3-3 Topologie snů (10 bodů)

Topologie snových světů je reprezentována binárním stromem. Katedra snového inženýrství se pokusila zmapovat okolní světy, ale zatím mají k dispozici jen neúplná data.

Podařilo se jim získat tento strom vypsaný v prefixové a infixové notaci. Problém je, že pro další zpracování by velice potřebovali mít strom vypsaný také v postfixové notaci.

Napište algoritmus, který z prefixového a infixového výpisu sestaví výpis postfixový, případně oznámí, že ze zadaných dat nelze sestavit tento výpis jednoznačně.

Jednotlivé vrcholy jsou ve stromě označeny celými náhodnými čísly. Označení je navíc jednoznačné – tj. žádné dva vrcholy nemají stejné číslo.

Příklad: Pro strom s prefixovým výpisem 16 11 19 3 42 a infixovým 11 16 3 19 42 bude postfixový výpis 11 3 42 19 16.

Následujících několik dní bylo velmi zajímavých. Energie mne neopouštěla, a tak jsem strávil v práci i celý víkend. Můj plán byl našetřit nějaké přesčasy a pak si udělat dovolenou. Ale nešlo to. Mozek byl příliš aktivní a neustále potřeboval něco řešit. Každou noc se mi zdály tytéž sny o vědcích usilovně pracujících na zařízení, které by je mělo dostat ven ze snu. Začínalo mě to děsit. Opět jsem navštívil svého psychologa a převyprávěl mu své sny i to, co se se mnou v poslední době děje …

„Takže říkáte, že oni – tedy jako v tom vašem snu – něco staví?“ zeptal se už asi po čtvrté.

„Ano. Jak jsem říkal, staví nějaké zařízení, které by je mělo dostat ven ze snu.“

„Hm. Velmi zajímavé,“ pokýval doktor hlavou a zamyslel se. „Myslím, že byste je měl nechat, aby to dostavěli.“

„A nemohlo by to být – já nevím – nebezpečné?“

„Snad nemyslíte, že by to mohlo být skutečné,“ usmál se. „Ten stroj symbolizuje nějakou věc ve vašem podvědomí, která čeká, až ji vyřešíte. Pomozte jim. Mějte dobrou vůli ten stroj dostavět. Jedině tak vaše podvědomí vyřeší problém, který zřejmě máte.“

Úžasné! Psychologové mají prostě na všechno vysvětlení. Cestou do práce se mi hlavou honily nejrůznější myšlenky. Na jednu stranu mohl mít pravdu. Na druhou stranu, co když je ten sen skutečný. Nebo je také možné, že mi šplouchá na maják! V duchu jsem se zasmál té hloupé myšlence, ale veselo mi nebylo.

Večer jsem dal na radu psychologa. Od teď bude mou jedinou myšlenkou před spaním dostavět ten zatracený přístroj. Ať to stojí co to stojí.

Pohled na město byl nádherný, ale zdaleka už ne tak úchvatný. Byl to stále ten stejný pohled, který se vracel noc co noc. Budova na okraji města, ve které vědci připravovali svůj přístroj, byla stále plná a žila čilou kreativní prací. Právě řešili další problém …

„Už se nám podařilo rozmístit jednotlivé sny na různé frekvence, ale stále nemáme potřebný výkon, abychom je dokázali všechny pokrýt,“ říkal právě jeden vědec druhému.

„A co kdybychom optimalizovali hierarchii snů?“

„To by mohlo jít, ale výsledná struktura by musela mít co nejmenší průměr!“ přikývl vědec a začal počítat potřebné úpravy.

Řešení

21-3-4 Optimalizace stromu (11 bodů)

Hierarchie, do které vědci přeuspořádali jednotlivé sny, je vlastně strom. Ale už nemusí být nutně binární a také není zakořeněný. Manipulace se sny je velmi složitá, takže můžete jen jednu hranu odebrat a jednu hranu přidat. Výsledek musí být opět souvislý strom a navíc musí mít nejmenší možný průměr.

Pro upřesnění: Termínem průměr zde myslíme počet hran na cestě mezi dvěma nejvzdálenějšími vrcholy grafu (v našem případě stromu).

Před změnou Po změně

Příklad: Na obrázcích je uveden strom, který máme modifikovat. Na prvním obrázku je zvýrazněná hrana, kterou odebíráme, na druhém hrana, kterou jsme přidali. Původní strom má průměr 5, po úpravě se dostaneme na hodnotu 3.

„To by mělo stačit,“ přikývl postarší vědec, když prošel všechna čísla. „Zkontrolujte znovu všechny systémy! Zbývá necelá hodina do spuštění!“

Zařízení mělo tvar obrovského oválu. Po obvodu byly přidělány mohutné cívky, ke kterým se táhly tlusté kabely. Pobíhající vědci kontrolovali poslední detaily před prvním spuštěním. Čas pomalu ubíhal a jednotlivé týmy postupně potvrzovaly funkčnost jednotlivých systémů. Přípravy byly dokončeny a čekalo se pouze na pokyn z nejvyšších míst. Pan profesor, který celý vývoj řídil, se postavil před shromážděné vědce.

„Experiment, který nyní provedeme, je velice nebezpečný. Pokud jsme někde udělali chybu, ten, kdo projde bránou na druhou stranu, může skončit kdekoli. Třeba v nějaké noční můře, nebo ještě hůř …“ Shromáždění vědci se podívali jeden na druhého.

„Nemohu po nikom z vás chtít, aby takto riskoval svůj život,“ navázal profesor. „Proto jsem se rozhodl, že bránou projdu sám.“ Z hloučku přítomných lidí se ozvalo překvapené zalapání po dechu.

„Spusťte to!“ zavelel profesor a otočil se k zařízení. Ozvalo se hlasité cvaknutí spínaných kontaktů a hluboké bručení transformátorů. Vzduch uvnitř oválu se začal vlnit a tmavnout. Ve vzduchu byl cítit silný elektrostatický náboj. Obraz uvnitř portálu se ustálil a skupinka vědců zírala do tmavé místnosti. Uprostřed ní byla postel, ve které kdosi spal.

Profesor pomalu vykročil k oválu. Naposledy se otočil a kývl svým kolegům na pozdrav. Zhluboka se nadechl a jedním krokem prošel skrz. Obraz ložnice se zavlnil. Pak začal rychle blednout, až zmizel docela …

Probudil jsem se a posadil se. U postele stála postava. Oči pomalu přivykly šeru a rozeznaly dlouhý plášť a plnovous …

„Vzpomínáte na ty vědce z mého snu? Tak už dostavěli to zařízení.“

„Opravdu? A mělo to na vás nějaký účinek?“ zeptal se doktor.

„Myslím, že ano,“ přikývl jsem. „Každopádně se mnou dnes přišel někdo, kdo by se s vámi rád seznámil …“

Řešení

21-3-5 Rozklad na součty (10 bodů)

Hampf

V této sérii se nám praktická úloha nevešla do příběhu. Ale nebojte se, o to lépe se vám bude řešit …

Tuto úlohu odevzdávejte výhradně prostřednictvím webové aplikace CodEx. Pokud jste s řešením začali teprve v této sérii a nevíte, co je CodEx, podívejte se třeba na úlohu 21-1-2 „Optimalizace kotlů“, ve které naleznete úvodní povídání o CodExu.

Zadání:

Na standardním vstupu je zadáno číslo N (1 ≤ N ≤ 40). Vypište na standardní výstup všechny možnosti, jak toto číslo rozložit na součet celých kladných čísel. Každý rozklad musí být uveden na samostatném řádku, sčítance vyjmenovány od nejmenšího k největšímu a odděleny znaménkem „+“. Na pořadí řádků nezáleží.

Například pro N=5 je jeden ze správných výstupů následující:

  1+1+1+1+1
  1+1+1+2
  1+1+3
  1+2+2
  1+4
  2+3
  5

Řešení

21-3-6 Pan Cowmess (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.

Pan Cowmess [čtěte Koumes] si založil softwarovou firmu Zkrátil a Zrychlil, s.r.o., která se hodlá zabývat programováním nejkratších a nejrychlejších programů na světě. Pro svého prvního zákazníka napsal následující program:

        n = 0
        y = 1
cyklus: A[n] = x % 2
        n = n + 1
        x = x / 2
        if n < 32 => jump cyklus
        i = 0-1
hledej: i = i+1
        if i >= n => jump zkus
        if A[i] <> 0 => jump hledej
        j = 0-1
druhe:  j = j+1
        if j >= n => jump hledej
        if A[j] <> 1 => jump druhe
        A[i] = 2
        A[j] = 2
        jump hledej
zkus:   if A[k] = 2 => jump ok
        y = 0
ok:     k = k+1
        if k < n => jump zkus

Vám se (zcela oprávněně) nezdá, že by tento program byl obzvlášť krátký nebo rychlý. Zkuste tedy přijít na to, co Cowmessův program dělá, a zdůvodnit, proč to dělá (za 6 bodů). Pak napište daleko kratší program, který počítá totéž (za dalších 6 bodů). Tím myslíme, že váš program má pro libovolnou počáteční hodnotu registru x odpovědět stejnou hodnotou y jako původní program. Vaše řešení může být i pomalejší, hlavní je, aby mělo co nejméně instrukcí.

Řešení