Druhá série devatenáctého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
- Termín série: 11. prosinec 2006
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
Zadání úloh
- 19-2-1: Čokoláda podruhé
- 19-2-2: Kvalitní hesla
- 19-2-3: Moneymaker
- 19-2-4: Optimální formace
- 19-2-5: Hluboký les
- 19-2-6: Prolog
Kapitola 2
Ve dveřích stála má nová klientka a dvě nadřený gorily. Něžně ji hodily na podlahu vedle mě a zazubily se. Teda, ony se moc nezubily, protože neměly čím. A hned jsem pochopil důvod – obě v ruce třímaly tabulku čokolády. V tom mě osvítil nápad hodný mého génia.
„Čo ťak blbě čumíš?“ zeptal se mě ten kolozubější.
„Koukám se, co držíš v ruce, a tak mi napadá, to jíte tu čokoládu jen tak?
Vy nevíte, co legrace se s ní dá užít, než jí sníte?“
Tázavé přiblblé kukuče mi prozradily, že netuší, a tak jsem začal s výkladem pravidel:
19-2-1 Čokoláda podruhé (6 bodů)
Typická gangsterská čokoláda vypadá jako obdélník o rozměrech M×N dílků, kde alespoň jeden rozměr je sudý. Dva hráči se střídají v lámání tak, že si ten, kdo je na tahu, vybere nějakou celistvou část čokolády a rozlomí jí na dvě části. Gangster, který odlomí dílek 1×1, prohrál. Vaším úkolem je najít takovou strategii, aby začínající mafián vždy vyhrál.
Příklad: Pro čokoládu o rozměrech 2×3 musí první zloduch lámat na dvě části 1×3, načež druhý zloduch prohrává, protože ať láme, jak láme, vždy získá dílky 1×1, 1×2 a 1×3.
Pozn.: Protože čokolády o rozměrech 1×1 a 1×2 neposkytovaly gangsterům dostatečné mlsavé uspokojení, upustily nelegální čokoládovny od jejich výroby, takže je zanedbejte.
Dveře se zabouchly a my slyšeli jen křupání tabulek čokolád, skřípání zubů a po chvíli …„Ty podvodníku!“
„Čože? Já hlaju naplošto a školo češtně.“
A pak třeskly dva výstřely, ozvaly se dvě tupé rány a já jsem velmi odvážně vykoukl dírkou ve dveřích.
„Je po nich, jsme volní!!!“ zajásal jsem.
„A jak se dostaneme ven, Einsteine?“ zpražila mě pohledem.
Faktem je, že na tento způsob jednání jsem byl od žen, zvláště tak krásných jako ona, zvyklý.
Nechtěl jsem se ale nechat zahanbit, a tak jsem začal usilovně přemýšlet. Po patnácti minutách
mého přemýšlení konečně na něco přišla, zvedla se, chvíli něco šťourala v takové krabičce s dráty
na dveřích a najednou se dveře otevřely.
Když jsem po letech zjistil, jak je to snadné, tak jsem se divil, že jsem na to nepřišel sám.
19-2-2 Kvalitní hesla (6 bodů)
Původní obsah následující pasáže jsme museli vystřihnout na nátlak rodiny [CENSORED], která popisovaný systém stále používá. A tak vás tato rodina požádala alespoň o pomoc při rozpoznávání hesel, na která je policejní program krátký. Heslo je, jak známo, posloupnost alfanumerických znaků délky N. Díky znalosti algoritmu, který policejní počítač používá, se nám povedlo zjistit, jak „kvalitu“ hesla spočítat – heslo je tím lepší, čím větší jeho část se v něm opakuje.
Vaším úkolem je po zadání hesla najít maximální d a různé indexy i a j takové, aby se souvislé podúseky délky d začínající na těchto indexech shodovaly. Podúseky se mohou překrývat. Pokud těchto dvojic s maximálním d existuje několik, tak stačí najít jednu z nich.
Příklad: Pro N=13 a heslo abrakadabraka jsou hledané indexy 1 a 8 (abraka) a délka je 6.
Pro N=7 a heslo aaaaaaa jsou hledané indexy 1 a 2 a délka je opět 6.
Bonus: Pokud bude váš program pracovat opravdu rychle, dostanete až 5 bonusových bodů.
Dveře se otevřely a my začali prchat. Teda, já sem začal prchat. Ona stála ve dveřích a rozhlížela se.
„Na co čekáš? Mizíme!“
„Ne, nejdřív musíme do jeho kanceláře, ukradneme vše, co se týká jeho práce!“
„Já si nemysl… ženská pitomá, kam zase běžíš?“
Za chvilku jsme dorazili ke dveřím. Sice byly zamčené, ale má nová průvodkyně se ukázala být nejen šarmantní, ale i velmi zručná. Práce se sponkou jí trvala jen několik vteřin.
Když jsme vešli, okamžitě se vrhla k šuplatům a začala se přehrabovat ve stole. Poté stejně sebevědomě zplundrovala trezor (kde jen vzala heslo?). Jen jsem tupě zíral a jediné, na co jsem se zmohl, byla otázka.
„Tak málo papírů? Vždyť je skoro prázdnej. To mu určitě všechno dělaj jeho účetní.“
„Blázníš? K těmhle věcem nikoho nepouští, všechno si dělá sám.“
„Tomu nevěřím, já dřu od rána do večera, popíšu stohy papírů a div nebydlím pod mostem.“
„No jo, ale ty nemáš program, který ti naplánuje činnosti tak, že málo děláš a hodně vyděláš.“
Vám je už určitě jasné, že takový program máte napsat.
19-2-3 Moneymaker (10 bodů)
Na vstupu dostane váš program číslo N, což je počet úkolů ke zpracování. Zpracování každé úlohy zabere jednotkový čas. Dále pak N řádků, každý se dvěma čísly. První číslo znamená, dokdy je třeba úkol vykonat, a druhé číslo je odměna, kterou za splněný úkol dostaneme. V jednom čase mohu pracovat právě na jednom úkolu. Výstupem programu by pak mělo být takové pořadí úkolů, aby zisk byl maximální. Pokud je takových pořadí více, stačí libovolné z nich.
Příklad: Pro N=4 a záznamy
| 3 | 1 |
| 1 | 3 |
| 2 | 5 |
| 2 | 4 |
je optimální pořadí 3, 4 a 1.
Pobrali jsme rychle vše, co se dalo, a vyběhli ven z budovy. Po cestě jsme zneškodnili několikery spící stráže, až na jednoho. Ten bohužel zburcoval všechny ostatní a ti zaujali obrannou formaci. To nám útěk značně zkomplikovalo a jedinou naší nadějí bylo to, že jsme věděli, jak taková formace vzniká. Ale jak taková obranná formace vypadá? To už jsme nevěděli. S tím nám budete muset poradit vy.
19-2-4 Optimální formace (11 bodů)
Formace je tvořena N střelci. Střelec číslo i má dostřel ai. Střelci stojí ve vrcholech konvexního N-úhelníku (konvexní N-úhelník je takový, že všechny jeho vnitřní úhly jsou v intervalu (0°,180°)) v takovém pořadí, v jakém jsou zapsáni na vstupu. Cílem je vytvořit takovou formaci, aby každý střelec dostřelil k následujícímu a aby obvod N-úhelníku byl maximální. Program by měl libovolnou jednu takovou formaci nalézt a vypsat souřadnice jednotlivých střelců.
Příklad: Pro N=5 a dostřely střelců (2.5, 2.5, 3, 5, 2) leží jeden z možných N-úhelníků na souřadnicích [0, 0], [0, 2.5], [-2, 4], [-5, 4], [-2, 0]. Pro N=4 a dostřely (10, 2, 3) nelze N-úhelník sestrojit.
Naštěstí se nám díky znalosti přesného tvaru formace podařilo najít slabinu v jejich obraně, a tak se nám povedlo uprchnout.
Pozn. KSP: Přesprstovi zjevně nedošlo, že popis formace neurčuje jednoznačně její tvar. Záhadou zůstává to, že právě vaše odpověď byla ta správná.
Celí zadýchaní jsme doběhli do hlubokého lesa.
„Co si teď počneme? Kam půjdeme? On si nás najde všude
a příště už takové štěstí mít nebudeme!“ ptala se zděšeným hlasem moje společnice.
„Znám křišťálovou studánku, kde nejhlubší je les …“
„Co to meleš za nesmysly?“
„Já jsem to řekl nahlas? Já jako myslel, že poblíž tý studánky je
opuštěná chalupa, kde bychom se mohli aspoň na noc schovat.“
„A jak jí asi najdeme?“
„No jednoduše, prostě najdeme dva stromy v lese,
které jsou u sebe nejblíže ze všech, a tam je les zákonitě nejhlubší.“
„No jo, to mě vlastně nenapadlo …“
19-2-5 Hluboký les (13 bodů)
A zatímco si Přesprst vychutnavá svůj malý triumf, napište program, který takové stromy najde. Váš program dostane na vstupu číslo N a dále N řádků s reálnými souřadnicemi jednotlivých stromů v lese. V případě, že je takových dvojic stromů víc, stačí vypsat libovolnou z nich.
Příklad: Pro N=4 a stromy
| 1 | 3 |
| 2 | 1 |
| 3 | 1 |
| 4 | 3 |
by měl program vypsat: Stromy 2 a 3 jsou si k sobě nejblíže.
Po hodinách prodírání se lesem nás sama Prozřetelnost přivedla před práh chaty. Unaveně jsme padli do postele a tvrdě usnuli. Spal jsem snad dva dny, než jsem konečně dokázal otevřít víčka a rozhlédnout se kolem sebe. A v tom mi došlo, že to, co nás do té chaty přivedlo, rozhodně nebyla Prozřetelnost.
To be continued…
19-2-6 Prolog (12 bodů)
Milí programátoři v Prologu,
jsme rádi, že se vám první díl seriálu o programovacím jazyku Prolog líbil, a přinášíme vám další zajímavosti ze světa logického programování :o)
Termy
Základní jednotkou programovacího jazyka Prolog je term. Termy se v Prologu dělí na jednoduché (atomy, čísla, proměnné) a na struktury. Atomy, čísla a proměnné už znáte. Struktura je rekurzivní, složený term, tedy součástí struktury mohou být další termy. Příklady struktur jsou:
Ve skutečnosti je strukturou dokonce i klauzule
:- je totiž binární predikát, který má dva argumenty: hlavu a tělo
klauzule, a píše se doprostřed, tedy infixově. Klidně byste mohli
psát
Unifikace pořádně a naposled
Po zadání dotazu, například
začne Prolog procházet program shora dolů a snaží se najít, „přiřadit“, neboli unifikovat zadaný dotaz s hlavou nějaké klauzule v programu. Jinými slovy prostě najít jaksi odpovídající řádek programu. Jak ale přesně funguje unifikace, když jsme teď zjistili, že úplně všechno v Prologu je term a ty můžou být pěkně složité? K naší radosti to funguje přesně tak, jak byste čekali a jak byste to dělali intuitivně:
Jestliže jeden z termů je (nezunifikovaná, volná) proměnná a druhý libovolný term (různý od proměnné, například nějaká struktura, atom nebo číslo), okamžitě se do proměnné dosadí daný term. To jsme viděli v minulém díle.
Jestliže jsou oba termy proměnné, pak je výsledkem jejich ztotožnění.
Příklad:
Jsou-li A i B volné, unifikace uspěje a proměnné se od tohoto okamžiku budou
chovat jako jedna. Pokud A bude v budoucnu unifikována například
s atomem kleofac, pak samozřejmě bude i B = kleofac.
Jestliže jsou oba termy atomy nebo čísla, pak unifikace uspěje pouze tehdy, pokud jsou oba stejné.
Jestliže jsou oba termy nějaké struktury, pak provedeme unifikaci rekurzivně. Podíváme se na jejich argumenty a pokud jich je stejný počet, zkusíme každý odpovídající si pár argumentů unifikovat. Pokud se to podaří pro každý argument (a samozřejmě pokud se struktury jmenují stejně), jsou struktury shodné.
V žádném jiném případě nejsou termy shodné a nelze je ani unifikovat.
Tím jsme si podrobně vysvětlili mechanismus unifikace. Teď už také
chápeme, co přesně dělá binární predikát =, totiž že vyvolává
unifikaci na své argumenty.
Co myslíte, že by se stalo, pokud byste napsali A = f(A)?
Seznamy
V Prologu máme k dispozici datovou strukturu seznam. Seznam je posloupnost termů, například čísel, struktur, nebo dalších seznamů.
Prázdný seznam se značí atomem []. Neprázdný seznam se zapíše
například takto: [a,b,c] nebo [1,2,3,4].
Prolog chápe seznam jako dvě části: hlavu a tělo. Hlava je
první prvek seznamu a tělo celý zbytek seznamu. Tento zbytek chápe
Prolog opět jako seznam, tedy v případě seznamu [a,b,c] je hlavou
prvek a a tělem opět seznam [b,c].
K tomu, abychom ze seznamu snadno oddělili hlavu, slouží ještě jiný
způsob zápisu seznamu: seznam [a,b,c] můžeme napsat jako
[a|[b,c]].
Už nás také napadá, jak budeme s prologovskými seznamy pracovat. Vždy si oddělíme hlavu, něco s ní uděláme a potom se pustíme rekurzivně na zbytek seznamu. Hned si to ukážeme na příkladu hledání prvku v seznamu:
V prvním řádku se díváme, jestli hledaný prvek není náhodou přímo v hlavě seznamu. Pokud hledaný prvek není v hlavě seznamu, musíme vzít zbytek (tělo) seznamu a pátrat v něm.
Jiný příklad, tentokrát hledáme poslední prvek seznamu:
První řádek je jasný, poslední prvek jednoprvkového seznamu je onen
jediný prvek. Druhý řádek je zajímavější, pokud máme seznam s jedním
prvkem, za kterým je ještě nějaký další seznam, zavoláme si rekurzivně
predikát posl na tělo seznamu s utrženou hlavou. Takto se postupně
volají predikáty posl na čím dál kratších seznamech. Proměnná Posl
je přitom stále volná. Jakmile dojedeme na konec seznamu a máme už jen
jednoprvkový seznam, dostaneme se na dno rekurze, uplatní se první
řádek programu a v tom okamžiku se nám úspěšně unifikuje proměnná
Posl.
Nakonec příklad bez komentáře:
Kvíz
♠ Který zápis seznamu není správný?
[ [a,b], c][a, b, [c] ][a, [b,c] ][ [a,b]|c][a,b,c,[]]
Odpověď: [ [a,b] | c] není seznam, protože za operátorem | musí být vždy seznam.
♠ Kolik prvků má seznam [a,b,c,[]]?
- 2
- 3
- 4
Odpověď: Seznam má čtyři prvky, a, b, c a [].
♠ Jaký výsledek dostaneme při ?-prvek(a,Seznam).?
No.Yes.[a,a,a,a,a,...][a,a,a,a,a,...] ; No.[a|_] ; [_,a|_] ; [_,_,a|_] ; ...
Odpověď: Prolog se snaží vyhovět vašemu dotazu a donekonečna generuje
všechny možné seznamy, které obsahují a, tedy správná je poslední varianta.
♠ Jaký bude výsledek dotazup(A,B,q(c,A,B))=p(a,b,q(c,a,d))?
- Yes.
- No.
Odpověď: Odpověď bude No., nejprve se unifikuje A = a, B = b,
ale potom ve třetím argumentu struktury q se srovnává B = d,
ale B už bylo unifikováno jako b.
Soutěžní úložky
1. Příliš těžké slepice (4 body) Slepice sedí na hřadě. Bidýlko se pod nimi prohýbá a každou chvíli hrozí, že praskne. Nejprohnutější a nejzatíženější je bidýlko pod prostřední slepicí. Slepice ale neví, která z nich je uprostřed. Napište slepicím program v Prologu, který dostane seznam slepic tak, jak sedí na bidýlku zleva doprava, a vybere prostřední z nich. Pokud je slepic sudý počet, vybere tu, která sedí více vpravo. Nezapomeňte, že slepice neumí počítat, takže nesmíte používat žádnou aritmetiku. Program by měl být co nejrychlejší. Slepice také neoplývají přílišnou chytrostí, takže byste svůj program měli náležitě okomentovat a popsat :o))
Příklad:
Pro vstup [a,b,c] je prostřední slepice b, pro vstup [1,2,3,4]
je prostřední slepice [3].
2. Permutující slepice (4 body) Poté, co jste vyřešili problém bidla praskajícího pod slepičími špeky, začalo slepice pálit dobré bydlo a obrátily se na vás s dalším problémem. Slepice se mezi sebou neustále hašteří, ve které části bidla bude která sedět. Už to tak dál nejde, a proto se budou každou noc střídat v pořadí. Napište program, který vypíše všechny možné rozmístění slepic na bidýlku, každé právě jednou. Vstupem programu je seznam slepic a výstupem seznam seznamů obsahující všechny permutace slepic, tj. všechny možnosti, jak mohou slepice sedět, každou právě jednou.
Příklad: Pro vstup [a,b] je výstupem tento seznam seznamů:
[ [a,b], [b,a] ], pro vstup [1,2,3] je výstupem následující seznam
permutací: [ [1,2,3],[1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2] ].
3. Palindromické slepice (4 body)
Jelikož jste dokázali usmířit rozhádané opeřence, byli jste požádáni
o vyřešení posledního problému. Slepice zjistily, že nejbezpečnější
rozmístění na bidýlku je takové, že proti sobě symetricky sedí vždy
slepice stejné váhy. Například rozmístění vah [1,2,3,3,2,1],
[4] či [4,3,5,6,5,3,4] jsou bezpečná umístění, zatímco [4,3],
[4,3,1], [5,6,7,7,6,6] nejsou bezpečná umístění. Napište program,
který zjistí, zda slepice sedí na bidýlku bezpečně. Jinými slovy,
zjistěte, zda číslo zapsané jako seznam číslic je palindrom, čili
slovo, které se čte stejně zepředu i zezadu. Pro sladkou bodovou
odměnu se snažte program co nejvíce urychlit (nejlépe na lineární :–).
Tímto se s vámi loučíme a těšíme se na setkání v příštím díle. Kokokodák!