Druhá série desátého ročníku KSP

Zadání úloh

10-2-1 Byrok(r)ati (10 bodů)

V královském paláci se ke značnému zoufalství všech poddaných rozbujela byrokracie – královští ouřadníci si navzájem vytvořili n papalášských funkcí a do nich se jmenovali (označíme si je třeba čísly 1 až n). A když někdo přišel do paláce žádaje audienci u krále, musel jít za ouřadníkem, který byl pro daný den zvolen jako lord tiskový mluvčí (nechť má číslo L) a vyžádat si od něj povolení k audienci.

Jenže jak už to v byrokratických systémech bývá, týmová práce jest nezbytná (asi proto, že umožňuje svalit vinu na ostatní), a tak lord tiskový mluvčí vydá povolení pouze tehdy, dostane-li potvrzení o odbornosti tazatele, potvrzení o loayalitě králi, dále pak glejt o bezúhonnosti, jakož i výpis z rejstříku tortury – tedy vlastně mnoho dalších lejster, která vydávají jiní ouřadníci. Ale vydají je obvykle jen tehdy, přinese-li jim ubohý poddaný glejty od jiných ouřadníků atd. Každý z nich ovšem vydává pouze jedno lejstro (takže každého z nich má smysl navštěvovat nejvýše jednou).

Ale poddaní se nedali – na cestě ke královskému paláci stojí stánek byrokata (to je člověk, jenž se specializuje na potírání byrokracie) a z jedné strany k němu chodí donašeči z paláce dodávající informace o tom, který z pánů ouřadů zrovna chce potvrzení od kterých ostatních (například jakožto čísla oij jsoucí nenulová, pokud i-tý ouřada požaduje k vydání svého lejstra jiné od j-tého ouřady), zatímco ze strany druhé přicházejí poddaní a ptají se, v jakém pořadí mají papaláše navštívit, aby povolení k audienci od lorda L získali. (Všechny osoby v tomto příběhu jsou smyšlené a jakákoliv podobnost s pohádkou o kohoutkovi a slepičce, s realitou, jakož i s úlohou o topologickém třídění grafu je čistě dílem náhody.)

Úkol pro vás: vymyslet program, který bude řešit byrokatův problém.

Příklad: Pro o=

0 1 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 1
0 1 0 0 1 0

a L=1 je jedním z možných pořadí 4, 3, 2, 1, zatímco pro tatáž oij a L=5 není úkol splnitelný, protože papaláši 5 a 6 se navzájem posílají jeden k druhému.

Řešení

10-2-2 Minitónní posloupnost (12 bodů)

Napište program, který pro dané číslo n vytvoří posloupnost délky n obsahující každé z čísel 1 až n, a to takovou, aby délka nejdelší monotónní (to jest rostoucí či klesající) podposloupnosti byla co nejmenší. Podposloupností posloupnosti a1, … , an se rozumí jakákoliv posloupnost ai1, … aik, kde i1 < i2 < … < ik.

Kupříkladu pro n=5 program vygeneruje 1, 4, 5, 2, 3 nebo 3, 2, 1, 4, 5 atd. Nejdelší monotónní podposloupnost má v obou případech délku 3.

Řešení

10-2-3 Turingův stroj (10 bodů)

Turingův stroj sestává z pásky a řídící jednotky. Páska Turingova stroje má jen jeden konec, a to levý (doprava je nekonečná) a je rozdělena na políčka. Na každém políčku se nachází právě jeden znak z abecedy Σ (to je nějaká konečná množina, o které navíc víme, že obsahuje znak Λ). Nad páskou se pohybuje hlava stroje, v každém okamžiku je nad právě jedním políčkem.

Řídící jednotka stroje je v každém okamžiku v jednom stavu ze stavové množiny Q (opět nějaká konečná množina) a rozhoduje se podle přechodové funkce f(q,z), která pro každou kombinaci stavu q a znaku z, který je zrovna pod hlavou, dává uspořádanou trojici (q′,z′,m), přičemž q je stav, do kterého řídící jednotka přejde v dalším kroku, z′ znak, kterým bude nahrazen znak z umístěný pod hlavou a konečně m je buďto L nebo R podle toho, zda se má hlava posunout doleva nebo doprava.

Výpočet Turingova stroje probíhá takto: na počátku je hlava nad nejlevějším políčkem, na počátku pásky jsou uložena vstupní data (zbytek pásky je vyplněn symboly Λ) a řídící jednotka je ve stavu q0. V každém kroku výpočtu se Turingův stroj podívá, co říká funkce f o kombinaci aktuální stav + znak pod hlavou, načež znak nahradí, přejde do nového stavu a posune hlavu v udaném směru. Takto pracuje do té doby, než narazí hlavou do levého okraje pásky, čímž výpočet končí a páska obsahuje výstup stroje.

Příklad: Následující tabulka definuje Turingův stroj nad abecedou Σ= {0, 1, Λ}, který ze vstupního slova složeného ze znaků 0 a 1 odstraní všechny jedničky. Počátečním stavem je stav 0, políčka tabulky označená `- - -' nemohou být strojem nikdy dosažena.

     0 1 Λ
0 0,0,R 0,1,R 1,Λ,L
1 1,0,L 2,0,R - - -
2 2,0,R - - - 3,Λ,L
3 1,Λ,L - - - - - -

Úkol: Popište Turingův stroj realizující výpočet součinu dvou čísel. Representaci čísel na pásce stroje si zvolte, jakou uznáte za vhodné.

Řešení

10-2-4 Bynáriho logaritmus (10 bodů)

Představte si Pascal, v němž typ integer může obsahovat až 1024-bitové číslo (alternativně Céčko, kde platí totéž pro typ int). Napište v takovémto jazyce co nejrychlejší program, který pro dané číslo n spočte jeho Bynáriho logaritmus, což je nejmenší číslo k takové, že 2k ≥ n.

K dispozici máte všechny běžné pascalské (resp. céčkovské) operace: sčítání, odčítání, násobení, dělení, bitový and, or, xor i negaci atd.

Řešení

10-2-5 Kostky jsou vrženy (12 bodů)

Známý metrolog baron Bynári přišel s následujícím problémem: máte na stole rovnoramenné váhy a hromadu n kostek. Vaším cílem je z těchto kostek za pomoci zmíněných vah nalézt k nejtěžších.

Navrhněte algoritmus, který bude osobě obsluhující váhy (nečiňmež, prosím, žádné neodůvodněné předpoklady o její inteligenci) diktovat, co má dělat: v každém kroku vypíše čísla kostek, které má osoba dát na levou misku a čísla těch, která má dát na misku pravou. Načež osoba kostky naskládá a odpoví, jestli byla těžší levá miska, pravá miska či obě vyrovnané. Takto algoritmus pokračuje až do okamžiku, kdy si je jist výsledkem.

Příklad: n=3, k=2. První vážení: na levé misce 1, na pravé 2, výsledek L (levá těžší). Druhé vážení: nalevo 1, napravo 3, výsledek: P. Hotovo, nejtěžší je 3 a druhá nejtěžší 1.

Řešení