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

Zadání úloh

14-1-1 Kostky (11 bodů)

Frantík si rád hrál s kostkami. Nejvíce ho bavilo si z kostek stavět věže. Čím vyšší věž byla, tím větší měl Frantík radost. Jednoho dne Frantíka napadla záludná otázka, na kterou neznal odpověď ani jeho tatínek: Jaká nejvyšší věž jde z jeho kostek postavit? A protože tatínek před synkem nechtěl ukázat, že něco neví, obrátil se na vás, abyste mu pomohli otázku zodpovědět.

Váš program dostane na vstupu počet kostek N. Pak následuje popis kostek – pro každou kostku tři čísla (šířka, tloušťka a výška). Pro jednoduchost předpokládejte, že kostky se nedají otáčet. Dvě kostky lze postavit na sebe, pokud šířka resp. tloušťka spodní kostky je větší nebo rovná šířce resp. tloušťce horní kostky (to znamená, že kostky se na sebe dají postavit tak, že horní kostka stojí celou svou podstavou na spodní kostce). Vaším úkolem je vypsat výšku nejvyšší postavitelné věže.

Příklad: Ze tří kostek o rozměrech 1×1×1, 1×5×3, 5×1×2 lze postavit věž výšky 4.

Řešení

14-1-2 Orientační běh (9 bodů)

Orientační běh probíhá tak, že na trať vytyčenou v terénu v určitých intervalech postupně vybíhají závodníci. Na trati je několik stanovišť, které by měl každý závodník navštívit. Organizátoři mají ale problémy s ověřováním, zda každý závodník proběhl všechna stanoviště, a tak se rozhodli využít počítače.

Vaším úkolem je napsat program, který dostane na vstupu počet stanovišť N a pro každé stanoviště vzestupně setříděný seznam čísel závodníků, kteří jím proběhli. Vaším úkolem je napsat program, který vypíše čísla závodníků, kteří proběhli všechna stanoviště.

Příklad: Na trati jsou 4 stanoviště. Prvním stanovištěm proběhli závodníci 1, 6, 8, 10; druhým závodníci 6, 8, 9, 10; třetím závodníci 1, 6, 9, 10 a čtvrtým závodníci 1, 6, 10. Všemi stanovišti tedy proběhli závodníci 6 a 10.

Řešení

14-1-3 Elektrická vedení (10 bodů)

Na planetě Aleton započala kolonizace. Aby měli kolonisté zajištěny alespoň základní životní potřeby, je nutné do celé země zavést elektřinu. Inženýři z Úřadu pro vesmírné plánování již navrhli úspornou síť rozvodných stanic a vedení mezi nimi. Je ale ještě třeba do některých rozvodných stanic umístit servisní střediska, která se budou starat o údržbu vedení. Aby byla údržba rychlá a jednoduchá, každé vedení musí mít alespoň na jednom svém konci servisní středisko. Jak inženýři zjistili, vystačit si s malým počtem servisních středisek není vůbec jednoduché, a tak vás požádali, abyste jim s rozmísťováním pomohli svými programátorskými schopnostmi.

Vaším úkolem je napsat program, který na vstupu dostane počet rozvodných stanic N a dále seznam N-1 vedení mezi jednotlivými stanicemi. Každé vedení je určeno dvojicí čísel rozvodných stanic, mezi kterými vede. Předpokládejte, že se lze po vedení dostat mezi každými dvěma rozvodnými stanicemi (tzn. pro každé dvě stanice s1 a sk existuje posloupnost stanic s1, s2, … , sk taková, že mezi stanicemi si a si+1 vede přímé vedení pro každé 1≤ i<k) a že vedení nikde netvoří okruh. Na výstup má váš program vypsat nejmenší možný počet servisních středisek a čísla stanic, ve kterých mají být servisní střediska umístěna.

Příklad: Na planetě je 6 rozvodných stanic. Propojení jsou: (1 2), (2 3), (2 4), (4 5), (4 6). Na planetě musí být alespoň 2 servisní střediska. Mohou být například ve stanicích 2 a 4.

Řešení

14-1-4 k-Klidná posloupnost (10 bodů)

O posloupnosti řekneme, že je k-klidná, pokud se žádné dva její po sobě jdoucí prvky neliší o více než k. Vaším úkolem je napsat program, který pro dané k, n a posloupnost celých čísel a1, a2, … , an nalezne a vypíše nejdelší k-klidnou vybranou podposloupnost dané posloupnosti. Pokud je takových vybraných podposloupností více, stačí vypsat libovolnou z nich. Vybraná podposloupnost posloupnosti a1, … , an je posloupnost čísel ai1, ai2, … , ail, kde 1≤ i1<i2<… <il≤ n.

Příklad: Nejdelší 2-klidná podposloupnost posloupnosti 10, 7, 9, 12, 14, 15, 11, 13 je 10, 12, 14, 15, 13.

Řešení

14-1-5 Turingovy stroje (10 bodů)

V letošním ročníku jsme se rozhodli uvést seriál na téma „Turingovy stroje“. Chtěli bychom vám v něm představit jeden z výpočetních modelů (výpočetní model je vlastně jakási abstrakce reálného počítače) a jeho rozličné modifikace, ukázat, jaký mají jednotlivé úpravy vliv na rychlost a výpočetní sílu modelu.

Nejdříve si nadefinujeme, co to takový Turingův stroj je. 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.

Pokud budeme v zadání mluvit o Turingově stroji nad abecedou Σ′, myslíme tím, že vstup stroje bude zapsán pomocí písmen z abecedy Σ′. Samotný stroj ovšem může mít svou abecedu Σ, kterou bude používat při výpočtu, podstatně bohatší.

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 Λ
q0 q0,0,R q0,1,R q1,Λ,L
q1 q1,0,L q2,0,R - - -
q2 q2,0,R - - - q3,Λ,L
q3 q1,Λ,L - - - - - -

Vaším úkolem v této úloze bude navrhnout dva Turingovy stroje. Součástí Vašeho řešení by samozřejmě neměla být pouze tabulka Turingova stroje, ale i popis, který osvětlí jeho funkci a správnost. Také by neměl chybět asymptotický odhad počtu kroků vašeho stroje a asymptotický odhad počtu použitých políček (tedy vlastně analogie časové a paměťové složitosti). Za počet použitých políček považujeme číslo nejzasšího políčka, na které vstoupila hlava Turingova stroje. A nyní slíbené úlohy:

Příklad stroje 1: Váš první stroj by měl slovo 01101 přepsat na slovo 10110.

Příklad stroje 2: Druhý stroj by měl slovo 111111 přepsat na slovo 111

Řešení