První série dvacátého osmého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 26. října 2015 8:00. Termín odevzdání CodExové úlohy je pak 26. října 2015 8:00. Ř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.

Odměna série: Řešitelům, kteří vyřeší alespoň jednu ze dvou nejvíc bodovaných úloh první série na plný počet bodů, pošleme sladkou odměnu.

Zadání úloh

Vyhrocené sousedství

Je jasná, klidná letní noc. Téměř celé město spí, u řeky se prochází nevinné páry a na diskotékách vydrželi už jen ti největší tahouni. Silnice jsou prázdné. Jen občas na nich můžeme potkat zpívající skupinku, oslavující včerejší fotbalový úspěch, nebo taxík vezoucí ty, kdo už domů nezvládají dojít po svých.

Všechen klid tady kazí jen jeden zmateně pojíždějící motorkář a skupina policejních aut snažící se o jeho dopadení. Motorkář nejede nijak rychle, ale moc se nezajímá o protisměry, nemá boty, natož helmu, a už vůbec nehodlá zastavit. Hlídkám zdařile uniká a úspěšně objíždí i všechny zátarasy. Ale jen do chvíle, než dojede do slepé uličky, kde jej policie konečně dopadne.


Praktická opendata úloha28-1-1 Jízda na biomotorce (10 bodů)


Představte si, že jedete městem na motorce, jiné než té v příběhu: na biomotorce. Takové, která jezdí na pomeranče. Na jeden pomeranč je schopná ujet celých 100 metrů. Má to ale háček: pomeranče jsou velké a vejde se jich do nádrže jen 10. Naštěstí ale pomeranče ve městě jen tak rostou na stromech.

Ilustrace: Zmatená silnice

Mapa je tvořená křižovatkami a ulicemi, které je spojují. Můžeme si ji tedy představit jak neorientovaný ohodnocený graf, v němž navíc každý vrchol má daný počet pomerančů, které v něm rostou.

Napište program, který na vstupu dostane mapu města a najde trasu ze startu do cíle, během které co nejméněkrát projedeme ulicemi (tedy nás zajímá počet přejezdů a ne celková délka trasy). Během cesty můžete brát pomeranče z křižovatek. Nesmíte však překročit limit 10 pomerančů v nádrži. Křižovatky i ulice se mohou na trase opakovat.

Všechny sebrané pomeranče na křižovatce dorostou hned po jejím opuštění a dojetí na jinou křižovatku. Na začátku má motorka prázdnou nádrž, ale můžete ji naplnit pomeranči ze startovní křižovatky.

Formát vstupu: Na prvním řádku vstupu budou čísla N, M, SC oddělená jednou mezerou, kde N je počet křižovatek ve městě, M počet ulic, S číslo startovní křižovatky a C číslo cílové křižovatky.

Na druhém řádku bude N mezerou oddělených čísel udávající počty pomerančů v jednotlivých křižovatkách. Na dalších M řádcích jsou popsány ulice, každá třemi čísly. První dvě udávají čísla křižovatek, mezi kterými ulice vede, a třetí udává délku ulice v metrech. Všechny ulice jsou obousměrné.

Pro hodnoty na vstupu dále platí:

  • 1 ≤ N ≤ 30 000
  • 1 ≤ M ≤ 1 000 000
  • Křižovatky jsou číslované od 1 do N.
  • Na každé křižovatce leží maximálně 10 pomerančů.
  • Ulice jsou dlouhé minimálně 100 a maximálně 1 000 metrů. Délky jsou násobky 100.

Formát výstupu: Na výstup vypište jedno celé číslo udávající délku nejkratší cesty v počtu projetých ulic ze startu do cíle, na které vám nikdy nedojdou pomeranče v nádrži.

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Řešení

Motorkář je mírně zakrvácený, vytřeštěný a stále opakuje, že musí utéct. Není mu to ale nic platné, je odveden na stanici a usazen na židli do rohu, kde čeká, než na něj přijde řada.

* * *

Tím motorkářem jsem já. Roztřeseně sedím, hledím do země a naslouchám okolnímu dění.

„Já nevim proč! Prostě najednou odněkud vyskočil, vyrval mi tu pochodeň z ruky, srazil mě na zem a zdrhnul někam do lesa!“ rozčiloval se muž na policejní stanici.

„A nemůžete prostě vzít kus klacku a vyrobit si novou? To nás musíte zdržovat takovýma prkotinama?“ reaguje znuděně policista.

„To nebyla jen tak nějaká pochodeň,“ brání se muž, „to byla speciální žonglovací pochodeň za tisíc korun!“

„Dobře, dobře…“ vzdává se policista, „tak to teda vezmeme znova od začátku.“ „Budeš zapisovat,“ říká kolegovi.

„Jak se incident odehrál?“ ptá se.

„Žongloval jsem v rámci fire show na louce u lesa. Najednou se vedle mě objevil chlap, vzal mi pochodeň, srazil mě na zem a zdrhl. To už jsem vám přece říkal!“ popisuje muž a praští naštvaně pěstí do stolu.

„Můžete pachatele nějak popsat?“ ptá se nenuceně dál policista.

„No… já jsem ho moc neviděl. Byla tma a soustředil jsem se na žonglování,“ vykládá muž, „takový normální chlap, o trochu vyšší než já a byl docela silný.“

„Skvělý! Napiš tam, že hledáme normálního muže vysokého asi 185 centimetrů, co chodí po městě s pochodní,“ vysmívá se policista, „proboha chlape, to na něm nebylo nic neobvyklého?“

„Ne,“ odpovídá muž, „vlastně… měl na ruce něco jako moderní hodinky. Takový technologický náramek – pořád to blikalo.“

Policista se pohrdavě otočí na kolegu: „Máš to?“

„Jo, mám,“ říká kolega.

„Tak děkujeme za nahlášení. V případě jakýchkoliv výsledků ve vašem případu vás ihned budeme informovat. Číslo na vás máme. Na shledanou!“ loučí se s mužem.

Muž se zvedl a trochu nesouhlasně odcházel. Asi tušil, že svou pochodeň již nikdy neuvidí. Jak by taky mohl, když dneska je problém najít ukradené auto, nebo třeba i kamion. A kamion se oproti pochodni sakra dobře hledá.

Ale vlastně ho trochu chápu. Hrátky s ohněm jsou fajn. Když mi bylo pět, tak jsme si s klukama ze sousedství tajně s ohněm hráli. Jen než mi jeden blbeček zapálil kraťasy a způsobil ošklivé popáleniny. Od té doby mám z ohně panickou hrůzu. Ono totiž utíkat před ohněm, který hoří přímo na vás, je čirá marnost.


Teoretická úloha28-1-2 Zapalování kostek (8 bodů)


Hrajeme následující hru. Máme postavenou pyramidu z dřevěných kostek o K patrech. To jest v prvním patře máme K kostek, na nich stojí K-1 kostek, na těch stojí K-2 kostek, až na špičce stojí jen jedna kostka.

Dva hráči se střídají v tazích. V jednom tahu hráč vybere jednu kostku v pyramidě a zapálí ji. To zapálí (obě) kostky, které na ní stojí, ty zas zapálí kostky, které stojí na nich a tak dále. Sousední kostky od aktuální nechytnou! Pak hraje druhý hráč. Vyhrává ten, kdo zapálí poslední kostku v pyramidě.

Pro dané K navrhněte vyhrávající strategii pro prvního hráče. To znamená takovou strategii, že ať druhý hráč dělá cokoliv, první vždy vyhraje.

Lehčí variantaLehčí varianta (za 3 body): Popište konkrétní strategii pro K=4K=5.

Řešení

„Tak teď vy,“ křikl na mě policista.

Hlídka mě odvádí k výslechovému stolu a sundává mi pouta. Rozklepaně pokládám ruce na stůl, sklopím hlavu a mlčím. Po chvíli se ozve policistův rozzářený hlas.

„Ale, ale… Vás jsme tady měli i včera, že jo? Nějaké sousedské problémy, jestli si správně pamatuji.“

„A-a-ano… S-s-soused mi-mi-mi z-zbořil m-můj ko-ko-komín.“


Teoretická úloha28-1-3 Bourání komínu I (12 bodů)


Na zahradě stojí V metrů vysoký komín, který chceme zbourat. K tomu máme k dispozici N bomb. Bomba i váží wi kilogramů a zničí přesně di metrů komínu. Komín bouráme postupně odshora. Při boření vždy musíme vynést bombu až na vršek zbytku komínu a tam ji odpálit. Tím se komín sníží o di metrů (přitom nesmí vyjít záporná výška, nechceme skončit s jámou).

S nošením bomb se ale chceme co nejméně nadřít. Vynesení i-té bomby na komín vysoký x nás stojí x  · wi jednotek energie. Navrhněte algoritmus, který naplánuje boření komínů tak, abychom celkem použili nejmenší možné množství energie.

Lehčí variantaLehčí varianta (za 7 bodů): Řešte případ, kdy všechny bomby dohromady zničí přesně V metrů. Tedy víme, že je všechny musíme použít.

Řešení


Praktická CodExová úloha28-1-4 Bourání komínu II (8 bodů)


Stejná úloha jako minulá, ale nyní ji řešte prakticky v CodExu. Stačí ovšem, když místo přesného postupu bourání budete vypisovat pouze minimální počet jednotek energie, kterou je nutno ke zbourání použít.

Formát vstupu: Na vstupu na prvním řádku dostanete dvě čísla VN – výšku komínu a počet bomb. Na dalších N řádcích jsou vždy dvě čísla widi udávající váhu a sílu bomby i. Dále platí:

Ilustrace: Na hrocha asi spadla cihla…

  • 1 ≤ V ≤ 10 000
  • 1 ≤ N ≤ 10 000
  • 1 ≤ wi ≤ 100 000
  • 1 ≤ di ≤ 10 000
  • Pro několik prvních vstupů platí, že bomby dohromady zničí přesně V metrů.

Formát výstupu: Na výstup vypište jediné číslo udávající minimální námahu, se kterou je možno komín zbourat.

Ukázkový vstup:
12 3
4 6
2 2
12 4
Ukázkový výstup:
108

Nejdříve použijeme první bombu, stojí nás 12 ·4 = 48 jednotek energie, komín po ní bude mít výšku 6. Poté použijeme druhou, stát nás to bude 6 ·2 = 12, z komínu zbudou 4 metry. Nakonec třetí bombu, k použité energii přičteme 4 ·12 = 48, celkem jsme tedy využili 108 jednotek energie a z komínu nic nezbylo.

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Přesný formát vstupu a výstupu, povolené jazyky a další technické informace jsou uvedeny v CodExu přímo u úlohy.

Řešení

„Ano, čtu to tady: Pán nahlásil zboření svého výstavního komínu. Podezřívá z toho svého souseda kvůli dlouhodobým sporům a protože ten jej údajně neprávem obviňuje z otrávení svého psa… Hmmm… Koukám, že jsme panu sousedovi poslali předvolání. Tak nebojte, ono se to brzy vyřeší. Ale teď zpět k vám. Jaké vy jste dneska dělal problémy?“

„Jel na motorce jako blázen, opětovně ignoroval výzvy hlídek k zastavení a po dopadení blekotal nějaké nesmysly o útěku. Možná je pod vlivem drog,“ odpovídá rázně muž z hlídky.

„Tak se na to podíváme. Dělej zase zápis,“ ukazuje na kolegu.

„Proč jste ignoroval všechny výzvy k zastavení?“

„J-já se p-p-potřeboval co-co nejrychleji d-dostat sem… a-abych n-nahlásil, c-co se stalo.“

„Pokračujte,“ vybízí policista s náznakem zvědavosti.

„V-víte, já měl vždycky h-hroznou smůlu n-na své sousedy. Už v první třídě jsem seděl v l-lavici vedle kluka, který mi k-kradl svačiny a tr-trhal o-oblečení. T-to bylo vždycky d-doma problémů, že každý t-týden roztrhnu tričko. J-já ni-nikdy nepřiznal, že to dělá on. J-jsem se b-bál na něj ž-žalovat.“

„Proboha mluvte k věci. Mě zajímá dnešek a ne váš podělanej život.“

„A-ale t-to b-byla na-naprostá pr-prkotina o-oproti tomu, c-co se stalo t-teď,“ pokračuji, jako bych policistu vůbec neslyšel.

Ilustrace: Hroch detektivem

Začalo to hned včera, jak jsem vyšel z policejní stanice. Silně pršelo, tak jsem rozevřel deštník a vyrazil. Ze stanice to mám do práce kousek, jen pár bloků. Šlo se mi těžce, protože v ulicích foukal silný vítr a zápasil jsem s rozevřeným deštníkem. Nakonec jsem jej musel naklonit před sebe, abych jím prorážel vzduch. Tím jsem si zablokoval výhled. PRÁSK! Někdo přímo přede mnou vystupoval z auta a já, nevidě před sebe, mu kovovou špičkou deštníku vyryl do dveří pořádnou rýhu.

„Ty šmejde! Tys mi zničil auto! Nemůžeš se doprdele dívat na cestu?“ ozvalo se.

Nadzvedávám deštník, abych viděl, s kým mám tu čest, a mohl se dotyčnému omluvit. Stál tam asi padesátiletý pohublejší muž s vyholenou hlavou, který byl aspoň o pět čísel vyšší než já. Byl to můj soused.

„Ty?! Ty se ještě odvažuješ plést se mi do cesty, po tom, cos mi otrávil psa? To mi teda zaplatíš! To ti jen tak nedaruju!“ pokračuje.

„Já??? Já nikoho neotrávil. A nic vám platit nebudu! Tohle byla vaše chyba. Máte se koukat, jestli tam nejsou lidi, když otevíráte dveře,“ bráním se a s úšklebkem dodávám, „kromě toho vás v dohledné době přijdou vyšetřovat kvůli tomu komínu, který mi v noci někdo zbořil.“

Soused zasupěl a odměřeným zastrašujícím tónem řekl: „Ty mě jako budeš žalovat?“

„Jestli budu? Právě jsem to udělal, protože tohle vám už dál trpět nebudu!“

Soused zrudl, prohlídl si mě očima a potichu supěl: „Tos přehnal chlapečku. Mě tady nikdo žalovat nebude. Rozumíš? Nikdo! A už vůbec ne ty! …Ty o mě ještě uslyšíš.“

Najednou začal křičet: „TY JEŠTĚ POZNÁŠ, CO JÁ DOKÁŽU A NEBUDE SE TI TO LÍBIT! NA TO SE MŮŽEŠ SPOLEHNOUT!“

Přešel chodník, ukázal směrem ke mně výhružné gesto, agresivně trhl dveřmi a zmizel ve vedlejší budově.

Nevyděsilo mě to. Naopak mi to zvedlo náladu a s pocitem zadostiučinění jsem pokračoval v cestě do práce. Konečně dosáhnu spravedlnosti! V duchu jsem si představoval policejní důstojníky klepající na dveře souseda a jak mi přímo on dává do ruky peníze za způsobenou škodu. Nebo ještě líp, dostává příkaz k vystěhování.

S takto dobrou náladou jsem došel do práce – dokonce přestalo i pršet. To jsem ale ještě netušil, co mě později v ten den čeká…

* * *

Z práce jdu rovnou domů. Po průchodu brankou se ještě jednou smutně podívám na hromádku cihel, která mi zbyla po komínu. On to totiž nebyl jen tak obyčejný komín. Byl to umělecky navržený výstavní komín, který jsme vlastnili už po dvě generace a ke kterému se pojí nejedna vzpomínka. Například když do něj můj mladší bratr zapadl při hře na schovávanou a přes dvě hodiny jsme jej nemohli najít. Nebo méně veselá historka: jak se nám z něj šířila plíseň do vedlejších záhonů a museli jsme se jí celý víkend zbavovat různými chemikáliemi.


Praktická opendata úloha28-1-5 Likvidace plísně (10 bodů)


Na zahradě nám vyrostlo N hromádek mnohavrstvé plísně. Té bychom se chtěli co nejrychleji zbavit. K tomu máme plošný postřikovač naplněný přípravkem proti plísním. V jednom kroku můžeme buď použít postřikovač a zničit tak jednu vrstvu plísně z každé hromádky, nebo vzít několik vrstev z jedné hromádky a dát je na jinou (klidně i novou) hromádku. Hromádek takto můžeme vytvořit kolik chceme.

Napište program, který spočítá, v kolika nejméně krocích je možné se zbavit celé plísně.

Formát vstupu: Na prvním řádku vstupu dostanete číslo N udávající celkový počet hromádek plísně. Na druhém řádku dostanete čísla v1, …, vN udávající počet vrstev na jednotlivých hromádkách.

  • 1 ≤ N ≤ 10 000
  • 1 ≤ vi ≤ 10 000

Formát výstupu: Na výstup vypište jedno celé číslo udávající minimální počet kroků, v jakém je možné se plísně zbavit.

Příklad: Máme-li tři hromádky o počtech 9, 3 a 3, je nejlepší nejdříve dvěma přesuny z první hromádky vyrobit tři po třech plísních, a pak všech pět třemi postřiky vyhubit.

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Řešení

Věnoval jsem hromádce cihel další, poslední pohled, když vtom mě popadla zlomyslnost. Proč já mám mít na zahrádce hromadu cihel a ten, kdo ji zničil, pořádek? Ať si soused taky trochu vychutná svou vlastní práci! Vzal jsem několik kusů a hodil je přes plot.

Jednu do růží. Jednu do okurek. Další mezi chryzantémy. Pak jednu do rajčat. Do umělého bazénu a poslední jsem zničil psí boudu. Stejně už toho blbýho čokla nemá. Haha! Takhle už jsem se dlouho nebavil!

Když jsem se vydováděl, šel jsem domů. Po namáhavém dni se natáhl na pohovku, pustil televizi a usnul. Spalo se mi krásně a klidně, ale nevydrželo to dlouho. Probudila mě obrovská rána, která šla z mojí kuchyně. Cože? Nebyl to sen? Nebyl, hned vzápětí se ozvala další, ještě větší!

Celý zmatený spadnu z pohovky na zem a snažím se vzpamatovat. Co se děje? Najednou oknem proletí velký, těžký předmět. Dopadne přímo do zapnuté televize a ta se celá rozpadne.

Ten magor mi hází do domu cihly! Další letěla přes pohovku a roztříštila skleněný stolek přímo přede mnou. Letící střepy mi pořezaly tvář, ruce a pravou nohu. Naštěstí jsem stihl zavřít oči.

Tohle už došlo moc daleko! Tady jde o život! Musím něco udělat dřív, než sem hodí další a stane se něco fatálního.

„Sousede! Dost! Chci se usmířit! Tohle už se nám vymklo z rukou!“ křičím.

Další rána, tentokrát z koupelny.

„Dost! To auto ti zaplatím! Zahradu taky! Jenom už mi prosimtě přestaň ničit barák.“

Nastala chvíle klidu. Z okna se ozve sousedův vyrovnaný hlas: „Ty si vážně myslíš, že penězi se dá něco urovnat po tom, co jsi proved'? Tak pojď ven a zkus to. Čekám na tebe.“ „A ať tě ani nenapadne volat pomoc, pár cihel mi tady pořád zbývá!“ dodal.

Seděl jsem na místě a přemýšlel, co mám dělat. Vzhledem k okolnostem mluvil soused až překvapivě klidně a to mě zneklidňovalo. Takto klidného ho neznám. Nakonec jsem se vyhrabal ze střepů a vydal se do ložnice pro peníze. Šel jsem opatrně, u zdi a při tom se pořád ohlížel po oknech. Vzal jsem peníze a zamířil na chodbu. Všude byl naprostý klid a po sousedovi žádné známky.

„Sousede, jsi tam?“ volám směrem ke dveřím.

Ticho, žádná odpověď. Že by bylo po všem? Že by si uvědomil váhu svých činů a šel domů? Radši se ještě podívám ven, abych měl jistotu.

„Jdu ven!“ volám.

Přistupuji ke dveřím, opatrně beru za kliku a pomalu otvírám. Rozhlížím se. Nikde jej nevidím. Pomalu a tiše dělám krok směrem ven. Druhý. Třetí.

Náhle mi ztuhnou ruce i nohy. Zvláštním způsobem mě zabrní celé tělo a padám na zem. Nemůžu se hnout. Jsem v jedné velké křeči. Nad sebou vidím stát souseda a pomalu se mi udělá temno před očima. Tak takový je to pocit… když vás někdo uzemní paralyzérem.

* * *

Ležím na tvrdé, nepohodlné, studené podložce a pomalu se probírám. Třeští mi hlava. Rozhlížím se a snažím se zjistit, kde to jsem. Jsem v potemnělé místnosti s jedním menším oknem, kterým prosvítá měsíční světlo. Ze všech stran kolem mě jsou mříže. Jsem zavřený v kleci.

Na zdech visí spousta různých středověkých nástrojů.
Nůžky mnoha velikostí, kladivo zakončené hřebíky, řemdih, pouta… Na věšáku visí svěrací kazajka a v opačném rohu místnosti stojí… to je opravdu skřipec?

Jsem v mučírně. To nemůže být pravda! To je jenom sen! Hlava mi stále třeští, že nejsem schopný si ani kleknout. Tiše ležím na zemi a čekám, co se bude dít. Asi po půl hodině vchází soused.

„To je ale překvapení! Pán se nám konečně probral!“ zvolal s mírným nadšením v hlase. „To si spolu konečně můžeme užít trochu legrace,“ řekl a usmál se na mě. Pak hned zvážněl a zeptal se přísně: „Víš, proč jsi tady?“

Mlčím. Nejsem schopný slova. Vyčkávám. Najednou se mu v ruce objeví zbraň a střelí mě do paže.

„Na něco jsem se tě ptal!“

„Au!“ chytám se za paži. Nekrvácí. Ale nahmatávám pod kůží zarytou kuličku. Má airsoftku. A nepříjemně silnou!

„Neslyšíš, nebo co?“ střelí mě znova, tentokrát do břicha, „ptal jsem se, jestli víš, proč jsi tady!“

„Jo, tuším!“ chytám se za břicho a vzdychám, „asi kvůli vašemu autu a těm cihlám, co jsem k vám hodil. Omlouvám se! Všechno zaplatím! Jen už do mě prosim nestřílejte!“

„Špatně!“ zaburácel podrážděně a trefil mě do ramene, „za těma chryzantémama,“ rána do holeně, „na kterých ses vydováděl,“ rána pod lopatku, „si hrála moje vnučka!“ završil přímou ranou do čela.

Choulím se v bolestech na zemi. Nedokáži se natočit tak, aby mě nic nebolelo. On zatím odkládá zbraň. Vnučka? On měl nějakou vnučku? Ani jsem nevěděl, že měl ženu nebo děti.

„Dokážeš si představit, co se stane se čtyřletou holčičkou, když na ni dopadne cihla???“ dal hlavu co nejblíž mřížím a potichu a chladně pokračoval, „že nedokážeš? Tak počkej pár hodin a já ti to pomalu a velmi, velmi přesně ukážu.“

Odstoupil několik kroků, sedl si na židli a pozoroval mě svým chladným výrazem. Byl jsem šokován. Otřesen vším, co mi právě řekl, jsem zapomněl na všechny své bolesti a hlavou mi začala probíhat spousta nepříjemných otázek.

Opravdu měl vnučku? Opravdu bych ji přehlédl? Vždyť ta cihla dopadla přímo doprostřed záhonu, tam nikdo nemohl být! A nebo jen chci, aby to tak bylo, a ve skutečnosti jsem v rozrušení nedával pozor, kam co házím? Jak může mít vnučku v domě, kde má mučírnu? Jsme vůbec u něj doma? Jak dlouho jsem byl mimo po zásahu paralyzérem? Nevymyslel si svou vnučku, jen aby teď sledoval mě, užírajícího se pocitem viny? Ale co když si ji nevymyslel? Jak já s tím teď budu žít? Budu vůbec žít? Jak to myslel, že mi to pomalu a přesně ukáže? To mě plánuje něčím rozmáčknout?

Na žádnou z těch otázek jsem neuměl odpovědět a postupně padal do hlubšího a hlubšího pocitu agonie, který jsem doprovázel tichým sípáním. Soused mě neustále bedlivě sledoval. Pak se zvedl, přistoupil ke kleci a hodil mi nějaký ovladač s displejem a tlačítky.

„Na, vem si to. Sleduj displej. Když zasvítí zeleně, musíš zadat správné číslo.“

„Bav se. Musím si teď na tebe něco připravit,“ a odešel.


Teoretická úloha28-1-6 Úloha z ovladače (12 bodů)


Držíte v ruce ovladač, na jehož displeji se postupně objevují čísla. Jakmile displej zasvítí zeleně, musíte zadat nejmenší z posledních K čísel, které jste viděli. Toto číslo K je pevně dané.

Navrhněte datovou strukturu, která bude umět efektivně zpracovávat následující dvě operace: přidání prvku a vypsání nejmenšího z posledních K přidaných prvků.

Plný počet bodů můžete získat za řešení, které potřebuje průměrně konstantní čas na dotaz. Tedy některé operace struktury můžou být pomalejší, ale posloupnost D operací zabere čas O(D). Bonusové body můžete získat za řešení, které potřebuje konstantní čas na každý jeden dotaz.

Řešení

Dělal jsem, jak řekl. Sledoval čísla na displeji. Najednou zasvítil zeleně. Rychle jsem něco zadal a potvrdil. V tu chvíli nade mnou něco zavrzalo a strop klece klesl asi o tři centimetry. Neee! Tak takovou já tady hraji hru. Takhle to myslel! Vždyť já vůbec nevim, co tam mam zadávat!

Během mého panikaření na displeji proběhlo dalších několik čísel a opět zezelenal. Zkusím nedělat nic, třeba to nezareaguje! Asi čtvrt minuty byl klid. Pak displej zablikal červeně a strop se znova snížil. Tentokrát asi o deset centimetrů.

To je ještě horší! Musím se teda snažit hrát. Vždy chvíli čekám a zkouším zadávat různá čísla. Nikdy jsem se netrefil a strop stále pomalu klesal. To je naprosto beznadějný, takhle nikdy nemám šanci nic uhodnout. A jde to vůbec? Nemá mi to jen dávat falešnou naději na moji záchranu? Padám do hluboké deprese a už prostě jen zadávám nějaká čísla, nevnímaje jaká.

Strop klece se již dostal tak nízko, že jsem si musel lehnout. Už jen pár poklesů a bude po všem. Už jen pár poklesů a nebude mě nic trápit. Strop už je tak blízko, že cítím narezlé železo, které ke mně stále klesá.

Hluboce dýchám. Snažím se každý další pokles nevnímat, ale nejde to. Zavřu oči a odhodím krabičku. Prosím, ať už to skončí! Já chci mít klid! Mříže naposled zavržou a zastaví se přesně ve výšce, že se jich má prsa při každém nádechu dotýkají. Dál se nic neděje. Otevřu oči. Mříže jsou až u mě. Mám tak málo místa, že se sotva můžu pohnout.

Najednou se za mnou zableskne a začnou se ozývat kroky. Už je zas tady! A má s sebou oheň. Já nesnášim oheň! Mám z něj panickou hrůzu! Vydávám vyděšené povzdechy. Představa upálení je pro mě naprosto zničující. To je ta nejhorší možná smrt, co může být!

Není to soused. Po místnosti se prochází neznámý muž asi po třicítce. V ruce drží pochodeň, rozhlíží se všude kolem a pečlivě si prohlíží předměty na zdech. Kdo to je? Je to snad otec sousedovy vnučky, který se mi taky přišel pomstít? Vybírá si teď vhodný mučící nástroj, kterým mi znepříjemní poslední hodiny života?

Sebral ze zdi dlouhé nůžky, kterými by se dalo ustřihnout i celé zápěstí a udělal pár kroků směrem k východu. Najednou se otočil a zadíval se na mě. Zastavil se mi dech. Vystrašeně se dívám jeho směrem a ležím bez nejmenší známky pohyblivosti. Vykročil směrem ke mně. Vyskočil na klec a skrčil se. Stále ty obrovské nůžky držel v ruce. Snažím se nemyslet na to, co s nimi hodlá dělat, ale nejde to. Furt dokola mi hlavou probíhá, jestli víc bolí ustřižené zápěstí, anebo prostřižené stehno.

Muž si nůžky strčil za opasek, koukl se na své moderní hodinky a něco na nich nastavil. Z hodinek vylezla dlouhá žhavá jehla. Tu vzal a začal s ní objíždět mříže. Mě se ani nedotkl, aspoň zatím. Dokončil okruh, škubl za mříže a vyrval je.


Teoretická úloha28-1-7 Vyříznutý kus mříže (10 bodů)


Ve čtvercové mřížce je nakreslený mnohoúhelník s N vrcholy, které jsou umístěny přesně v mřížových bodech. Navrhněte algoritmus, který na vstupu dostane souřadnice bodů mnohoúhelníka (v pořadí na obvodu) a spočítá, kolika mřížovými body prochází jeho strany.

Řešení

Stále nehybně a vyčerpán ležím. Bojím se jakkoliv zareagovat. „Uteč!“ pošeptá mi, zvedne pochodeň a začne odcházet.

Nevěře, co se právě stalo, se pomalu zvedám a podezřívavě se dívám na muže. Jen aby to nebyla nějaká hra, dávající mi falešnou naději na svobodu. Vtom do dveří vejde soused.

„C-cože? Kdo jsi a co tady děláš?“ napůl překvapeně a napůl vyděšeně křičí na muže a začne jej ohrožovat pěstí.

Muž jej tvrdě odstrčí ke zdi a utíká ven. Soused hned vyrazí za ním a natahuje po něm ruku. Vtom za rohem zablýskne ostré světlo a soused začne neuvěřitelně řvát. Řval, jakoby mu tloukli hřebíky do kolen. Byl to takový úzkostný a dávivý řev, jaký jsem nikdy předtím neslyšel.

Já přestal na cokoliv čekat a zamířil k východu. Má záchrana bylo to jediné, co mě zajímalo.

Dobelhal jsem se do vedlejší místnosti. Tam se v rohu v bolestech svíjel zakrvácený soused. Chyběla mu půlka paže a z rány stříkala tmavě rudá krev. Prošel jsem místností, jak rychle to jen šlo, a začal hledat východ z domu.

Venku byla naprostá tma. U branky bylo zaparkované auto a vedle motorka. Po neznámém muži ani stopy. Bez rozmýšlení jsem sedl na motorku a ujížděl pryč. V hlavě mi zůstala jen jedna myšlenka a tou byl ÚTĚK!

Karel Tesař


Seriálová úloha28-1-8 Programování podle Darwina (15 bodů)


V letošním seriálu se budeme věnovat přírodou inspirovaným algoritmům, jakými jsou například evoluční algoritmy či neuronové sítě. Téma je velmi široké a obsahuje v sobě velkou spoustu postupů, ze kterých my se budeme věnovat jen těm základním a často používaným.

Úvod do evolučních algoritmů

Proč se vlastně informatici snaží přírodou inspirovat? Jednak určitě hraje roli motivace vyzkoušet si něco neobvyklého, ale jedním z hlavních důvodů je, že tradičními (exaktními) informatickými postupy mnoho problémů neumíme vůbec řešit. Přitom příroda má v zásobě spoustu poměrně silných a obecných technik pro řešení problémů, nepodobných čemukoli, na co jsme v informatice zvyklí. A při pohledu na výsledky se zdá, že fungují docela dobře. Patří mezi ně třeba právě proces evoluce (který je vlastně takovým algoritmem na hledání nejschopnějších forem života).

Nabízí se tedy otázky: „Mohly by nám tyto techniky nějak pomoci při řešení těžkých algoritmických problémů?“, „Dají se jednoduše popsat, nebo dokonce naprogramovat?“, „Dokážeme naprogramovat mravence, kteří by společně namísto stavění mraveniště hledali cestu v grafu?“, „Může se i počítač pomocí simulace neuronů něco naučit?“ a tak dále. Ukazuje se, že odpovědí na většinu těchto otázek je: „Ano, je to možné!“

To všechno vypadá skvěle! Ale možná si teď někteří z vás pro sebe řekli: „Budu já tomu rozumět? Já biologii moc neumím.“ Tak toho se přesně nemusíte bát. Všechny algoritmy, kterým se během seriálu budeme věnovat, se přírodou pouze inspirují. To znamená, že sledují nějaké její základní chování, a pak si jej vysvětlí svým informatickým způsobem. Tedy prakticky žádné biologické znalosti nejsou potřeba.

Evoluční algoritmy – část 1

Prvních několik dílů seriálu se budeme věnovat evolučním algoritmům. V tomto díle si konkrétně popíšeme a naučíme se používat vůbec první typ: takzvaný genetický algoritmus. Řekneme si, čím je motivován, podrobně popíšeme jeho hlavní části a pokusíme se pomocí něj vyřešit pár problémů. Do otázek ohledně toho, proč by takový algoritmus vůbec měl mít šanci fungovat, zatím nebudeme příliš zabíhat – ty si necháme na příště.

S genetickým algoritmem poprvé přišel John Holland v roce 1970. Genetický algoritmus je inspirován myšlenkou evoluce. V přírodě platí pravidlo „silnější přežijí,“ což znamená, že nejsilnější jedinci obstojí v konkurenci ostatních, reprodukují se a zvládnou tak přenést své geny do dalších generací. Tím v každé další generaci dostáváme lepší jedince, protože nám zůstanou geny jen těch, kteří dokázali přežít.

Dále budeme předpokládat, že výkonost jedince ovlivňují pouze jeho geny a nic jiného (tomu se v biologii říká darwinismus). Tento předpoklad znamená, že při reprodukci jsou potomci a jejich vlastnosti závislí pouze na genech rodičů a ne na jejich životních zkušenostech. Nyní se pojďme podívat, jak vypadá nějaký informatický genetický algoritmus.

Genetický algoritmus sestává z populace jedinců, funkce ohodnocující výkonost těchto jedinců (fitness funkce) a tří hlavních genetických operátorů pro manipulaci s jedinci: selekce, kříženímutace. V dalším textu si tyto jednotlivé části podrobněji popíšeme.

Jedinec je tvořen posloupností genů, která představuje nějaké řešení našeho problému. Je důležité, aby tato posloupnost měla danou fixní délku. Zatím navíc budeme předpokládat, že tato posloupnost je binární (skládá se pouze z 0 a 1). Pro binární soustavu dokážeme jednoduše popsat další operátory.

Fitness funkce ohodnocuje výkonost (kvalitu) jednotlivých jedinců. Jinými slovy říká, jak jsou jedinci dobří pro řešení našeho problému. Zpravidla vyhodnocuje tak, že vyzkouší, jak dobře genetický kód jedince řeší zadaný problém a ohodnotí jej reálným číslem.

Selekce

Pomocí selekce vybíráme, které jedince použijeme pro vytvoření další populace. Bereme přitom v úvahu fitness jedinců, ale zároveň ponecháváme i určitou míru náhody. My si uvedeme dva druhy selekcí: ruletovou selekciturnajovou selekci.

Ruletovou selekci si představíme jako opravdovou ruletu. Máme kruh rozsekaný na různě velké části, kde každá odpovídá jednomu jedinci. Velikost části kruhu je přímo úměrná fitness jedince. Do rulety pak hodíme kuličku a vybereme toho jedince, v jehož části kulička skončí. Tento proces opakujeme tolikrát, kolik jedinců potřebujeme vybrat. Nevadí nám, pokud jednoho jedince vybereme vícekrát (V přírodě by to sice nešlo, ale my si to v informatice klidně můžeme dovolit a jednoho jedince si nakopírovat, kolikrát chceme.).

V praxi je ruletová selekce počítána tak, že se vygeneruje náhodné číslo od 1 do součtu všech fitness a podle toho se vybere příslušný jedinec. Z toho důvodu je pro ruletovou selekci nutné, aby fitness funkce byla vždy kladná.

Pak ale existuje ještě turnajová selekce, u které hodnoty fitness funkce mohou být libovolné. Ta funguje tak, že vezme dva náhodné jedince a z nich vybere toho s lepší fitness. To opět zopakuje tolikrát, kolik chceme vybrat jedinců. (Turnajová selekce nemusí vždy vybírat jen lepšího ze dvou jedinců, ale klidně obecně nejlepšího z k jedinců.)

Křížení

Křížení je jedním z nejdůležitějších genetických operátorů. To vezme dva jedince a nějakým způsobem je zkombinuje. Nejčastěji se používá takzvané jednobodové křížení, které vybere náhodný bod, tam jedince rozpůlí a prohodí jejich druhé části. Obdobně také funguje dvoubodové křížení, které náhodně zvolí dva body a pak prohodí tu část jedinců, která je mezi nimi.

Také se může použít křížení, které se pro každý bit zvlášť rozhodne, zda jej prohodí nebo ne. Takové křížení se ale pro některé problémy moc nepoužívá. Později si sami můžete vyzkoušet, které z křížení vám bude fungovat lépe.

Křížení se neaplikuje na všech jedincích, ale probíhá s pravděpodobností pk, která se obvykle pohybuje od 0,7 do 0,9. Křížení se často považuje za hlavní pohon genetických algoritmů. Na druhou stranu existuje mnoho verzí a odvození, které křížení vůbec nezahrnují.

Mutace

Mutace je operátor, který náhodně změní jednoho jedince. To jest každý bit s nějakou malou pravděpodobností změní. Tato pravděpodobnost je často volena kolem 1/d, kde d je délka jedince. Taková volba pravděpodobnosti způsobí, že během mutace v průměru prohodíme právě jeden bit jedince. Mutace se na jedince aplikuje s pravděpodobností pm, která se obvykle volí v rozmezí 0,001 až 0,05.

Poslední pojem, který si definujeme, je generace. Generací je myšlena populace, která existuje v jedné iteraci. Na začátku máme generaci 0, z té je pak pomocí selekce, křížení a mutace vytvořena generace 1, z té pak generace 2 a tak dále. Předchozí generace vždy celá umírá a dále se používá pouze nová generace.

Pseudokód algoritmu

Nyní jsme si představili všechny důležité části genetického algoritmu, tak se pojďme podívat, jak dohromady fungují. Zde je pseudokód algoritmu.

  1. Vygeneruj náhodných n jedinců velikosti d do generace 0 a spočítej jejich fitness.
  2. t = 0
  3. Opakuj následující:
  4. Pomocí selekce vyber m jedinců z generace t.
  5. Na každého z těchto m jedinců aplikuj křížení s pravděpodobností pk.
  6. Na každého dále aplikuj mutaci s pravděpodobností pm.
  7. Spočítej fitness výsledných jedinců a nejlepších n prohlaš za generaci t + 1.
  8. t = t + 1

Jelikož využíváme náhodu, vyplatí se algoritmus pustit několikrát za sebou a ze všech běhů vzít ten nejlepší výsledek. Při každém běhu začínáme s jinak nagenerovanou počáteční populací, a tedy můžeme získat i jinak dobré řešení.

A to je celé. Poslední, co zbývá říct, je, kdy se algoritmus zastaví. To může být buď ve chvíli, kdy vyvineme jedince reprezentujícího optimální řešení problému (tj. s maximální možnou fitness, pokud ji známe) nebo po určitém počtu iterací. Často se také zohledňuje počet vyhodnocení fitness funkce, protože právě ta bývá tou časově nejnáročnější částí algoritmu. Ta se ale v našem případě pustí v každé iteraci právě m-krát, takže výpočet budeme řídit počtem iterací a velikostí populace. (m ≥ n, ale často m = n)

Elitismus

Než si algoritmus vyzkoušíme, zmíníme ještě poslední věc. V algoritmu, tak jak jsme jej popsali, se lehce může stát, že během přesunu na další generaci přijdeme o nejlepšího jedince – můžeme jej nevybrat, může se špatně zkřížit a může zmutovat. Z tohoto důvodu se do algoritmu přidává ještě další vlastnost, která se jmenuje elitismus. Ta funguje tak, že do výběru pro generaci t + 1 přidáme ještě pe  · n nejlepších jedinců z generace t. Tím určitě zachováme doposud nejlepší geny. Hodnota pe se obvykle volí maximálně 0,1. Nemůžeme brát moc velkou část, protože pak by nám celá populace postupně konvergovala jen k jednomu aktuálně nejlepšímu jedinci.

Nyní si algoritmus pojďme vyzkoušet. Protože genetické algoritmy obsahují mnoho parametrů, které se musí správně nastavit, aby dobře fungovaly, ladí se nejdříve na jednoduchých problémech. Na takových, na kterých je dobře vidět, jak algoritmus funguje, a pro které umíme efektivně vyhodnocovat fitness funkci. My se pokusíme navrhnout genetický algoritmus, který se bude snažit vyvinout posloupnost samých jedniček.

Pro takový problém je fitness funkce jednoduchá – prostě jen spočítá, kolik jedniček jedinec obsahuje. Selekce, křížení a mutace fungují přesně tak, jak je popsáno výše. Zbývá vyladit parametry: velikost populace n, počet iterací t a hodnoty pk, pm, pe. Vaším úkolem teď bude si různé kombinace těchto parametrů vyzkoušet a zjistit, jak se algoritmus chová.

Úkol 1 [6b]

Pomocí genetického algoritmu vyviňte posloupnost samých jedniček. Tedy začněte s populací náhodných jedinců a pomocí genetického algoritmu se snažte vyvinout jedince, který je složen pouze z jedniček.

Vyzkoušejte to pro velikosti jedince d = 20, 100, 500. Zkuste různé velikosti populace a různé kombinace pravděpodobností. Jak se algoritmus chová?

Sledujte, jak se během výpočtu mění maximální a průměrná fitness generací.

Vyzkoušejte si také napsat nějaký vlastní způsob křížení nebo mutace. Jak to bylo úspěšné? Tato křížení a mutace by neměly nijak záviset na znalosti řešeného problému. Cílem je odladit operátory, které by pak mohly fungovat i pro jiné, už ne tak jednoduché problémy.

Vyzkoušejte také, jak je algoritmus úspěšný, pokud má vyvinout jedince, kde se 0 a 1 střídají. (Přičemž je jedno, čím se začne.) Mělo by stačit změnit fitness funkci. Funguje váš algoritmus stále stejně dobře?

Během řešení můžete použít naše šablony genetického algoritmu ze stránky k evolučnímu seriálu.

Odevzdávejte soubor typu zip s popisem řešení, průběhem algoritmu a pokud chcete, tak i se zdrojovým kódem. V popisu rozeberte, co jste zkoušeli a jaké jste použili parametry, aby algoritmus byl co nejlepší.

Průběhem algoritmu je myšlen textový soubor, kde na každém řádku budou mezerou či tabulátorem oddělené hodnoty: číslo generace, hodnota průměrné fitness, hodnota maximální fitness. Nemusíte logovat každou generaci, stačí každá desátá.

Tím jsme si vyzkoušeli, jak se genetický algoritmus ladí na jednoduchém problému. Často při vymýšlení nového operátoru či dokonce celého algoritmu se hodí jej nejdříve vyzkoušet a odladit na něčem takto jednoduchém. To se především týká operátorů, které jsou nezávislé na řešeném problému. O takové operátory se snažíme, protože je pak můžeme aplikovat i na složitější problémy.

Někdy ale můžeme znalost řešeného problému využít a přímo ji zahrnout do genetických operátorů, jako jsou křížení nebo mutace. To na jednu stranu může značně urychlit výpočet, na druhou stranu nás to ale může v řešení zahnat někam do suboptimálního řešení, ze kterého se nebudeme moci dostat.

To vše si vyzkoušíme na problému sedmi loupežníků. Skupinka sedmi loupežníků vyloupila vesnici a získala z ní dohromady d předmětů, každý z nich ohodnotila nějakou cenou. Vaším úkolem je tyto předměty rozdělit na 7 hromádek tak, aby jejich součet byl co nejbližší. Konkrétně tak, aby rozdíl nejhodnotnější a nejméně hodnotné hromádky byl co nejmenší.

Než se pustíme do řešení, musíme vyřešit několik problémů: Jak budeme kódovat jedince? Jak v tomto kódování bude fungovat křížení a mutace? Jak zvolit fitness funkci?

Jedinci budou délky d a budeme je kódovat čísly 0, 1, …, 6. Pokud na i-té pozici máme číslo 4, tak to znamená, že i-tý předmět přidělíme do hromádky 4. Křížení může fungovat stejně jako s binárními jedinci a mutace změní číslo na náhodnou hodnotu od 0 do 6 namísto překlopení bitu. To, jak dobře tyto operátory budou fungovat, je jiná otázka.

A co s fitness funkcí? V tomto případě máme za úkol minimalizovat rozdíl největší a nejmenší hromádky. Náš genetický algoritmus se ale snaží fitness funkci f maximalizovat a ne minimalizovat.

U turnajové selekce problém můžeme vyřešit jednoduše – prostě použijeme hodnoty -f(x) namísto f(x). Co ale dělat, pokud chceme použít ruletovou selekci? Tam všechny fitness navíc musí být kladná čísla. Máme několik možností, jak toho dosáhnout. Často se používá hodnota 1/(f(x) + 1) namísto f(x). Nebo hodnota A - f(x) pro vhodně zvolené A tak, že výsledné hodnoty určitě budou kladné. Musíme ale dát pozor, aby A nebylo příliš velké, protože pak by výsledné hodnoty byly příliš blízko u sebe a z pohledu ruletové selekce byly „skoro stejné“.

Tím jsme si poradili se všemi problémy a tedy genetický algoritmus můžeme zkusit použít.

Úkol 2 [9b]

Pomocí genetického algoritmu řešte problém sedmi loupežníků pro data, která naleznete na stránce se šablonami. Data jsme vygenerovali troje: lehká, střední a těžká. Doporučujeme je řešit postupně. Tj. až si budete myslet, že máte dost dobré řešení pro lehká data, zkuste, jak vám algoritmus funguje pro střední, atd.

Na prvním řádku dat jsou dvě celá čísla: počet loupežníků (vždy 7) a počet nakradených věcí D. Na druhém řádku je D mezerou oddělených čísel udávajících váhy jednotlivých věcí.

Opět zkoušejte různé kombinace parametrů. Také si vyzkoušejte, jak nejlépe převést fitness funkci na maximalizační – můžete vymyslet i vlastní způsob nebo nějaké modifikace způsobů popsaných výše.

Nalezněte co nejlepší řešení daného problému. Můžete použít i vlastní genetické operátory, které libovolně využívají znalost problému a provádějí křížení nebo mutace „cíleně“ na specifických částech jedinců.

zipu odevzdejte nejlepší vyvinuté řešení společně s popisem, jak jste jej dosáhli a proč si myslíte, že takový postup funguje. Také můžete přidat záznam průběhu řešení (jako v minulé úloze).

Při řešení obou úloh můžete upravit námi vytvořenou šablonu v jazycích C++, Java, …, anebo použít svou vlastní.

Naše kódy obsahují základní verzi genetického algoritmu se všemi jeho částmi. Navíc logují, jak se během výpočtu mění průměrná a maximální fitness, a ukládají doposud nejlepšího vyvinutého jedince.

Karel Tesař

Řešení