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

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

Řešení úloh

19-2-1 Čokoláda podruhé (Zadání)

Jak si mnoho z vás všimlo, existuje docela jednoduchá vyhrávající strategie pro prvního hráče. V prvním kroku náš začínající bandita rozlomí čokoládu na dvě totožné části (všimněme si, že je to možné pouze tehdy, máme-li alespoň jeden rozměr sudý) a dále už jen opakuje podle osy prvního zlomu soupeřovy tahy do té doby, než vyhraje.

Uvědomme si, že taková strategie určitě vede k vítězství. Pokud jsme hráli podle popsané stragie a prohráli jsme, tj. odlomili jsme kostičku 1×1, udělali jsme to proto, že náš soupeř udělal to samé v minulém tahu – musel tedy prohrát on.

To bylo v případě, že hra skončí. Mohlo by se teoreticky stát, že budeme lámat do nekonečna a nikdo neprohraje. V našem případě se to ale určitě nestane, protože se čokoláda skládá jen z konečného počtu čtverečků.

Cyril Hrubiš

19-2-2 Kvalitní hesla (Zadání)

Jako obvykle jsem chtěl začít své řešení vtipnou poznámkou či glosou, ale vzhledem k tomu, že mi zubařka o Vánocích vyvrtala 4 zuby a já mohl všechny ty cukrovinkami se cpoucí lidi jen sledovat, jistě chápete, že na vtipy nemam náladu. Takže k řešení.

První nápad je vyzkoušet všechny možné podřetězce hesla a vzájemně je porovnat. Bez ohledu na vámi navrhované heuristiky pracuje toto řešení v čase O(N3) vzhledem k délce hesla v nejhorším případě s pamětí O(N), což jste si povětšinou správně uvědomovali a zasloužíte si pochvalu. Pokud jste mi přece jen tvrdili, že je to rychlejší, tak se ještě jednou zamyslete, zda skutečně neexistuje nějaký protipříklad. Pokud by vás přece jen nenapadl (případně já udělal chybu), ozvěte se.

Ono to ale jde o něco (a následně o dost) lépe. Představme si, že máme dobrého kamaráda a ten nám poví, jak daleko od sebe leží začátky shodných podstringů. Pak je ale snadné zjistit, kde se takové podřetězce nachází, prostě jen projdeme celé heslo a nalezneme nejdelší posloupnost shodných dvojic v této vzdálenosti. A to zvládneme jedním průchodem. No a co když nemáme dobré kamarády? Tak prostě prozkoušíme všechny možné vzdálenosti a jen si zapamatujeme, kde jsme dosáhli maxima. Že takových vzdáleností je N a časová složitost O(N2) nás tudíž nemine, jistě nemusím dodávat.

Nyní si sedněte, udělejte pohodlí a připravte kyblíčky (na nervy). Začnu slovem suffixový strom. Už tím jsem vás jistě odradil, ale pro ty skutečně otrlé dodám ještě odkaz a zároveň velmi poděkuji Kubovi Kaplanovi za tento odkaz a potřebnou inspiraci. Pojednání je bohužel anglicky, takže přidávám ještě jedno české, jež je obklopeno ještě několika dalšími zajímavými algoritmy. Po přečtení těchto článečků zjistíte, co to takový suffixový strom je, ke svému údivu objevíte, že se dá zkonstruovat lineárně a s lineární pamětí (no já taky zíral) a … využijete služeb kyblíčku. Pro ty méně otrlé připojím malý popis. Nejprve vysvětlení: suffix je „koncovka“ slova, např. pro slovo book získáme suffixy book, ook, ok, k a prázdný suffix. Suffixový strom je pak trie, ve které jsou uloženy všechny suffixy zadaného řetězce (pokud nevíte co je trie, zapátrejte v ročenkách). Ta má zjevně paměťovou složitost až O(N2) a logicky s tím i čas na její stavbu je O(N2). Tím bychom si moc nepomohli, a tak tuto trii vylepšíme. Všechny vrcholy, které mají jen jednoho následníka, sloučíme s jejich otci. V naší trii tak například budou sloučeny vrcholy b→o→o→k do jednoho vrcholu book. Tím se paměťová složitost zmenší na lineární (uvědomte si, že přidáním suffixu do takto komprimované trie přidáme maximálně dva vrcholy a že všechny řetězce přiřazené k hranám trie jsou podslova zadaného slova, takže si je stačí pamatovat jako polohu začátku a konce v tomto slovu). Technické detaily již ponechám článku a teď k vlastnímu řešení.

Na konec hesla připojím nějaký nikde se nevyskytující znak a nad takto vytvořeným řetězcem vytvořím suffixový strom. Jak se nám projeví společná část suffixů? To je část od kořene stromu k prvnímu místu, kde se tyto suffixy rozdělí. Je velmi důležité si uvědomit, že k tomu musí dojít, protože máme-li dva suffixy, tak se tyto musí lišit v délce a tudíž kratší se oddělí na nějakém znaku od delšího (liší se přinejmenším koncovým znakem hesla, který byl přidán a jistě se uprostřed delšího suffixu nevyskytuje). Tyto společné části suffixů ale hledáme, protože každý podstring je zjevně začátkem (libovolně dlouhým!) alespoň jednoho suffixu. Námi hledaný řetězec se tedy jistě vyskytuje na začátku alespoň dvou suffixů (rozmyslet!).

Příklad: pro heslo ananas a suffixy ananas, nanas, anas, nas, as, a mají nejdelší společný začátek ananas a anas a výsledkem je ana. Dále si všimněte, že suffix anas krom toho začíná na řetězce a, an, ana, anas.

Nejdelší společnou část suffixů pak snadno najdeme jedním průchodem stromu do hloubky, při kterém budeme hledat nejdelší cestu z kořene do vrcholu s alespoň dvěma následníky. To je díky lineární velikosti stromu též lineární, a tak jsou celkové složitosti paměťová i časová O(N). Ale ptám se vás, stálo to za to? :–)

Program

Jan Bulánek

Poznámka na okraj: Byl bych sice ten poslední, kdo by se ošklíbal nad suffixovými stromy, jenže mi to přece jen nedá, abych neukázal ještě jedno řešení, které má sice o trochu horší časovou složitost, ale vystačí si s daleko jednodušší mašinerií, konkrétně s hešováním z kuchařky v této sérii a přihrádkovým tříděním.

Když vymyslíme algoritmus (budeme mu říkat třeba pohrabáč, protože se jím prohrabujeme řetězcem), který v lineárním čase pro dané k zjistí, zda se v zadaném řetězci vyskytuje nějaký podřetězec délky k vícekrát, můžeme použít půlení intervalu na nalezení největšího takového k, přičemž pohrabáč použijeme jen log N-krát.

Lineární pohrabáč vám sice nenabídnu, ale ukážu, jak to udělat alespoň v průměrně lineárním čase. Zvolíme si šikovnou hešovací funkci, která bude hešovat k-znakové řetězce do N2 přihrádek a bude mít navíc tu vlastnost, že pokud jsme ji spočítali pro znaky a1… ak, dokážeme ji z toho v konstantním čase spočítat pro a2… ak+1 (zkuste si rozmyslet, že funkce hash_string z kuchařky toto splňuje). Tak dokážeme zahešovat všechny podřetězce délky k v lineárním čase a víme, že pokud se nějaký vyskytl vícekrát, určitě oba výskyty skončí v jedné přihrádce. Stačí tedy po zahešování projít všechny kolize a zjistit, jestli existovaly dva stejné podřetězce. Navíc platí, že při tomto počtu přihrádek je průměrný počet kolizí O(1) (to si nedokážeme, ale s pomocí povídání o pravděpodobnosti a středních hodnotách z 16. ročníku to snadno vymyslíte), takže probrání všech kolidujících párů zvládneme v čase O(k)=O(N).

Jenže ještě tu je jeden háček: přihrádek jsme zvolili N2, a tak si nemůžeme dovolit přihrádky reprezentovat polem, protože jenom na jeho projití potřebujeme kvadratický čas. Proto si prostě ke každému začátku podřetězce poznamenáme stranou hodnotu hešovací funkce a začátky podle těchto hodnot setřídíme – to jde přihrádkovým tříděním s N přihrádkami stihnout v lineárním čase, což přesně potřebujeme. Poté porovnáme všechny podřetězce se stejnou hešovací funkcí a zjistíme, zda jsou nějaké dva shodné.

Celkově tedy umíme pohrabovat v čase O(N) průměrně a požadované k najít v O(N log N) a lineární paměti.

Program

Martin Mareš

19-2-3 Moneymaker (Zadání)

Asi nejjednodušší řešení této úlohy by se dalo popsat slovy když metoda hrr na ně nezabere, tak se stáhneme a zkusíme to zezadu. Až na jedno řešení využívající intervalové stromy skončili všichni řešitelé začínající od počátku kvadratickou, popř. ještě horší časovou složitostí. Nyní ale zpět k tomu, jak se úloha měla řešit.

Označme T termín nejméně spěchající zakázky. Budeme postupně, pro jednotlivé časy t < T, generovat pořadí plnění zakázek (označme je A
t
t
, A
t
t+1
, … , A
t
T
), kterým maximalizujeme zisk v časovém úseku < t ; T >. Pokud zjistíme jak toto pořadí vypadá pro t = 1, tak máme hotovo.
Pro t = T je to jednoduché. Mezi všemi zakázkami s termínem T vybereme tu, která je nejlépe placená. Nyní předpokládejme, že známe optimální pořadí zakázek od času t+1 (tj. známe A
t+1
t+1
, A
t+1
t+2
, … , A
t+1
T
). Pak tvrdím, že jedna z možných sekvencí zakázek s maximálním ziskem je:
  • A
    t
    i
    = A
    t+1
    i
    pro i ≥ t+1
  • A
    t
    t
    nalezneme jako zakázku s maximální odměnou, která má termín t, nebo pozdější, a kterou jsme ještě nepoužili (tj. není mezi {A
    t+1
    i
    }).
Dokáže se to snadno. Pro spor předpokládejme, že známe nějaké pořadí B
t
t
, B
t
t+1
, … , B
t
T
, které nám zajistí lepší zisk.
Zároveň ale víme, že odměna za úkoly A
t
t+1
, A
t
t+2
, … , A
t
T
je alespoň stejně velká jako za zakázky B
t
t+1
, B
t
t+2
, … , B
t
T
(z toho, že jsme předpokládali, že {A
t+1
i
} maximalizuje zisk na časovém intervalu < t+1 ; T>). Z toho plyne, že odměna za B
t
t
je větší než odměna za A
t
t
. Jelikož ale A
t
t
má maximální odměnu ze všech zakázek, která nebyly obsaženy v {A
t+1
i
}, musí tedy existovat j > t takové, že A
t+1
j
(= A
t
j
) = B
t
t
, nebo jsme dostali spor. Prohodíme tedy v posloupnosti {B
t
i
} pozice úkolů B
t
t
a B
t
j
(to si můžeme dovolit, jelikož pak úkol B
t
j
splníme dřív a zakázku B
t
t
můžeme splnit až v čase j, protože se až tak pozdě vyskytovala v posloupnosti {A
t+1
i
}, která termíny respektuje). Tím jsme zřejmě nezměníme celkovou odměnu za úkoly v {B
t
i
} a tedy celý tento odstavec můžeme použít na novou posloupnost {B
t
i
} úplně stejně.
To jsme ale ještě nic dokázali, jak si jistě čtenář všiml. Spor dostaneme až když si uvědomíme, že výše uvedené nemůžeme opakovat donekonečna. Pokud budeme uvažovat počet úkolů, které jsou v {A
t
i
} a {B
t
i
} na stejném místě (tj. počet takových k, že A
t
k
= B
t
k
), tak v každém cyklu stoupne o 1 (úkol B
t
t
se dostane na stejné místo jako je v posloupnosti {A
t
i
}), tedy po několika opakováních výše uvedeného musíme někdy dostat spor.

No a jak toto nejlépe implementovat? Nejdřív setřídíme úkoly dle termínu. Pak budeme odzadu generovat jednotlivé úkoly, které je třeba v daný čas t udělat. K tomu použijeme haldu. Budeme si v ní udržovat úkoly, které mají termín t či pozdější a které jsme zatím ještě nezařadili mezi zakázky, které splníme. Na začátku bude prázdná a v každém kroku do haldy přidáme všechny úkoly, které mají termín t (pozdější tam již máme z předchozích kroků) a odebereme maximum. Tím jsme skoro hotovi.

Kdybychom implementovali výše uvedené doslovně, tak čas běhu programu bude kromě velikosti vstupu záviset i na nejpozdějším termínu úkolu. Toho se ale je možno jednoduše zbavit. Pokud bude halda prázdná, tak můžeme rovnou posunout čas na nejbližší dřívější termín zakázky, čímž si ušetříme čas.

No a složitost. Setřízení pomocí rychlého třídícího algoritmu trvá O(N · log N). Přidání do haldy zabere O(log N) a provádíme ho N-krát, tedy opět O(N · log N). No a ještě z haldy odebíráme kořen. To uděláme také maximálně N-krát a trvá to O(log N). Dohromady tedy O(N · log N).

V paměti máme vstup a haldu. Jejich velikost je přímo úměrná velikosti vstupu, tedy paměťová složitost je O(N).

Program

Pavel Čížek

19-2-4 Optimální formace (Zadání)

Tato úloha, na první pohled docela snadná – stačilo najít souřadnice vrcholů jakéhokoli konvexního mnohoúhelníka, byla nakonec docela těžká. První, byť jen malý zádrhel, byl v tom, uvědomit si, že každý střelec musí svůj dostřel využít naplno. Pokud bychom totiž u střelce §Si využili jen část dostřelu tak, aby všechny vnitřní úhly byly ostře menší než 180°, mohli bychom útvar malilinko „zplacatit“ a dostat tak ještě o kousek větší obvod. Takhle bychom se buď u každého dostali na maximální dostřel, nebo maximum neexistuje.

Kdy jde nakreslit konvexní mnohoúhelník o zadaných stranách? Pokud splňuje zobecnění trojúhelníkové nerovnosti – mnohoúhelníkovou nerovnost, která říká, že pro každou hranu Si musí součet délek ostatních hran být větší než délka Si. Tuto nerovnost stačí ověřit pro Si nejdelší stranu. Nejdelší stranu budu dále označovat S0, ostatní pak S1,S2,Sn-1 v pořadí v jakém navazovaly na S0. Vrcholy označím V0,…Vn-1, přitom Si=(Vi,Vi+1) a Sn-1=(Vn-1,V0).

Jak teď sestrojit konkrétní souřadnice? Mohli bychom si mnohoúhelník představit jako trojúhelník V0V1Vl, kde l je co nejblíže polovině vzdálenosti V1-V0 mimo S0. Takový trojúhelník splní trojúhelníkovou nerovnost a celkem snadno můžeme spočíst souřadnice jeho vrcholů. Teď už stačí body na přímkách V1-Vl a Vl-V0 lehce „vyboulit“ abychom dosáhli úhlů menších než 180° a přitom si nepokazili sestrojitelnost ani konvexnost. Jak na to?

Jedna z možností je umístit strany S1,S2,…Sn-1 jako tětivy po obvodu dostatečně velké kružnice k a tu pak ve vhodném bodě Vl „zlomit“ a přiblížit tím body V0 a V1 na délku úsečky S0. Jak velkou kružnici k zvolit? Stačí, když po tom, co na ní umístíme S0 jako tětivu, délka oblouku V0V1 bude menší nebo rovna obvodu mnohoúhelníka bez nejdelší strany. Nyní se dostává ke slovu analytická geometrie černější než černá magie a proto nebudu všechny kroky zdůvodňovat a důkazy korektnosti jednotlivých voleb přenechám laskavému čtenáři.

Obvod mnohoúhelníka bez nejdelší strany označím Su Poloměr kružnice k zvolím

r ≥
Su S0
√
S
2
u
S
2
0
.

Střed této kružnice umístím na souřadnici [r,0], od souřadnice [0,0] začnu směrem nahoru po kružnici umisťovat body V1,V2,…Vn-1,V0 ve správných vzdálenostech na souřadnice [xi,yi]. Jak spočítat souřadnice těchto bodů? Další bod Vi+1=[xi+1,yi+1] musí být ve správné vzdálenosti od bodu Vi=[xi,yi] i středu kružnice k [0,r], musí tedy platit

(xi+1-r)2+y
2
i+1
=r2
(xi+1-xi)2+(yi+1-yi)2=S
2
i

Vyřeším kvadratickou rovnici, ze které dostanu dvě možnosti pro Vi+1. Kružnici jsem si zvolil dvakrát tak velkou, než bych nutně potřeboval a proto mohu spoléhat na to, že pokládám vždy směrem nahoru. Označím-li si pro jednotlivá i

Ai+1=1+
(r-xi)2
y
2
i
Bi+1=
(r-xi)(x
2
i
+y
2
i
+S
2
i
)
y
2
i
-2r
Ci+1=
(x
2
i
+y
2
i
+S
2
i
)2
4y
2
i
,
dostanu xi+1=(Bi+1+√(B
2
i+1
-4Ai+1Ci+1))/2Ai+1 a
yi+1=
x
2
i
+y
2
i
+S
2
i
+2xi+1(r-xi)
2yi
.

Bod Vl zvolím co nejblíže polovině vzniklého oblouku V1V0. Je třeba dopočíst finální souřadnici bodu V0 tak, aby byl od V1 vzdálen S0 a od V0 vzdálen F. Toto opět vede na soustavu kvadratických rovnic, z jejichž dvou řešení vybereme to s větší souřadnicí y. Výpočet souřadnic [x0,y0] je jen rutina a přenechám ji odvážnému čtenáři, který se dočetl až sem.

Předposlední částí výpočtu je otočit body Vl+1,Vl+2,…, Vn-1 okolo bodu Vl o stejný úhel, o jaký byl otočen bod V0 (ten se pohyboval na kružnici se středem v Vl). To je možné třeba spočtením tohoto úhlu goniometrickými funkcemi a sestavením transformační matice nebo řešením dalších soustav kvadratických rovnic.

Poslední částí je pak jednoduché vypsání výsledků, které je po tom všem už hračkou.

Časová i paměťová složitost tohoto algoritmu je lineární. Paměťovou složitost by bylo možno snížit na konstantní, pokud bychom některé hodnoty zapomínali a v průběhu výpočtu si je znovu dopočítali. Program neuvádíme, protože se skládá pouze z výpočtů pomocí zde navržených vzorců.

Tomáš Gavenčiak

19-2-5 Hluboký les (Zadání)

Je zajisté triviální nalézt les nejhlubší zkoumáním vzdáleností všech dvojic stromů, ale uznejte sami, že za to bychom sotva slibovali 13 bodů, protože je to cca desetiřádkový program s ošklivou kvadratickou složitostí. Zkrátka to, čemu se říkává dřevorubecké řešení. Pojďme se raději zakoukat do hladiny křišťálové studánky, jestli nám neporadí, jak na to jít lépe (třeba od lesa):

Stromy si představme jako body v rovině, x-ová souřadnice bude odpovídat směru zleva doprava, y-ová shora dolů. Vzdálenost stromů S1=(x1,y1) a S2=(x2,y2) bude činit:

d(S1,S2) = √(x1-x2)2 + (y1-y2)2.

Kdo jste tento vzoreček ještě nepotkali, vzpomeňte si na pana Pythagora a jeho větu – chceme změřit přeponu pravoúhlého trojúhelníka S1TS2 s pravým úhlem u vrcholu T=(x2,y1). Místo vzdáleností budeme ale raději porovnávat jejich druhé mocniny, což jsou pro celočíselné souřadnice bodů také celá čísla. Tak si ušetříme starosti se zaokrouhlovacími chybami a program bude nadále fungovat, jelikož x<y platí právě tehdy, když x2<y2, tedy aspoň pro nezáporná čísla, což výraz pod odmocninou bezpochyby je.

Ještě si všimněme jednoho zajímavého faktu: pokud chceme do čtverce velikosti d×d umisťovat body tak, aby vzdálenost každých dvou byla alespoň d, vejdou se tam maximálně čtyři (třeba do vrcholů čtverce). Dokázat to můžeme například tak, že čtverec rozřežeme na čtyři menší čtverce velikosti d/2 ×d/2, které budou mít společné hrany, a nahlédneme, že do každého z nich můžeme umístit nejvýše jeden bod. Nejvzdálenější body v malém čtverci jsou totiž jeho protilehlé vrcholy a ty mají vzdálenost d√2/2<d.

Jak onehdy naznačili jistí programátorští kuchaři, hodit by se mohla metoda Rozděl a panuj. Ta by se pro hledání nejbližší dvojice bodů dala použít zhruba následovně:

Pokud by první a třetí krok algoritmu běžely v lineárním čase, choval by se celý algoritmus podobně jako QuickSort s rovnoměrným dělením, který jsme ukazovali v kuchařce, a tedy by jeho časová složitost byla O(N log N) a paměťová O(N). Stručně: Na vstup délky N spotřebujeme čas O(N) plus ho rozložíme na dva vstupy délky N/2. Pro ty potřebujeme dohromady také čas O(N) plus je rozdělíme na čtyři vstupy délky N/4, a tak dále, až se po  log2 N krocích dostaneme ke vstupům délky 1 a celkem tedy spotřebujeme čas O(N log N). To je velmi lákavá představa, jen zatím poněkud efemérní, jelikož není vůbec jasné, jak první a třetí krok provést.

Rozdělování bodů: Nabízí se vybrat souřadnici rozdělovací přímky náhodně (podobně jako u QuickSortu bychom se tak dostali na průměrně rovnoměrné rozdělení) nebo si vzpomenout na lineární algoritmus pro výpočet mediánu uvedený v kuchařce. Oba přístupy ale mají společný háček: pokud většina stromů leží na jedné vodorovné přímce, vybereme nejspíš tuto přímku a body rozdělíme nerovnoměrně. Tomu by se dalo odpomoci dělením na tři části – body ležící na dělící přímce bychom zpracovali úplně zvlášť, beztak padnou do pásu, ve kterém dvojice kontrolujeme explicitně.

Mnohem jednodušší je na začátku algoritmu setřídit všechny body podle svislé souřadnice a rozdělit je prostě na prvních ⌊N/2⌋ a zbylých ⌈N/2⌉. Různé body na dělící přímce sice mohou padnout do různých polovin, ale to není nikterak na škodu, stejně je následně všechny probereme. Třídění nám časovou složitost nepokazí a rozdělování pak dokonce zvládneme v konstantním čase.

Porovnávání hraničních dvojic: Dvojic může být až kvadraticky mnoho (představte si všechny body ležící na dvou vodorovných přímkách), takže je musíme probírat šikovně. Kdybychom je měli setříděné zleva doprava, stačilo by pro každý bod B prozkoumat jen několik bodů od něj doprava – jakmile x-ová vzdálenost překročí d, nemá smysl dál hledat. Zajímají nás tedy body z X1 ležící ve čtverečku d×d bezprostředně nad přímkou a body z X2 ve stejně velkém čtverečku pod přímkou. A my už víme, že v každém z těchto dvou čtverečků mohou ležet nejvýše 4 zajímavé body (každé dva body ležící v téže množině jsou přeci vzdálené aspoň d a použijeme pozorování o umisťování do čtverečků). To je celkem 8 bodů, navíc jedním z nich je náš bod B, čili pro každý bod B zbývá prozkoumat jen 7 následníků. To snadno stihneme v lineárním čase.

Předpokládali jsme ale, že prvky máme setříděné. To skutečně máme, jenže podle druhé souřadnice, než potřebujeme. Jak z toho ven? Jistě můžeme body na počátku setřídit podle každé souřadnice zvlášť a při rozdělování udržovat obě poloviny také setříděné oběma způsoby, ale opět bychom se dostali do potíží s mnoha body na jedné přímce. Proto se uchýlíme k drobnému úskoku: zabudujeme do naší funkce třídění sléváním: funkce na vstupu dostane body setříděné podle y a vrátí je setříděné podle x. To půjde snadno, jelikož z rekurzivních volání dostane každou polovinu správně setříděnou, a tak je jen v lineárním čase slije.

Tím jsme doplnili bílá místa v algoritmu a zbývá ukázat program. Je napsaný v C99 a drží se téměř doslovně našeho algoritmu. Vypisuje pouze nalezenou vzdálenost, ale sami jistě vymyslíte, jak do něj dodělat, aby vypisoval i souřadnice místa, kde nejhlubší je les.

Pár poznámek na závěr:

Program

Martin Mareš

19-2-6 Prolog (Zadání)

1. Příliš těžké slepice Navzdory názvu nebyla úložka příliš těžká, pokud by se ovšem slepice spokojily s kvadratickým řešením. Snad každého napadlo vzít seznam, uškubnout mu hlavu, dojet na konec seznamu, uškubnout poslední prvek a takhle pokračovat, dokud bychom nezískali prostřední prvek, případně dvojici prvků, v závislosti na tom, zda byl vstupní seznam sudé nebo liché délky. Slepicím se takové řešení moc nelíbilo, možná také proto, že nerady slyší zmínku o škubání.

Zkusme tedy použít trik. Vyšleme v řadě slepic dva signály – jeden pomalý, jeden dvakrát rychlejší. Jakmile dojede rychlý signál na konec, pomalý bude právě uprostřed. V Prologu toto realizujeme tak, že si na vstup dáme tentýž seznam dvakrát a v každém kroku utrhneme v prvním seznamu jenom hlavu, v druhém seznamu první i druhý prvek zároveň.

proGram

2. Permutující slepice

Ukázalo se, že tato úloha byla poměrně obtížná. Problém byl hlavně s manipulací se seznamy, většině řešitelů se nepovedlo vytvořit požadovaný seznam permutací.

Jak na to: Ze vstupního seznamu postupně vyberu každý prvek X (tedy jakýsi cyklus for přes všechny prvky seznamu) a vytvořím seznam bez tohoto prvku. Tento seznam nechám rekurzivně zpracovat a dostanu seznam všech možných permutací, jen bez prvku X, načež prvek X předřadím jako hlavu před každou z těchto permutací. Když toto provedu se všemi prvky v zadaném seznamu, vygeneruji všechny permutace.

Jako další argument si musím předávat seznam již vytvořených, hotových permutací, abychom je nezapomněli (neb Prolog nemá globální proměnné) a kdykoliv vytvořím novou permutaci, vložit ji do tohoto seznamu.

Nápad se lehce řekne, ale hůř napíše. Prohlédněte si tedy připojený program.

Nakonec dodáme, že se opravovatelé příliš nešťourali v syntaktických detailech a okrajových případech této úlohy a body se udělovaly i za přibližné řešení.

pogrrma

3. Palindromické slepice

Tato úložka byla opět jednoduchá pro toho, kdo se rozhodl pro jednoduché kvadratické řešení. Snadno vidíme, že stačí vzít vždy první a poslední prvek seznamu, porovnat je a takto pokračovat, až dojedeme doprostřed seznamu.

Rychlejšího, lineárního řešení dosáhneme tak, že seznam otočíme a potom porovnáme původní vstupní seznam s otočeným seznamem. Pokud se shodují, byl vstupní seznam palindromem.

Jak ale otočíme seznam v lineárním čase? To dokážeme pomocí známého triku – použitím tzv. akumulátoru. Princip je velmi jednoduchý – vezmeme si původní seznam, z něj budeme trhat prvky a předřaďovat je jako hlavu do druhého seznamu. Až nám dojdou prvky v původním seznamu, v druhém seznamu (akumulátoru) budeme mít otočený původní seznam.

margorP

Jana Kravalová