Druhá série devatenáctého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 11. prosinec 2006. Ř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.

Zadání úloh

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×21×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.

Řešení


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.

Řešení


19-2-3 Moneymaker (10 bodů)


Hroší mafián

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

31
13
25
24

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.

Řešení


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 …“

Řešení


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

13
21
31
43

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…

Řešení


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:

datum(den(3),mesic(10),rok(2006)).
osoba(jmeno(bretislav),prijmeni(rozsejpal)).

Ve skutečnosti je strukturou dokonce i klauzule

matka(X) :- rodic(X,_), zena(X).

:- 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

:-(matka(X), (rodic(X,_), zena(X))).

Unifikace pořádně a naposled

Po zadání dotazu, například

?-je_matka(X).

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:

?-A = B.

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.

Danger!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:

% prvek(X,Seznam) je X prvkem seznamu Seznam
prvek(X,[X|_]).
prvek(X,[_|Telo]) :- prvek(X,Telo).

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:

% posl(Seznam,X) vraci posledni prvek seznamu
posl([X],X).
posl([_|Telo],Posl) :- posl(Telo,Posl).

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:

% vypust(X,Sezn,NovySezn)
% vypusti jeden vyskyt X ze seznamu
% Sezn a vrati novy seznam NovySezn
vypust(X,[],[]).
vypust(X,[X|T],T).
vypust(X,[Y|T],[Y|L]) :- vypust(X,T,L).

Kvíz

♠ Který zápis seznamu není správný?

  1. [ [a,b], c]
  2. [a, b, [c] ]
  3. [a, [b,c] ]
  4. [ [a,b] | c]
  5. [a,b,c,[]]

♠ Kolik prvků má seznam [a,b,c,[]]?

  1. 2
  2. 3
  3. 4

♠ Jaký výsledek dostaneme při ?-prvek(a,Seznam).?

  1. No.
  2. Yes.
  3. [a,a,a,a,a,...]
  4. [a,a,a,a,a,...] ; No.
  5. [a|_] ; [_,a|_] ; [_,_,a|_] ; ...

♠ Jaký bude výsledek dotazu
p(A,B,q(c,A,B))=p(a,b,q(c,a,d))?

  1. Yes.
  2. No.

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].

Těžká slepice?

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!

Řešení