První série jedenáctého ročníku KSP

Zadání úloh

11-1-1 Cypherština (10 bodů)

Doktor Suess našel v troskách starověkého města Cypheru knihu, která byla psána písmeny podobnými písmenům latinské abecedy. Bohužel tato abeceda byla uspořádána jinak než abeceda latinská, tj. písmena nešla po sobě v pořadí ABCD… Doktora Suesse velmi mrzelo, že neví, jak je cypherská abeceda uspořádána, ale po chvíli listování knihou narazil na stránku, která byla pravděpodobně vytržena z jiné knihy, a do této pouze založena. Doktor Suess prozkoumal tuto stránku a zjistil, že je to stránka cypherského slovníku. Za předpokladu, že cypheřané třídili své slovníky podle své abecedy, pomozte doktorovi tím, že napíšete program, který pro seřazená slova ze stránky určí pořadí písmen v cypherské abecedě, případně odpoví, že to nejde. Předpokládejte, že slova na stránce slovníku jsou setříděna korektně.

Příklad: Stránka obsahovala 4 slova v pořadí CDA ABCD ACCD DAB. Pak seřazená abeceda vypadá takto: B<C<A<D.

Řešení

11-1-2 Quad rant (10 bodů)

Mějme obrázek nakreslený do čtvercové sítě velikosti 2n ×2n, pričemž každý čtvereček je celý buďto černý nebo bílý. Obrázky tohoto druhu se často pro úsporu místa popisují takzvanými kvadrantovými kódy dle následujících pravidel:

Příklady: 220001001001, 0200201002001, 2020001021000, 002200012100000, 220010020100000.

Vaším úkolem je vymyslet algoritmus a napsat program, který dostane na vstupu kód obrázku a odpoví kódem obrázku vzniklého otočením zadání o 90° proti směru hodinových ručiček (tedy například z druhého z našich příkladů by udělal třetí).

Řešení

11-1-3 Magiášův Tfujtajxl (10 bodů)

Již od nepaměti žil na hoře Hejšovině černokněžník Magiáš. Ve dne kouzlil, a v noci, konec konců, také. Ale jak stárnul (přeci jen už mu na podzim bude 300 let), pomalu si uvědomoval, že ani jeho paměť už není, co bývala, a že si zrovna vůbec nemůže vzpomenout, jak zní magické zaříkadlo na hledání zapomenutých magických zaříkadel. Ale ještě si vybavoval, že určitě obsahuje slovo `tfujtajxl' (i když možná s nějakou předponou či příponou), že počet písmen formule je dělitelný třemi, a že v něm není slovo začínající na `q'.

Mistrovu naříkání již delší dobu tiše naslouchal jeho fámulus, sluha, kuchař, nosič, knihovník, donašeč, čistič laboratorního skla, dvorní krysař a v neposlední řadě hromosvod, to vše v jedné osobě jménem Vincek. A uvědomil si, že Magiáš přeci již dávno podlehl šílenství doby a své poznámky si přepsal do svého jeskynního počítače a že by tedy stálo za to napsat program, který zjistí, zda se mezi kouzelnými průpovídkami z Magiášových zápisků nějaký řádek splňující kouzelníkovy požadavky vyskytuje. Pokuste se sami takový program napsat, leč uvědomte si, že Magiášovo počitadlo má extrémně malou datovou paměť a tedy čím méně proměnných použijete, tím lépe.

Řešení

11-1-4 Sibylla 98 (12 bodů)

V tomto ročníku KSP bychom rádi v každé sérii uvedli jednu úlohu ražení spíše teoretického. Na zahřátí začneme něčím poměrně jednoduchým, ač poněkud netradičním: nedeterministickým programováním.

Programovací jazyk Sibylla 98 se chová jako obyčejné C nebo Pascal, až na dva podstatné rozdíly:

  1. Výsledkem programu je vždy buďto nula nebo jednička. Program tedy může odpovídat pouze na binární problémy typu "je toto číslo prvočíslem?".
  2. Má navíc jednu zajímavou funkci zvanou oracle(n), která poskytuje odpověď věštírny – celé číslo v rozsahu 0 až n. Tato odpověď je nedeterministická (to jest nevíte nic o tom, jak závisí na stavu výpočtu).
Pro každou posloupnost odpovědí věštírny tedy výpočet může probíhat úplně jinak (těmto variantám říkáme větve výpočtu) a potenciálně i vydat jiný výsledek. K čemu je to tedy dobré? Inu, nadefinujeme, že program na danou otázku odpoví 1 (true) právě tehdy, když mohla věštírna poskytnout takovou posloupnost odpovědí, která by vedla výpočet k výsledku 1. V ostatních případech je odpovědí 0 (false).

Časová složitost nedeterministického programu je v případě odpovědi 1 čas nejkratší větve výpočtu, která odpoví 1, jinak délka nejdelší ze všech větví výpočtu. (Tedy pokud žádná větev neodpoví 1 a některá větev se zacyklí, celý výpočet nikdy neskončí.)

Příklad: Nedeterministický program

begin
   readln(i);
   j := 2 + oracle(i-3);
   if (i>2) and (i mod j = 0) then writeln(1)
   else writeln(0)
end.

rozhoduje o tom, zda je zadané číslo i číslem složeným. Dělá to tak, že si nechá od věštírny poradit nějaké číslo j ∈<2,i-1> a odpoví 1 právě tehdy, když je j dělitelem čísla i. Podle definice je celkovým výsledkem 1, právě když mohla věštírna vygenerovat j takové, aby program odpověděl jedničkou, což je přesně tehdy, když existuje vlastní dělitel čísla i, tedy když jde o číslo složené. Toto vše se děje v konstantním čase – O(1), ježto všechny větve jsou prováděny konstantně rychle.

Úloha A: Napište nedeterministický program v jazyce Sibylla 98, který řeší co nejrychleji známý problém batohu: Máte batoh o nosnosti k kilogramů a předměty hmotností m1,… ,mn kilogramů a otázka zní, zda je možno vybrat z těchto předmětů takové, abyste batoh přesně zaplnili.

Úloha B: Zkuste dokázat, že každá úloha, která je řešitelná nedeterministickým programem, je řešitelná i programem deterministickým, i když možná za cenu výrazného zpomalení výpočtu.

Řešení