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

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

Milí řešitelé!

zima a s ní i Vánoce se pomalu blíží, a tak se svou nadílkou pod stromeček přichází i KSP. Doufáme, že se vám naše dárky budou líbit a že s nimi strávíte příjemné chvíle.

Zadání úloh

16-2-1 Král Eeek (10 bodů)

Byl-nebyl jednou jeden král, který se jmenoval Eeek a měl tuze rád knížky. Jeho palác se už dávno stal jednou velikánskou knihovnou a král Eeek trávil celé dny vysedáváním u krbu ve své soukromé čítárně. Až jednoho dne za ním přišel lord nejvyšší knihovník a svěřil se králi, že objevil knihu, které ani za mák nerozumí.

Celý text onoho masivního fasciklu byl tvořen jen a pouze číslicemi, uspořádanými zdánlivě bez jakéhokoliv řádu, a spolehlivě činil zmatek jak v pomazané hlavě královské, tak v poněkud méně vznešené, leč vzdělanější hlavě knihovníkově. Dlouho o tom při dobrém víně přemýšleli, až dospěli k následující teorii:

Kdysi dávno žila civilizace, jejíž filosofové rádi zapisovali své myšlenky jako dlouhatánská čísla v roztodivných číselných soustavách. Ovšem základy těchto soustav byly natolik velké, že jim brzy došly symboly pro číslice, a tak jednotlivé číslice začali zapisovat v desítkové soustavě. Navíc ještě za číslo připojovali základ soustavy, rovněž zapsaný desítkově. Čísla tedy vypadala například takto:

(1)(6)[10] = 1·101 + 6·100 = 16
(10)(10)[11] = 10·111 + 10·110 = 120
(14)(10)(5)[16] = 14·162 + 10·161 + 5·160 = 3749
(1)(4)(1)(0)(5)(1)[6] = 1·65 + … + 1·60 = 13207

Přitom zápisy číslic nikdy nezačínaly nulou, pokud nešlo o nulu samotnou, a byla to vždy celá nezáporná čísla menší než základ. Základ byl celé číslo větší než 1 a také nikdy nezačínal nulou. Formálně řečeno, hodnota čísla se stanovovala podle následujícího pravidla:

(an)(an-1)… (a1)(a0)[z] = ∑
n
i=0
ai ·zi.

„Léty ovšem závorky v zápisu vybledly a zbyly jen číslice, takže původní číslo už stěží kdo rozpozná,“ povzdechl si král Eeek. Knihovník na to ale opáčil, že zatímco se Jeho veličenstvo ráčilo věnovati hodnotné literatuře, poddaní mezitím objevili počítače a dokonce si už založili i programátorský korespondenční seminář, takže jistě dokáží napsat program, který o daném řetězci čísel rozhodne, kolik existuje způsobů, jak doplnit závorky tak, aby vznikl korektní zápis nějakého čísla.

Co říkáte, dokážete to?

Příklad: Posloupnost 1410516 odpovídá zápisům:

(1)(4)(1)(0)(5)(1)[6] (1)(4)(1)(0)[516]
(1)(4)(1)(0)(5)[16] (14)(1)(0)[516]
(14)(1)(0)(5)[16] (1)(41)(0)[516]
(1)(4)(10)(5)[16] (141)(0)[516]
(14)(10)(5)[16] (1)(4)(10)[516]
(1)(4)[10516] (14)(10)[516]
(14)[10516] (1)(410)[516]
(1)[410516]

Naproti tomu posloupnost 100 žádnému zápisu neodpovídá.

Řešení

16-2-2 Král Ovopole (10 bodů)

Nebyl-byl jednou jiný král, kterému říkali Ovopole, neboť měl zvláštní zálibu ve vajíčkách – mimo to, že si na nich rád pochutnával, je také vědecky zkoumal. Jednoho dne ho napadlo, že zjistí, ze kterého nejnižšího patra jeho vysokánského (takto N-patrového) paláce se vajíčko puštěné z okna na nádvoří rozbije.

To je samozřejmě snadné zjistit pokusy: V každém pokusu král vajíčko pustí z nějakého patra a když se vajíčko nerozbije, nechá si ho přinést a může s ním podniknout další pokus; pokud se rozbije, musí král sáhnout po dalším vajíčku. To je snadné, ale ouha, Ovopole právě s ú(div|děs|žas)em zjistil, že v celém paláci se nachází jen k vajíček, která doposud nepodlehla předchozím experimentům. Navíc král je poněkud netrpělivý, takže by s těmito dvěma vajíčky chtěl získat správnou odpověď na co nejméně pokusů.

Napište proto našemu králi program, který jeho problém vyřeší (jistě se vám za to dostane královské odměny). Takový program dostane na vstupu počet pater N a počet vajíček k a postupně bude navrhovat jednotlivé pokusy a přijímat odpovědi, jak právě vypsaný pokus dopadl. Nakonec program odpoví číslem hledaného nejnižšího patra.

Řešení

16-2-3 Král Potvorník (10 bodů)

Král Potvorník (matematiky většinou zvaný „Ten, který zadává ε“ nebo prostě Nepřítel) si u svých zeměměřičů objednal přeměření své královské potvorologické zahrady za účelem stavby nového plotu. Zahrada má, jak je známo, tvar nepravidelného konvexního n-úhelníku (to, že je konvexní, znamená, že všechny vnitřní úhly jsou menší než 180°) a Potvorník potřebuje zjistit její obvod, aby věděl, kolik pletiva a ostnatého drátu musí objednat.

Zeměměřiči vyměřili souřadnice všech sloupků budoucího plotu ležících přesně ve vrcholech n-úhelníka a když se užuž chystali dát se do počítání, přiběhla jedna z obyvatelek zahrady a jako na potvoru do hromádky lístků s napsanými souřadnicemi strčila a beznadějně je pomíchala. Nedosti na tom, zamíchala mezi ně i jiné lístky, na nichž byly souřadnice různých objektů ležících uvnitř zahrady.

Na vás je, abyste zeměměřiče zachránili před královskou odměnou (která by je jistě neminula, kdyby nespočítali včas) tím, že napíšete program, který dostane na vstupu všechny nasbírané souřadnice (tedy souřadnice vrcholů a nějakých bodů uvnitř, to vše v libovolně zpotvořeném pořadí) a odpoví co možná nejrychleji, jaký je obvod zahrady (jak již asi tušíte, ani tento král není zrovna vzorem trpělivosti).

Řešení

16-2-4 Křížový král (10 bodů)

Při putování křížem kráž světem ve službách Křížového (nebo Krážového?) krále jste se dostali až do jeskyně obývané ohnivým drakem. Drak vás vřele přivítal a rovnou vás pozval k obědu. Brzy jste bohužel zjistili, že se také můžete stát jeho podstatnou součástí. Nicméně draci jsou čestní a navíc se tento už dlouho nudil, takže jste dostali šanci zachránit si život. Stačí porazit draka ve hře.

Hra je velmi jednoduchá: drak si zvolí nějaké přirozené číslo mezi 1 a N (kteréžto N je předem známo) a na vás je, abyste ho uhodli. Vy si v každém tahu zvolíte množinu čísel a drak vám řekne, zda se v ní jeho číslo nachází či nikoliv. Když jste si jistí, řeknete číslo, o kterém si myslíte, že si ho drak myslí, a drak zřejmým postupem rozhodne, zda si pochutnáte na pečínce nebo skončíte na pekáči.

Nicméně drak je velmi starý a buď se definice čestnosti od dob jeho mládí trochu změnila, nebo začíná být poněkud sklerotický. Drak považuje za zcela čestné podvádět, pokud to ovšem neudělá častěji než jednou za hru. Čili ve vaší hře jedna z jeho odpovědí může (ale také nemusí) být chybná.

Pokud ovšem s odpovědí příliš otálíte a ptáte se příliš dlouho, drak začne být z nutnosti provádět komplikované operace s množinami hladový a samozřejmě v takové situaci netoužíte po tom, aby mu došla trpělivost.

Je tu ještě jeden drobný háček – v dračí řeči si nejste zrovna nejjistější a drak sice češtinu ovládá bez problémů, nicméně nedávno si nechal nabrousit zuby a jeho výslovnost od té doby není příliš dobrá. Abyste předešli nedorozumněním, dohodli jste se, že budete komunikovat v jazycích zvaných Pascal nebo C a místo toho, abyste hráli přímo, popíšete svou strategii jako program.

P.S.: Zaručená informace pocházející od předkrmu říká, že při N=1 000 000 drakovi trpělivost vydrží alespoň 26 kol.

Řešení

16-2-5 Král Popleta (10 bodů)

Panovník Popleta XI. (nebo že by už XII., kdo ví?) jistého nejmenovaného království se již chystá na odpočinek (moderně bychom řekli do důchodu) a je potřeba, aby své království přenechal svým potomkům. A to je právě ten problém. Král má dva syny, Petra a Pavla, a shodou okolností jsou to dvojčata. Jak tak léta běžela, dvořané už dávno zapomněli, který ze synů je vlastně ten prvorozený, a bude proto potřeba království mezi ně spravedlivě rozdělit.

Království je tvořeno n provinciemi, které jsou očíslovány čísly od 1 do n. Každá připadne právě jednomu ze synů. Synové sepsali své požadavky na to, jak by takové rozdělení mělo vypadat. Petrovy podmínky jsou následujícího tvaru:

Stejné tři typy podmínek (až na to, že provincie chce pro sebe) má i Pavel.

Popletovi XI. jde z toho hlava kolem, a tak povolal své moudré rádce, aby království rozdělili. Rádcové podmínky synů podrobně zkoumali a brzy zjistili, že neexistuje žádné rozdělení provincií, které by všechny sepsané podmínky splnilo naráz. Na druhou stranu také zjistili, že libovolné tři podmínky naráz splnit lze, tj., např. se mezi podmínkami nevyskytuje následující trojice:

I přes tato objevná pozorování, nakonec rádci králi Popletovi XI. poradili, ať si u každé provincie hodí korunou a podle výsledku hodu pak provincii přenechá buď Petrovi nebo Pavlovi. Že prý takto (v průměrném případě), splní alespoň polovinu všech podmínek, které si oba synové dohromady vymysleli. Všimněte si, že podmínky synů by byly splněny s pravděpodobností 1/2 a 3/4 (dle jejich typu) a tedy v průměrném případě je splněna alespoň polovina všech podmínek. Popletovi XI. se to však nějak nezdálo (přece nebude házet svou zlatou královskou korunou, co nosí na hlavě, to dá rozum) a obrátil se na vás.

Vaším úkolem je vymyslet pravděpodobnostní algoritmus, který v průměrném případě splní co největší množství podmínek na rozdělení království. Tedy, nalezněte co největší číslo α, 0≤ α≤ 1, a k němu příslušný pravděpodobnostní algoritmus takový, že střední hodnota počtu splněných podmínek na rozdělení království je αm, tj. rozdělení provincií nalezené algoritmem průměrně splní alespoň αm podmínek ze všech m podmínek. Váš algoritmus by měl pracovat v polynomiálním čase (král chce předat království svým synům ještě za svého života).

Řešení