Čtvrtá série šestnáctého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Milí řešitelé!
Jaro se již krůček po krůčku blíží k nám. Vlastně se spíš plíží plůžek po plůžku… Pro ty z Vás, kteří i v tomto jarním čase mají chuť k řešení KSP, je tady další a v tomto roce již poslední série. S ní by Vám měla přijít i ročenka minulého ročníku.
K blížícímu se jaru patří jarní úklid. Ten se nevyhne ani našim webovým stránkám, kde brzy kromě zadání v HTML najdete i verzi pro tisk, která je ve stejném formátu jako ta, kterou právě držíte v ruce. A kromě jarního úklidu nám jaro přineslo také nového kamaráda →
Odesílání řešení po Internetu alias Poštovský panáček zatím vypadá slibně, takže bude připraven přijímat i Vaše řešení čtvrté série. Ovšem pozor na to, že je pedant a řešení přijímá jen do dne odeslání včetně.
- Termín série: 31. května 2004
- 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
- 16-4-1: Mnichova posedlost
- 16-4-2: Technologické trable
- 16-4-3: Stávka programátorů
- 16-4-4: Dlouhoprstova zapeklitá hra
- 16-4-5: Obchodníci s deštěm
- 16-4-6: Šikmá věž v Kocourkově
16-4-1 Mnichova posedlost (10 bodů)
Všichni jistě víte, co jsou to Hanojské věže. Jedná se o tři kolíky, na kterých je nasazeno celkem N disků různých velikostí. Na začátku jsou všechny disky nasazeny na krajním kolíku a uspořádány podle velikosti (dole leží největší disk). Vaším úkolem je přemístit všechny disky na jiný kolík a přitom dodržet pravidlo, že vždy musí menší disk ležet na větším.
Mnichům v Tibetu se v časech dávno minulých zjevil sám Bůhdha a slíbil jim, že až přesunou v Hanojských věžích 64 disků z jednoho kolíku na jiný, svět bude u konce. A mnichové se snaží jím zadaný úkol splnit již po tisíciletí, protože k tomu potřebují (jak jistě víte) 264-1 přesunů.
Vzhledem k tomu, že je to práce velmi jednotvárná, stalo se jednou, že do mnicha Askejťáka vstoupil démon Kazisvět, který nechce, aby svět skončil (jinak by ho už nemohl dál kazit). Mnich pod vlivem Kazisvěta přesouval disky sice podle pravidla, že menší disk musí ležet na větším, avšak vůbec nedodržoval již tisíce let stanovený postup. Poté, co Kazisvět odešel, mniši zjistili, že vůbec nevědí, jak dál. Ale Vy jistě vědět budete.
Na vstupu dostanete počet disků N. Předpokládejte, že disky jsou očíslovány podle velikosti od největšího (1) k nejmenšímu (N). Dále dostanete popis situace na Hanojských věžích (jaké disky jsou na kterých kolících; uvědomte si, že pořadí disků na kolíku je určeno vždy jednoznačně). Vaším úkolem je říci, na jaký kolík bude pro mnichy nejvýhodnější všechny disky nakonec nasadit a kolik k tomu budou potřebovat kroků. Můžete pro jednoduchost předpokládat, že počet potřebných kroků bude menší než 264-1.
Příklad: Pokud N=7 a na prvním kolíku jsou disky 6,7, na druhém kolíku disk 5 a na třetím kolíku disky 1,2,3,4, je pro mnichy nejvýhodnější přemístit všechny disky na kolík číslo tři. Dokážou to pomocí čtyř přesunů.
16-4-2 Technologické trable (8 bodů)
Jedna nejmenovaná počítačová společnost nedávno zveřejnila, že hodlá vrhnout na trh naprosto originální novinku mezi úložnými zařízeními. Její naprostá nepřekonatelná moderní nedostižná a prostě skvělá přednost tkví v tom, že bude mít nekonečnou kapacitu.
Toto úložné zařízení slouží k uchování nekonečně mnoha celých čísel. Jednotlivá čísla jsou uložena v buňkách, které jsou očíslovány přirozenými čísly, a navíc platí, že obsahy paměťových buněk jsou uloženy ve vzestupném pořadí.
Společnost se ovšem natolik vyčerpala několikatýdenní letákovou, novinovou, televizní a billboardovou propagandou, že již není schopná napsat program, který bude s propagovaným zařízením zacházet.
Vaším úkolem je napsat program, který najde zadanou hodnotu v nekonečně velkém vzestupně uspořádaném poli se začátkem. Pozor na to, že jednotlivé hodnoty se mohou opakovat. Protože toto pole je nekonečně velké, nemůžete ho dostat na vstupu. Hodnoty toho pole budete zjišťovat tak, že se budete zařízení ptát na hodnotu v konkrétní paměťové buňce (pro nás to znamená, že se budete ptát uživatele). Výsledkem programu má být číslo paměťové buňky, kde se hledaná hodnota vyskytuje, případně -1, pokud se hledaná hodnota v zařízení nevyskytuje vůbec.
Důležité na Vašem programu je to, kolik hodnot si z popisovaného zařízení vyžádá. Zkuste také dokázat, že Vaše řešení je optimální (pokud opravdu je).
Příklad: Hledaná hodnota je 15, odpovědi na dotazy jsou tyto: v buňce 1 je uložena hodnota -8, v buňce 3 je 14 a v buňce 4 je hodnota 16. Výsledek programu je -1.
16-4-3 Stávka programátorů (10 bodů)
Pondělí ráno. Ústředí televize TeleNovela. Telefon zvoní. „Prosím?“ „Pane řediteli, hrozná věc! Programátoři stávkují, prý že i programátor má právo na lidská práva!“ „Ale my jsme televize TeleNovela. Tohle nás vůbec nezajímá.“
To samé pondělí ráno. Ústředí televize CNN. Telefon zvoní. „Prosím?“ „Pane řediteli, hrozná věc! Programátoři stávkují, prý že i programátor má právo na lidská práva!“ „To je ale hrůza! O tom musíme natočit reportáž!“
Programátoři ve známém městě Jsi-li con, válej se rozhodli uspořádat stávku. Chtějí mít všechna lidská práva, hlavně právo dostat za práci přiměřenou odměnu. Většina z nich je totiž neúnosně přeplacena. A oni chtějí spravedlnost.
Město si můžeme představit jako pravoúhlou síť ulic, kterých je ve vodorovném i svislém směru N. Ulice si očíslujeme, ty vodorovné odspoda, ty svislé zleva. Každou křižovatku můžeme označit dvojicí (x,y), kde x je číslo ulice svislé a y je číslo ulice vodorovné.
Programátoři budou postupně stávkovat na M různých křižovatkách. A televize CNN chce o všech stávkách natočit reportáž. K tomu, aby natočili reportáž o stávce na křižovatce (x,y) však nemusí být přímo na této křižovatce, ale stačí, když jsou ve svislé ulici x nebo ve vodorovné ulici y (mají totiž velmi dobré objektivy).
Televize CNN má ústředí na křižovatce (cnnx,cnny). Má k dispozici bohužel jediný vůz, který na začátku vyjede z ústředí, nafilmuje všech M stávek v pořadí, v jakém se budou konat, a vrátí se zpět do ústředí. Vaším úkolem je naplánovat jeho cestu tak, aby nafilmoval všechny stávky (jak už bylo řečeno, nemusí být přímo u stávky, stačí, když bude na ulici procházející křižovatkou stávky) a jeho cesta byla nejkratší možná.
Příklad: Pro N=4, M=3, stávky na křižovatkách v pořadí (1,4), (4,1), (3,4) a pro centrum CNN (2,2) je nejkratší možná cesta filmového vozu ←↓→→↑←.
16-4-4 Dlouhoprstova zapeklitá hra (10 bodů)
Dlouhoprstova hrabivost byla sice jeho vítězstvím nad piráty na chvilku utlumena, ale jeho sebevědomí poněkud stouplo. A tak si řekl, že když už je jednou na cestě do pekla, aby upsal ďáblu duši za pár stříbrňáků, tak tam dojde.
V pekle byl Dlouhoprst Satanem pěkně uvítán, ale návrh, že upíše svou duši, mu neprošel. Satan tvrdil, že Dlouhoprstova duše skončí tak jako tak v pekle, takže proč by mu za to měl ještě platit. Nicméně souhlasil, že si s Dlouhoprstem zahraje karetní hru.
Hraje se na jedné straně o Dlouhoprstův život, o truhlu stříbrňáků na straně druhé. Hry prší se samozřejmě v horoucím pekle bojí jako kříže a ani s mariášem Satan nesouhlasil. Viděl totiž Dlouhoprstovy rukávy nadité falešnými kartami. A tak Satan navrhl hru vlastní.
Hraje se se speciálními pekelnými kartami, každá karta je označená buď malým nebo velkým písmenem nebo číslicí. Satan před sebe položí dvě řady karet, obě v nějakém konkrétním pořadí. V jedné řadě je karet N, v druhé M. V každé řadě otočí nějaké karty vzhůru rubem a nějaké lícem. Každou řadu tedy můžeme zaznamenat jako posloupnost malých a velkých písmen a číslic (to jsou konkrétní karty), otazníků (práve jedna libovolná karta) a hvězdiček (0 a více libovolných karet).
Protože Satan ví o Dlouhoprstových falešných kartách, dostal Dlouhoprst za úkol vytáhnout z útrob svého obleku takovou nejkratší posloupnost karet, že může být stejná jako obě Satanovy řady karet. Případně má říci, že to není možné. Pokud je nejkratších posloupností více, stačí libovolná z nich.
Příklad: Pokud jsou Satanovy řady karet t?2*f? a t*fg, Dlouhoprst má
vytáhnout například karty tX2fg.
16-4-5 Obchodníci s deštěm (10 bodů)
Pro svou práci na novém operačním systému potřebujete spolehlivý generátor pseudonáhodných čísel. A to takový, který bude generovat nelokální posloupnosti náhodných čísel. To jsou takové posloupnosti, jejichž členy jsou rozptýlené na celém používaném intervalu. Jinak řečeno, nejmenší vzdálenost mezi dvěma libovolnými prvky je pokud možno co největší.
Bohužel jediná firma, která generátory tohoto typu nabízí, je O. Š. Kubal a synové. Tu musíte určitě znát. Je to jediná společnost, která dokázala prodat tisíc kusů ledniček značky „Mrazík“ Eskymákům, patentovala si v USA perpetuum mobile a dokázala si prodat vlastní nos mezi svýma očima.
Ale protože znáte O. Š. Kubala i jeho syny a chcete, aby generátor doopravdy fungoval, rozhodli jste se ho nejprve vyzkoušet. A k tomuto účelu si potřebujete napsat následující program.
Na vstupu dostanete N a K. Pak budete postupně načítat N různých náhodných čísel. Hned po načtení jednoho náhodného čísla (kromě prvního) vypíšete, jaký je nejmenší rozdíl mezi libovolnými různými dvěma z posledních K načtených náhodných čísel.
Příklad: Pro N=6, K=3 má vypadat vstup a výstup programu následovně:
| náhodné číslo | aktuální nejmenší rozdíl |
| 5 | |
| 7 | 2 |
| 4 | 1 |
| 15 | 3 |
| 6 | 2 |
| 20 | 5 |
16-4-6 Šikmá věž v Kocourkově (10 bodů)
V Kocourkově se radní buřtipáni rozhodli, že si postaví šikmou věž. Všichni s jejich návrhem souhlasili a všichni chtěli pomoci. Silák se hned nabídl, že vykopá do země díru, aby byla věž šikmá, Bohemína tvrdila, že z hromady vajec dokáže udělat skvělou maltu, Zpívarotti slíbil, že za trochu piva zazpívá a všem půjde práce pěkně od ruky.
Brzy (po několika postavených věžích) ale zjistili, že to nebude tak jednoduché. Některé úkoly bylo totiž nutné vyřešit před tím, než jiné začnou. Silák bohužel nedokázal pod již postavenou věží vykopat dost velkou díru, aby věž byla šikmá. A i když Lamželezo byl silák a s velkým rozběhem zvládl vybourat dveře v již postavené zdi, postavit zeď i s dveřmi bylo přeci jen lepší.
Dále zjistili, že nějaké práce jsou klíčové. Zpoždění takových klíčových prací totiž vede ke zpoždění celé stavby. A protože chtějí mít Kocourkovští věž postavenou co nejdříve, poslali si pro Vás, abyste jim pomohli.
Váš program dostane na vstupu N, což je počet pracovních úkonů, které je třeba k postavení věže vykonat. U každého úkonu víte dobu, jakou trvá, a dále seznam jiných úkonů, které musí být dokončeny před tím, než začne práce na tomto úkonu. Výstupem programu by mělo být buď slovo „nelze“, pokud věž postavit vůbec nejde (například Zpívarotti zpívá jen za pivo a hospodský chce dát pivo jen za doušek pěkného zpěvu). Pokud věž postavit jde, měl by Váš program vypsat nejmenší dobu, za jakou mohou Kocourkovští věž postavit, a ty úkony, které jsou klíčové.
Příklad: N=5, úkon 1 trvá 4 časové jednotky, úkon 2 trvá 2 časové jednotky, úkon 3 trvá 5 časových jednotek, úkon 4 trvá 10 časových jednotek a úkon 5 trvá 2 časové jednotky. Úkon 2 je možné začít, až když jsou hotové úkony 1 a 3. Úkon 4 může začít až po skončení úkonů 5 a 2.
Tehdy lze věž postavit za 17 časových jednotek a klíčové jsou úkony 2, 3 a 4.