Třetí série šestnáctého ročníku KSP

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

Milí řešitelé!

Do ruky se Vám dostává již třetí letošní zadání našeho semináře. S touto sérií přichází také několik změn. Jednak jsme se rozhodli, že letošní ročník bude mít pouze čtyři série, a proto jsme zvedli počet úloh v sérii na šest.

Další změna se týká toho, že jsme se rozhodli přijímat Vámi vypracovaná řešení i elektronickou cestou. V žádném případě se ovšem nejedná o nahrazení stávajícího způsobu odesílání Vašich řešení! Spíše jde o jakýsi zkušební provoz a podle toho, jak dopadne, se zařídíme v časech budoucích.

Pokud se rozhodnete využít tohoto způsobu odevzdávání řešení, pak vězte, že úlohy se budou odevzdávat přes webové rozhraní na http://ksp.mff.cuni.cz/submit/. Zde se také dozvíte o konkrétních pravidlech pro odevzdávání Vašich řešení. Doporučujeme Vám si tato pravidla přečíst, pokud hodláte odevzdat svá řešení přes webové rozhraní, abyste nebyli na poslední chvíli zaskočeni.

Ať už pošlete řešení jakkoliv, zpět Vám přijdou normální poštou. Řešení, která přijdou elektronickou cestou, si totiž vytiskneme a opravíme tradičním způsobem. Ale ještě jednou bychom rádi zopakovali, že vypracovaná řešení můžete i nadále posílat normální poštou na naši nezměněnou adresu (najdete ji na konci zadání této série).

Zadání úloh

16-3-1 Fyzikova blecha (10 bodů)

Newtoon trénuje svoji blechu na bleší turnaj. Ten probíhá na svislé stěně, na které jsou vodorovné plošinky. Cílem blechy je slézt ze startovací polohy co nejdříve na podlahu. Pohyb blechy závisí na tom, zda je blecha na nějaké plošince, či padá. Pokud padá, klesne za jednu blechovteřinu o jeden blechometr. Pokud je na plošince, posune se za  jednu blechovteřinu o jeden blechometr vlevo či vpravo.

Závod tedy probíhá tak, že blecha padá, padá, až dopadne na plošinku. Pak se rozhodne (nebo jí její majitel přikáže), zda půjde doleva nebo doprava, a jde, dokud nedojde na konec plošinky. Z ní pak seskočí a zase padá, dokud se nedostane na podlahu. Vítězí blecha, která přistane na podlaze jako první. Ovšem je nutné, aby žádná blecha nespadla z větší výšky než v blechometrů, jinak se totiž po dopadu urazí a odmítne pokračovat v závodě.

Newtoon již vytrénoval svou blechu tak, že ho poslouchá na slovo. Problém je ten, že sám neví, jak blechu navigovat, aby prošla bludištěm nejkratší možnou cestou. Protože Vás ale zajímá, jak vypadá blecha, která poslouchá, rozhodli jste se Newtoonovi pomoci.

Na vstupu dostanete jednak počáteční souřadnice blechy (v celých blechometrech), v, což je největší výška, ze které může blecha spadnout, aby se neurazila, a N, což je počet plošinek na stěně. Dále dostanete popis N plošinek, u každé plošinky souřadnice jejího horního dolního rohu a její šířku (vše opět v celých blechometrech). Všechny plošinky jsou vysoké jeden blechometr a žádné dvě se nedotýkají. Blecha je na podlaze, pokud se nachází na souřadnicích [x;0], kde x je libovolné celé číslo.

Výstupem Vašeho programu je nejmenší počet blechovteřin, které bude blecha potřebovat, aby se dostala na podlahu. Kromě tohoto počtu vypište i počet plošinek, na které blecha dopadne, a u každé plošinky (v pořadí, jak na ně blecha dopadá) rozhodněte, zda má blecha jít vlevo či vpravo. Pokud úloha nemá řešení (moc malé v), vypište odpovídající zprávu.

Příklad: Blecha se nachází na souřadnicích [5;12], v=4, N=3. Plošinky jsou [3;8];5, [3;4];5 a [7;6];3 ([souřadnice levého horního rohu]; délka). Nejkratší cesta trvá 17 blechovteřin, blecha navštíví všechny tři plošinky a půjde vpravo na první, vlevo na druhé a vpravo na třetí navštívené plošince.

Řešení

16-3-2 Historikova past (10 bodů)

Váš přítel historik Vykopávka si na Vás přichystal, aby vylepšil Vaše (podle něj poněkud zanedbané) historické vzdělání, následující hru. Hraje se ve dvourozměrném bludišti N×M polí. V bludišti se (samozřejmě kromě zdí, ty se vyskytují v každém pořádném bludišti) nachází Theseus a Minotaurus. Abyste uspokojili svého přítele Vykopávku, musíte si tato jména nejprve zapamatovat. Theseus a Minotaurus. Theseus a Minotaurus…

Vy budete ovládat Thesea a budete se snažit dostat z bludiště ven, čili dostat se na hranici bludiště a následujícím krokem z bludiště utéct. Ovšem nikdy nesmíte narazit na Minotaura, sic bídně zhynete. Na Minotaura narazíte, pokud s ním sdílíte políčko.

Jeden tah probíhá následovně: nejprve se hýbe Minotaurus a táhne k-krát následujícím způsobem. Pokud nejsou postavy Minotaura a Thesea ve stejném sloupci, chce se Minotaurus pohnout o jedno políčko vlevo nebo vpravo, aby se Theseovi přiblížil. Pokud není na políčku, kam se Minotaurus chce posunout, zeď, skutečně se tam posune. Pokud nejsou obě postavy na stejném řádku bludiště, chce se Minotaurus pohnout nahoru či dolů opět směrem k Theseovi. Opět se na zvolené políčko Minotaurus přesune jen tehdy, není-li tam zeď. V jednom kroku provádí Minotaurus tyto pohyby v zadaném pořadí a může provést oba dva, čili se může dostat na jedno z okolních osmi políček.

Po k takovýchto krocích Minotaura se hýbe Theseus, a to na jedno ze čtyř okolních volných polí. Takto se oba střídají na tahu, dokud buď Theseus neuteče z bludiště, nebo dokud Minotaurus nedohoní Thesea.

Vaším úkolem bude najít pro Thesea nejkratší posloupnost pohybů vlevo, vpravo, nahoru, dolů, aby se dostal bezpečně z bludiště, případně říci, že to není možné.

Příklad: Pro k=2 a bludiště o rozměrech 8×10

XXXXXXXXXX
X.M......X
X........X
X........X
X...X....X    . - volné políčko
X.XXX....X    X - zeď
X....T....    M - Minotaurus
XXXXXXXXXX    T - Theseus
je nejkratší cesta z bludiště ←←→→→→→→→.

Řešení

16-3-3 Genetikova evoluce (10 bodů)

Když si Blátošlap bral ponožky ze svého prádelníku, zjistil, že se mu v něm vyvinula celá kolonie neznámých živočichů. Protože to byl genetik, jal se hned tyto živočichy zkoumat a zjistil, že i když se jedná o jediný druh, jeho zástupci jsou velmi rozmanití. Každý jedinec má totiž 30 znaků, které ho charakterizují a které se mohou měnit pouze mutací. Dalším výzkumem zjistil, že v prádelníku má N různých poddruhů (poddruhy se navzájem liší alespoň v jednom znaku), i když jeden z nich převažuje.

Ihned se dovtípil, že v jeho prádelníku došlo k evoluci. A protože ho zajímá její průběh, byli jste požádáni o vyřešení tohoto problému.

Blátošlap Vám zadá N a dále popis jednotlivých poddruhů. Každý poddruh je charakterizovaný číslem 0..230-1, přičemž i-tý bit tohoto čísla vyjadřuje, zda je i-tý z 30 znaků, které poddruh charakterizují, přítomen. Pokud bychom si číslo poddruhu napsali ve dvojkové soustavě, i-tý bit tohoto čísla je i-tá cifra (počítáno zprava od nuly) v tomto zápisu. Jinak řečeno, pokud číslo i-krát vydělíme dvěma a spočteme zbytek po dělení tohoto čísla dvěma, výsledek je i-tý bit původního čísla.

Vaším úkolem je zjistit, jaký poddruh se vyvinul z jakého, a počet mutací, ke kterým muselo při tomto vývoji dojít. Předpokládejte, že vývoj probíhal tak, že každý poddruh kromě toho, který Vám Blátošlap zadal jako první (to je ten nejpočetnější), se vyvinul právě z jednoho jiného poddruhu. Navíc první zadaný poddruh je původním prapředkem všech poddruhů v prádelníku. Dále předpokládejte, že evoluce probíhala nejjednodušší možnou cestou, a tedy počet mutací v evoluci je nejmenší možný. Počet mutací je součet všech rozdílných znaků mezi každým poddruhem (kromě prvního zadaného) a jeho předkem.

Navíc žádný poddruh v Blátošlapově prádelníku nevymřel, všechny evolucí vzniklé poddruhy přežily až do dnešní doby.

Příklad: Pro N=4 a poddruhy 0,3,7,12 je hledaná evoluce tato: poddruhy 3 a 12 se vyvinuly z poddruhu 0, poddruh 7 se vyvinul z poddruhu 3. Počet mutací, ke kterým muselo v evoluci dojít, je roven 5.

Řešení

16-3-4 Ekonomova odměna (10 bodů)

Dlouhoprst byl velmi bohatý ekonom. Jednoho dne si umínil, že by zase mohl zvýšit své jmění. Ale jak? Vždyť všichni lidé už zjistili, že jeho finanční poradenství je spíše finančním proradenstvím. A tak se rozhodl dojít za ďáblem a upsat mu svou duši za pár stříbrňáků.

Po cestě do pekla potkal skupinku pirátů, kteří se handrkovali nad truhlou plnou stříbrňáků. Dlouhoprstovi to nedalo, dal se s nimi do řeči a zjistil, že se piráti domlouvají, jak si poklad rozdělí. Již se shodli na následujícím způsobu dělení.

Řekněme, že v truhle je S stříbrňáků a pirátů je P. Piráti se očíslují, čili každý dostane právě jedno číslo od 1 do P. Pirát s pořadovým číslem P navrhne způsob rozdělení všech stříbrňáků mezi piráty (každému pirátovi včetně sebe přidělí nezáporný počet stříbrňáků). Ostatní o tomto rozdělení hlasují a pokud je jich alespoň polovina pro, návrh je přijat. V opačném případě je pirát P zabit a navrhuje pirát s číslem P-1.

Při hlasování se piráti řídí těmito pravidly: nejdůležitější je přežít. Pokud pirát ví, že v budoucnu určitě zemře, hlasuje vždy pro, nezávisle na výši svého podílu. Druhé pravidlo je zisk. Pokud má pirát v budoucnu šanci, že získá víc, než kolik je mu právě nabídnuto, hlasuje proti (ovšem jen pokud ví, že přežije). Třetí pravidlo je touha popravit co nejvíc pirátů, čili pokud pirát ví, že v budoucnu bude moci určitě získat stejný obnos, jaký je mu nabídnut, hlasuje proti. Důležité je, že se všichni piráti řídí stejnými pravidly a navzájem to o sobě vědí.

Dlouhoprst vycítil příležitost, a protože piráti se doteď nedohodli na tom, jak se očíslují, nabídl jim své finanční proradenství. Očísluje je, ale za odměnu se bude moci do rozdělování zapojit, a to s pořadovým číslem P+1. A piráti souhlasili. Dlouhoprst ovšem zjistil, že je to i nad jeho síly, a poprosil Vás o pomoc.

Váš program dostane na vstupu čísla S (počet stříbrňáků v pokladu) a P (počet pirátů). Musíte zjistit, zda může Dlouhoprst vůbec přežít a pokud ano, poraďte mu návrh rozdělení stříbrňáků mezi P pirátů takový, aby byl jeho zisk (počet stříbrňáků, které nemusí mezi piráty rozdělit) co největší.

Příklad: Pro S=100 a P=2 Dlouhoprst přežít může a jeho zisk je 100 stříbrňáků. Jeho návrh je dát oběma pirátům nula stříbrňáků. Pirát číslo 2 pro jeho návrh hlasuje, protože jinak (kdyby byl Dlouhoprst popraven) by pirát 1 hlasoval proti libovolnému jeho návrhu a on sám by byl popraven.

Řešení

16-3-5 Botanikova setba (10 bodů)

Známý botanik Konopník se rozhodl, samozřejmě z čistě vědeckých důvodů, zasít svojí nejoblíbenější rostlinu. Bohužel je pronásledován davy laiků, kteří by se rádi podíleli na sklizni, a tak je nucen zasít na poli, kde už je zaseta kukuřice, aby jeho úroda nebyla lidem na očích.

Protože ale Konopník chce, aby úroda byla co největší, rozdělil kukuřičné pole na pravidelnou síť oblastí a u každé oblasti zjistil její předpokládanou úrodnost. Ta může být i záporná, pokud daná oblast brání v pěstování na okolních oblastech. Konopník by chtěl osít jediné pravoúhlé území takové, aby součet úrodností na tomto území byl největší možný. Ovšem protože je biolog, obrátil se s tímto problémem na Vás.

Na vstupu dostanete N a M, čili šířku a délku kukuřičného pole. Dále dostanete matici N×M, jejíž hodnoty jsou úrodnosti jednotlivých oblastí kukuřičného pole. Vaším úkolem je najít podmatici (souvislou pravoúhlou oblast) takovou, že součet jejích prvků je největší možný. Pokud je takových podmatic víc, najděte takovou, která má nejmenší obsah.

Příklad: Pro pole o rozměrech 4×5 a úrodnostech

1 -1 4 5 3
-2 3 -2 -5 8
2 -4 2 1 -7
4 -3 2 1 1

má hledaná podmatice levý roh v prvním řádku a druhém sloupci, pravý dolní roh v druhém řádku a pátém sloupci.

Řešení

16-3-6 Matematikova sonda (10 bodů)

Matematici jsou zvláštní lidé a jako takovým se jim občas v hlavě zhmotní zvláštní nápady. Jako třeba vyslat sondu na Mars.

K tomuto problému je samozřejmě potřeba přistupovat systematicky. Náš matematik si nejprve studiem odborné literatury a předchozích publikovaných prací v tomto oboru zjistil, že existují dva postupy.

Chtěl by samozřejmě zvolit levnější variantu, nicméně která to je, záleží na tom, kolik koupených sond se rozbije. Proto vymyslel následující algoritmus:

Prvních k-1 sond si koupí. Pokud žádná z nich neuspěje, sondu si sám vyrobí.

Tento algoritmus mu zajišťuje, že nikdy nezaplatí víc než (2-1/k) krát tolik, kolik by musel: Nechť uspěje n-tá sonda. Pak buď n≤ k-1, pak zaplatí n jednotek, což je optimální. Nebo n≥ k, pak zaplatí 2k-1 jednotek, zatímco optimální řešení by bylo vyrobit si sondu rovnou a zaplatit pouze k jednotek.

A také si okamžitě dokázal, že tento postup je nejlepší možný. Zjevně jediná možnost, jak si volit strategii, je nějakým způsobem určit počet sond d, po jejichž zničení si sondu vyrobí. Nechť uspěje (d+1)-ní sonda, pak zaplatí k+d jednotek. Pokud by d bylo větší nebo rovno k, optimum je k, tedy by zaplatil alespoň dvakrát tolik, kolik musel. Naopak kdyby d bylo menší než k-1, optimum je d+1 a 
k+d
d+1
≥
(d+2)+d
d+1
≥ 2.

Po chvíli si však uvědomil, že by možná mohl ušetřit alespoň v průměrném případě, kdyby jednu z mincí našetřených na pořízení sondy použil jako generátor náhodných čísel. Nicméně protože je to starý zkušený profesor, přenechal vám vyřešení této úložky jako jednoduché domácí cvičení.

Vaším úkolem je tedy nalézt pravděpodobnostní strategii, pro kterou by existovala nějaká konstanta c (pokud možno co nejmenší) taková, že ať už se porouchá libovolný počet sond, profesor zaplatí v průměru nanejvýš c-krát tolik, než kolik musí.

Řešení