Čtvrtá série třicátého druhého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Nelehká pandemická doba jara tohoto roku bohužel nepřála ani přípravě
čtvrté série, ale již se k vám předposlední číslo jubilejního 25-tého
ročníku KSPčka konečně dostává. Doufáme, že vás všechny zastihuje v co
nejlepším zdraví a doufáme, že zdraví i nadále zůstanete a uvítáte
vytržení od domácího učení další várkou zajímavých úloh.
Předchozí díl seriálu můžete odevzdávat až do konce dubna.
V této sérii namísto seriálu přibalujeme kompetitivní úlohu, kde
můžete navzájem mezi sebou poměřit schopnosti ve hledání optimálního
řešení na těžkou úlohu. Zapojit se může každý, tak toho využijte!
Mimo to série obsahuje další čtyři teoretické a jednu
praktickou úlohu. A závěrem tohoto čísla je kuchařka o minimálních kostrách.
Připomínáme, že se z každé série stále započítává 5 nejlépe
vyřešených úloh (tedy nemusíte vyřešit úplně všechny a i tak můžete dosáhnout
na plný počet bodů). Také se vám body za úlohy přepočítávají podle vašeho
služebního stáří – na přesnou definici se podívejte do pravidel na webu.
Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek.
Úspěšným řešitelem se stává ten, kdo získá za celý ročník (této kategorie) alespoň
50 % bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice
pro úspěšné řešitele je 150. Maturanti pozor, toto je poslední série,
za kterou stihneme získat body, pokud potřebujete prominutí přijímaček uplatnit
již letos (pokud tomu tak je, ozvěte se nám).
Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů,
darujeme KSP propisku, blok, placku a možná i další překvapení.
- Odměna série: Třem nejúspěšnějším řešitelům kompetitivní úlohy pošleme sladkou odměnu.
Zadání úloh
V minulé sérii unikla posádka Hefaista ze základny zasažené podivnou iontovou
bouří, aby následně zjistila, že část ztracených kolonistů pravděpodobně v rámci
tajného výzkumu iontovou bouři vytvořila a vyslala ji proti zbytkům základny s
cílem zamést stopy – tedy zbylé kolonisty a také posádku hlídkové a servisní
lodi Hefaistos, která přiletěla kolonistům na pomoc.
Po dramatickém úniku (přečtěte si minulý díl)
a po napíchnutí místní satelitní sítě se povedlo posádce a kolonistům zjistit
souřadnice utajené základny a v hlasování o pokračování jste zvolili, že se mají
pokusit přepadnout druhou tajnou základnu, protože jsme přece lepší! Tak čtěte
pokračování…
* * *
„Já říkám, zaútočme na ně! Tady jsme jak sedící kachny, hned jak opadne to
rušení z iontové bouře, tak nás uvidí,“ zahřměl přes celý můstek vždy bojovný mariňák
Drake.
„Ale tohle není žádná válečná loď,“ oponoval mu pilot, „tohle je dobrá loď
na zachycení neovladatelné lodi, průlety skrz prachové ohony komet a jinou
drsnou jízdu… ale probůh, vždyť nemáme žádné pořádné zbraně, jenom
protimeteorické dělo.“
„Kolonistů je na té základně nanejvýš devět – náklad sem sice propašovat
mohli, ale další lidi by před kolonií neskryli. Nás je více a máme pořád plný
set těžkých skafandrů do nebezpečného prostředí, ty něco vydrží. A dostatek
nářadí na to propálit se několikametrovým pancířem hvězdné lodě, do té základny
se můžeme dostat pěšky,“ pronesla po chvíli přemýšlení kapitánka Laren.
„Navrhuji přistát vedle jejich základny a…“
Hlavní inženýr McCormack kapitánku přerušil: „Podle těhle snímků tam ale mají
nějakou obrannou soustavu a pravděpodobně štítový…“
Než však stihl něco doříct, ozvalo se náhle zezadu z chodby jasné zvolání:
„Tak už to hoď, vybuchne to!“
Inženýr přejel zděšeným nechápavým pohledem po ostatních a ještě než si to stihl
uvědomit, už proskakoval průlezem z můstku do chodby vedoucí k prostorům pro
posádku.
Vběhl do místnosti, ve které se tísnila většina shromážděných kolonistů, a
pátral očima po něčem, co by mohlo vybuchnout. Výbuch na lodi ve vesmíru mohl
mít fatální následky! Pak se ale zarazil, pohlédl na kolonisty v kroužku,
rozchechtal se a svalil se smíchy na zem – kolonisté hráli pro ukrácení času
hru!
32-4-1 Výbušné koťátko (9 bodů)
Kolonisté se pro ukrácení času rozhodli zahrát si hru – jedno z dětí z kolonie
si s sebou totiž vzalo kulatou hračku v podobě koťátka, kterou si hráči hází
a koťátko vždy po náhodné době „vybuchne“ a postříká toho, kdo ho právě drží,
obarvenou vodou. Ten ze hry vypadává a ostatní hrají dál.
Bohužel tato hračka už byla stará a náhodné odpočítávadlo přestalo být náhodné.
Teď se stávalo, že koťátko vždy „vybuchne“ po stejné době, která akorát
stačí na to, aby si koťátko hodilo K hráčů.
Kolonistům to ale zjevně nevadí. N hráčů si stoupne do kroužku, nultý hráč koťátko
spustí a hodí hráči po své levici. Ten ho opět hodí hráči po své levici a to se
opakuje tak dlouho, než je koťátko hozeno K-krát – v náručí K-tého hráče
„vybuchne“ a ten tak vypadává ze hry a vystupuje z kroužku ven. Přitom ale
koťátko opět spustí a hodí ho opět hráči po své levici (a po K přehozeních
opět vybuchne).
Postupně vypadávají všichni hráči, až zbude samotný poslední hráč, který
vyhrává. My bychom chtěli vyhrát – zajímalo by nás tak, na jakou pozici se
postavit v kroužku N hráčů, když víme, že koťátko „vybuchne“ u každého
K-tého hráče. A chtěli bychom to spočítat rychleji, než to odsimulovat za NK
kroků.
Řešení
Po tomto výbušném rozptýlení se posádka spolu se ředitelem kolonie opět vydali
k plánovacímu stolu. Rychle se dohodli, že útok na cizí základnu je nezbytný.
Pokusí se s Hefaistem co nejrychleji přistát, vyslat přepadové komando v těžkých
skafandrech.
Základna měla obranný systém a nějaký set štítových emitorů. Hefaistos měl jen
protimeteorické dělo, které se ale nabíjelo na plný výkon tak dlouho, že byl čas
jen na jeden pořádný výstřel. Pilot s inženýrem připravili program, který měl
při sestupu vybrat ten nejlepší cíl a vystřelit na něj.
Dva další technici, kapitánka a oba mariňáci se mezitím navlékli do těžkých
skafandrů a připravili se u hangárového otvoru společně s nákladní plošinou
obtěžkanou plazmovými řezáky a další technikou na vyrábění děr do dveří. Zbytek
posádky se oblékl do lehčích skafandrů a i kolonisté každý dostali nouzový
skafandr, kdyby se něco stalo.
Pak se na odvrácené straně planety zažehly hlavní motory Hefaista a nasměrovaly
ho na prudkou sestupovou trajektorii. Hefaistos se roztřásl, ale držel pevně –
na tvrdé vstupy do atmosféry byl přeci dělaný. Bez varování se loď vyřítila z
noční polokoule do oslepujícího světla místního slunce, ale nic si z toho
nedělala. Senzory začaly pátrat po naprogramovaných cílech. Kolem náhle proletěl
soustředěný výboj energie, ale loď minul. Senzory teď už ale věděly, po čem se
dívat. S metodickou přesností zaměřovaly jednotlivé energetické stopy na
povrchu. Systém věděl, že má jenom jeden výstřel, a tak stále propočítával.
Kolem proletěl druhý energetický výboj, ale i ten loď na sestupové dráze minul.
32-4-2 Jeden výstřel (10 bodů)
Senzory Hefaista zaznamenaly na povrchu u cizí základny soustavu pospojovaných
energetických bodů zajišťujících obranu této základny. Body tvoří vrcholy
pomyslného grafu a spoje mezi nimi pak jeho (neorientované) hrany. Soustava bodů
nemusí být nutně souvislá, může tvořit více samostatných komponent.
Jednotlivé spoje (neboli hrany) přispívají do energetické soustavy různou silou.
Každý spoj je ohodnocený kladným číslem a při čerpání energie ze soustavy se pak
sečte energie spojů na minimální kostře zkonstruované podle těchto
ohodnocení. Pokud soustava není souvislá, tak se spočítá minimální kostra v
každé komponentě samostatně a výsledná energie je pak součet energií všech
minimálních koster.
Hefaistos má protimeteorické dělo, které ale stihne vystřelit jen jednu ránu,
kterou zvládne přerušit jeden spoj (jednu hranu v grafu). Vymyslete algoritmus,
který určí v grafu takový spoj, jehož odstraněním se co nejvíce sníží energie
celé energetické soustavy.
Například na energetické síti z levé části obrázku vychází nejlépe přerušit spoj
s ohodnocením 3, výsledné kostry s celkovou energií 11 jsou pak vyznačeny v
pravé části obrázku. Kdybychom namísto toho přerušili například spoj
s ohodnocením 4, tak si vůbec nepomůžeme a výsledná energie zkonstruované kostry
dokonce vzroste na 18.
Řešení
Protimeteorické dělo na Hefaistu se zacílilo a pak lodí lehce trhlo, když
vypustilo plazmový výboj na přesně vybrané místo energetické sítě u cizí
základny. Spoj se s oslepujícím zábleskem rozletěl do okolí, štíty základny
pohasly a Hefaistos se již obracel ke kruhovému obletu a vysouval přistávací
nohy, když se proti němu rozletěl třetí energetický výboj z děla u základny.
Tentokrát již neminul.
Proud energie proletěl pravou zadní částí Hefaista, utrhl část motorové sekce a
prošel obálkou jeho fúzního reaktoru. Nouzové pojistky a pyropatrony, které byly
hluboko do Hefaistova trupu instalovány před dlouhými lety v loděnici, v mžiku
sekundy odstřelily zbylé plátování trupu a vymrštily selhávající fúzní reaktor
co nejdál od lodi. Stihly to, na poslední chvíli. Reaktor se roztrhl až třicet
metrů od trupu. Loď obklopil proud superpřehřáté plazmy o teplotě menšího
slunce, který spaloval, co mu přišlo do cesty. Ohořelý ale stále celistvý
hlavní trup Hefaista se z ohnivé koule vynořil o sekundu později a řítil se
v kotrmelcích k povrchu.
Další z nouzových systémů odolné lodě zafungoval na výbornou a vnitřní prostory
posádky okamžitě zaplavila extrémně expanzní vysokoporézní balistická pěna,
která bleskově tuhla a chránila svůj cenný lidský náklad před nejhoršími nárazy.
Hlavní počítač se po poškození svého jádra zasekl v nějaké smyčce vypisující na
obrazovky na můstku sled chybových hlášení E3, F5, E7, G6
. Ale jeho
práci převzaly záložní počítače, jejichž jedinou starostí byla stabilizace lodi
před dopadem. Nějakým zázrakem se jim povedlo loď pomocí trysek přetočit opět do
polohy na břicho a se zbytky kdysi devítisettunové devadesátimetrové lodě
přistát klouzavým pohybem – jestli se přistáním dá nazývat prudký náraz do země
s odskočením a vyrytím třísetmetrové brázdy.
* * *
Balistická pěna uchránila posádku před nejhorším, i když asi nikdo nevyvázl bez
alespoň lehkého zranění nebo pohmoždění. Brzy se rozsvítila nouzová světla
a jednotliví lidé začali prudkými pohyby drtit pěnu, která je fixovala na jejich
místech a nyní se začala rozpadat.
Hlavní inženýr se pokoušel rychle se probojovávat rozpadající se ztuhlou pěnou,
než se dostal přes prostor osádky do hangáru, kde čekalo přepadové komando. Ti
byli naštěstí uchráněni svými těžkými skafandry a všichni vypadali v pořádku,
ale dveře se odmítaly otevřít. A to ani na manuální ovládání, i když do nich
energie očividně šla. Hlavní inženýr rychle odtrhl krycí panel a podíval se
na spálenou elektronickou destičku řídícího mechanismu. Odněkud magicky zhmotnil
páječku a dal se do nouzové opravy.
32-4-3 Sběrnice na pájivém poli (12 bodů)
Hlavní inženýr potřebuje opravit řídící destičku od mechanismu otevírání dveří.
Destičku si můžeme představit jako pájivé pole, což je většinou nějaká mřížka
R×S kontaktů, kde můžeme pomocí pájení propojovat kontakty do cestiček.
Kdo pájivé pole neznáte, vyhledejte si na internetu obrázky. Pro naše potřeby
stačí vědět, že lze na pájivém poli vytvořit cestička z „políček“ sousedících
hranou (každé políčko mimo krajních tak má 4 sousedy).
Některá políčka na řídící destičce jsou již obsazena různými součástkami. Hlavní
inženýr by ale potřeboval protáhnout po destičce od její vrchní hrany k její
spodní hraně co nejširší sběrnici. Sběrnici představuje několik cestiček,
které vedou po pájivém poli těsně vedle sebe a nikde se nerozcházejí, jak
ukazuje například následující obrázek (tečky jsou středy políček, různé
součástky představují plná políčka, tmavě je vyznačená sběrnice).
Vymyslete algoritmus, který na vstupu dostane mapu volných políček na nepájivém
poli a zjistí, jakou nejširší sběrnici (kolik cestiček vedle sebe)
můžeme po volných políčkách nepájivého pole protáhnout od jeho horního ke
spodnímu okraji. Sběrnice široká K musí začínat na K vedle sebe ležících
volných políčkách na prvním řádku a končit na K vedle sebe ležících volných
políčkách na posledním řádku.
Nezapomeňte v této úloze dokázat, že vaše řešení vždy vrátí optimální výsledek
(že nemůže existovat sběrnice s více cestičkami).
Řešení
Hlavní inženýr odložil páječku, zasunul opravenou destičku zpět do slotu
a praštil rukou do tlačítka nouzového otevírání. Těžké dveře chvíli vzdorovaly,
protože vnější obšívka trupu byla výbuchem fúzního reaktoru spečena do celistvé
skořápky, ale pak se skřípavým trhnutím hydraulické vzpěry skořápku prolomily
a do lodi se vehnalo denní světlo.
Přepadové komando příliš nečekalo a v těžkých skafandrech se okamžitě vrhlo ven.
Dva technici za sebou táhli nákladní plošinu naloženou užitečnými nástroji.
Vypadalo to, že zásah protimeteorického děla a padající trosky z Hefaista
základnu celkem poničily – na hlavní budově zapuštěné do skalního masivu
svítila zvenku jen nouzová světla a z některých míst základny se kouřilo.
Štítový generátor i všechny obranné systémy vypadaly neaktivní – otázkou ale
bylo, jak dlouho to vydrží.
V půlce cesty překvapilo komando trojici lidí v lehkých skafandrech, kteří se
pravděpodobně vydali na průzkum vraku – nenapadlo je asi, že by takový pád mohl
někdo přežít, nečekali, že loď bude tak odolná. Když zahlédli pětici mohutných
postav, z nichž dvě svíraly nějaké zbraně, tak se na místě bez odporu vzdali.
Mariňáci je jen svázali a kapitánka mezitím zavolala vysílačkou na Hefaista, aby
pro ně někdo došel. Nebyl čas se zastavovat, na základně stále někde bylo šest
bývalých obyvatel kolonie.
Po několikasetmetrovém přesunu dorazili k hlavním dveřím zasazeným do skalního
masivu. „Prořezat tohle bude trvat aspoň hodinu, možná i víc,“ zhodnotil
stav dveří jeden z techniků. Druhý technik, lodní expert na počítače Jason,
mezitím napojil přenosný terminál na datový port u panelu dveří.
„Nejsou zakódované, jenom blokují otevírací signál z tohoto panelu“, trhnul
hlavou k ovládání vedle dveří. „Můžu se pokusit poslat otevírací signál
smyčkou přes jiné panely… ale oni ten signál taky okamžitě blokují. Musím
najít nejkratší cestu zpět.“
32-4-4 Zpětný signál (10 bodů)
Pro vniknutí do základny by přepadový tým potřeboval otevřít hlavní vstupní
dveře. Signál pro jejich otevření z lokálního panelu je ale blokován, je nutné
signál poslat oklikou přes jiné počítače v síti.
Současně se ale osazenstvo základny brání a signály na otevření dveří blokují.
Potřebovali bychom tedy najít co nejrychlejší cestu sítí zpět k našemu panelu,
aby měli co nejmenší šanci ho zastavit.
Počítačová síť je tvořena jednotlivými uzly (řídící panel u vstupních dveří je
jedním z nich), které jsou spojeny jednosměrnými komunikačními linkami. Navíc
každá linka má jinou rychlost přenášení signálu, u každé komunikační linky tedy
dostaneme číslo v milisekundách, jak dlouho trvá signálu přejít přes tuto
komunikační linku do dalšího počítačového uzlu.
Naším cílem je tedy najít cestu, která začíná u našeho řídícího panelu, projde
nějakou cestou sítí po komunikačních linkách a vrátí se nazpět do našeho panelu.
Ze všech takových cest by měla být nejkratší.
Toto je praktická open-data úloha. V odevzdávátku
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 dostanete dvě čísla N a M
udávající počet počítačů v síti a počet jednosměrných komunikačních linek mezi
nimi. Na druhém řádku pak bude jedno číslo S udávající index řídícího panelu,
ze kterého chceme vyslat signál a do kterého chceme, aby se signál nakonec
vrátil. Na dalších M řádcích pak budou vždy trojice čísel a, b, x udávající,
že z počítače a existuje přímá komunikační linka do počítače b a přenést po
ní signál trvá x milisekund. Počítače indexujeme od nuly. Zaručujeme, že vstup
nebude obsahovat smyčky (tedy vždy a≠ b) a že všechna x budou kladná.
Formát výstupu: Na první řádek výstupu vypište délku (v milisekundách)
vámi nalezené nejkratší cesty vedoucí z vrcholu S zpět do vrcholu S. Na
druhý řádek vypište počet počítačů na této cestě (počítaje počáteční i koncový)
a na další řádek vypište mezerami oddělenou posloupnost indexů počítačů na této
cestě.
Ukázkový vstup:
5 8
2
0 2 2
1 0 3
1 4 1
2 1 2
2 3 3
3 4 1
4 0 1
4 2 4
Ukázkový výstup:
6
5
2 1 4 0 2
Řešení
Po Jasonově konzoli běhaly proudy písmen. Technik se pod hledím těžkého skafandru
potil, ale nakonec vítězoslavně zvedl hlavu a ťukl do potvrzovací klávesy.
Chvíli se nic nedělo, ale pak se hlavní dveře lehce zasunuly do podlahy a
odhalily vstup do přechodové komory.
Pětičlenná skupinka vstoupila dovnitř. Vnitřní dveře přechodové komory již
nebyly nijak blokované a hladce se před nimi otevřely. Ocitli se v krátké chodbě
s několika bočními místnostmi – vnitřní prostory této základny nebyly příliš
rozlehlé. Největší utěsněnou místností byl hangár spojený s dílnou, kde
zrovna pracovali na úpravě jedné z družic, a pak sekce s několika
laboratořemi, ve kterých to sršelo blesky. S utěsněným hangárem ještě sousedil
větší neutěsněný hangár, ve kterém objevili malou transportní loď, kterou
pravděpodobně vynášeli družice na oběžnou dráhu.
Na druhé straně základny pak byla obytná část a řídící centrum. Netrvalo dlouho
a mariňákům se povedlo najít všech šest zbývajících obyvatel základny. Nikdo
z nich očividně nebyl voják a podle některých nalezených papírů to celé byla
akce velké korporace, která částečně financovala i výstavbu celé kolonie.
Kapitánka Laren si v duchu oddechla – aspoň že to není nějaká tajná akce
koloniální armády.
Poté, co do základny přivedli z havarovaného Hefaista všechny kolonisty, se
ředitel kolonie přišel podívat na vězně.
„Taylore, jak jen jsi mohl? Co jste tu probůh dělali a proč?“ nemohl uvěřit
tomu, že člověk, jehož ještě před měsícem považoval pouze za jednoho z geologů
kolonie, kteří rádi vyráželi na dlouhé výpravy do pustiny, šéfuje nějaké skupině
vědců zahrávajících si s iontovými bouřemi.
Než však mohl pokračovat, přerušilo všechny hlasité zakvílení alarmu od hlavní
přehledové mapy. Po chvíli zkoumání a vyzvídání od zajatých vědců zjistili, že
na celé planetě se v několika uzavřených stanicích „pěstují“ iontové bouře
držené na místě a posilované magnetickými silovými paprsky. A stanice nejblíže
této základně vlivem poškození energetické sítě zkolabovala a je potřeba ji opět
nahodit.
32-4-5 Svázání bouře (13 bodů)
Iontová bouře byla držena ve své „líhni“ pomocí magnetických silových paprsků
generovaných na přímých spojnicích mezi emitory. Každý emitor zvládne generovat
i více magnetických silových paprsků, ale nikdy se žádné dva magnetické silové
paprsky nesmí křížit (podle staré zásady „Nikdy nekřižte paprsky!“ by mohlo
dojít až ke konci světa, nebo minimálně ke konci daných emitorů).
Známe souřadnice jednotlivých emitorů v rovině. Chceme naplánovat, mezi kterými
dvojicemi emitorů budeme generovat paprsky tak, aby platilo:
- Žádné dva paprsky se nekříží.
- Neexistuje žádná dvojice emitorů, mezi něž bychom ještě mohli přidat paprsek
tak, aniž by se porušila první podmínka.
Vymyslete algoritmus, který pro zadané souřadnice vydá dvojice emitorů, mezi
kterými generovat paprsky, aby byly podmínky výše splněné. Vaše řešení nemusí
obsahovat co nejvíce paprsků, ani paprsky nemusí tvořit žádný speciální tvar.
Jde jen o to, že tam již nepůjde žádný další paprsek přidat.
Řešení
Iontovou bouři se povedlo opět svázat do její „líhně“. Podle všeho byly tyto
líhně na planetě celkem čtyři a dvě z nich teď držely připravené iontové bouře
(jedna iontová bouře byla použita na prvotní poničení kolonie a druhá pak na
druhý útok na kolonii, vyrobit nové prý trvá několik měsíců).
Byli teď ale v nezáviděníhodné situaci. Na planetě byly dvě subprostorové
vysílací stanice – jedna z nich na vážně poškozeném Hefaistu bez fůzního
reaktoru zabořeném do země a druhá na hlavní základně kolonie, která byla
prakticky smetena z povrchu planety. Navíc v této malé základně nebylo dostatek
prostoru ani jídla, aby zvládla všechny kolonisty i posádku.
Před posádkou Hefaista a před kolonisty tak stálo (již poslední) náročné rozhodnutí.
Co dělat teď? Opět zahlasujte
v anketě.
* * *
Možná vám vrtá hlavou, v jaké smyčce že se to zasekl hlavní počítač Hefaista po
poškození lodě při sestupu. K vysvětlení této části příběhu se musíme vrátit
zhruba dvacet minut před zahájením útoku na cizí základnu, dokud byl Hefaistos
ještě na oběžné dráze.
V tu chvíli se dva kolonisti, shodou náhod nejmladší a nejstarší ze všech
kolonistů, rozhodli ukrátit si čekání na další vývoj situace nějakou hrou. Hra
s výbušným koťátkem je přestala bavit a tak si mladý Tom spustil na jednom
z panelů na stěně své oblíbené sudoku. A starý Azachiáš si zase chtěl zahrát
partii šachů proti lodnímu počítači.
V tu chvíli se ale objevila v sekci pro posádku kapitánka a začala vysvětlovat
detaily nadcházející akce. Tom i Azachiáš nechali hry na panelech spuštěné
a úplně na ně zapomněli.
Jenže hlavní počítač ne. V momentě jeho kritického poškození došlo k pomíchání
běžících programových bloků, přepsání paměti procesů a ke spojení programů pro
řešení sudoku a hraní šachů do jednoho. A v této smyčce hlavní počítač stále
běží, napájen z nouzových článků na Hefaistovi…
32-4-6 Sudoku s koněm (15 bodů)
Toto je optimalizační kompetitivní úloha – na problém, který vám zde ukážeme,
pravděpodobně neobjevíte optimální algoritmus, který by vám našel nejlepší možný
výsledek. Ale můžete se pokusit najít dostatečně dobrý výsledek – nejlépe
takový, který bude lepší, než výsledky všech ostatních řešitelů.
Bodovat tuto úlohu budeme tak, že nejlepší řešení dostane plný počet bodů
a ostatní dostanou body odstupňovaně podle toho, jak dobrého skóre dosáhnou. Vše
vyhodnotíme po konci série. A přidáme i nějaká referenční organizátorská řešení :)
Úloha
Pro sudoku, neboli mřížku
9×9, existuje posloupnost tahů šachovým
jezdcem, která navštíví každé políčko právě jednou (bude tak mít právě 81
kroků), nemusí se však vrátit na startovní pozici. Takové posloupnosti často
říkáme
otevřená jezdcova procházka a najít jí není tak těžké. Také je to
pouze jedna z částí naší úlohy.
Pro nějaké vyřešené sudoku a pro konkrétní procházku jezdcem definujme skóre
jako posloupnost 81 cifer v pořadí, v jakém na ně jezdec na vyřešeném sudoku
vstoupí.
Příkladem může být třeba následující sudoku s následujícím pořadím návštěv
jezdcem (začínáme na nule) a následujícím skóre:
1 2 3 8 7 4 5 6 9
8 4 5 1 9 6 7 2 3
6 7 9 2 3 5 1 4 8
2 1 4 7 5 9 8 3 6
3 9 6 4 8 1 2 7 5
7 5 8 6 2 3 9 1 4
9 6 2 3 1 8 4 5 7
4 8 1 5 6 7 3 9 2
5 3 7 9 4 2 6 8 1
80 77 50 41 52 73 70 43 12
49 40 53 78 3 42 11 72 69
76 79 2 51 74 71 44 13 10
39 48 75 54 57 4 9 68 65
30 1 58 47 8 55 66 45 14
23 38 29 56 59 46 5 64 67
0 31 24 35 28 7 60 15 18
37 22 33 26 61 20 17 6 63
32 25 36 21 34 27 62 19 16
999999988887945513787987235218365143745248661734183275716562466216243355243462171
Vaším úkolem je najít takové vyřešené sudoku, na kterém půjde najít procházku
takovou, která dá co nejvyšší skóre (když budeme skóre chápat jako číslo o 81
cifrách).
Pro řešení sudoku klidně můžete použít externí knihovny či nějaké weby, není
naším cílem zkoušet vás z napsání solveru na sudoku. Ale napište nám prosím
odkaz na použité nástroje do řešení.
Co odevzdávat
Budeme po vás chtít jednak co nejvyšší nalezené skóre (a sudoku s procházkou,
které k němu vedou), ale také slovní popis řešení říkající, jakou cestou jste k
výsledku došli. Můžete přibalit i zdroják programu či sbírku skriptů, které jste
použili.
Upozorňujeme, že bez slovního popisu a vysvětlení, jak jste k výsledku došli,
nebudeme výsledky uznávat. Pamatujte na to.
Své řešení odevzdávejte jako ZIP obsahující:
- Soubor
sudoku.txt
se zápisem sudoku ve formátu jako výše (9 řádků, čísla oddělená mezerami)
- Soubor
prochazka.txt
s procházkou ve formátu jako výše (9 řádků, čísla oddělená mezerami)
- Soubor
skore.txt
s 81-ciferným skóre získaným z procházky
- Slovní popis řešení (třeba v PDF) a případně jakékoliv další použité programy.
U prvních tří souborů se prosím pokoušejte držet zadaného formátu, velmi nám to
usnadní kontrolu. Děkujeme.
Řešení
Čtvrtý díl příběhu pro vás sepsal
Jirka Setnička