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

Zadání úloh

14-2-1 Kyvadlo (10 bodů)

V daleké Tramtárii žije král Trdlo. Tento král se velmi vyžívá v různých hříčkách a hlavolamech ale hlavně v hazardních hrách. Jednou z jeho oblíbených her, kterou hraje se svými šlechtici, je hra „Kyvadlo“. Hra se hraje na svisle umístěné obdélníkové desce. Na přední stranu desky vždy bankéř připevní několik kolíků a k nejvýše upevněnému kolíku přiváže provázek se závažím. Poté, co si každý z hráčů vsadí na nějaký kolík, bankéř natáhne provázek se závažím doprava do vodorovné polohy a závaží hodí směrem dolů. Závaží letí, provázek se otačí okolo různých kolíků, až nakonec bude volná část provázku tak krátká, že nedosáhne k žádnému dalšímu kolíku a provázek se jen bude namotávat okolo jednoho kolíku. Hráč, který vsadil na tento kolík, vyhrává a bere vše. Pokud nikdo na kolík nevsadil, vyhrává bankéř. Jeden ze šlechticů na této hře prohrál již úctyhodné jmění a rozhodl se, že takhle to dál nejde. Proto si najal vás, abyste mu napsali program, který mu v sázení pomůže.

Váš program dostane na vstup počet kolíků N a souřadnice těchto kolíků. To jsou nějaké dvojice reálných čísel (X1, Y1),… ,(XN, YN). Pak ještě dostane délku provázku D. Na výstup má váš program vypsat číslo kolíku, okolo kterého se bude nakonec provázek namotávat. Pro účely naší úlohy předpokládejte, že kolíky mají nulový průměr a že bankéř hodí závaží dostatečnou silou (tedy že závaží bude mít dostatečnou rychlost na obtočení okolo libovolného kolíku).

Řešení

14-2-2 Cenzoři (11 bodů)

Není to tak dávno, co se v Banánistánu ujal vlády další z řady moudrých panovníků (tedy alespoň tak to píší v novinách). Tento moudrý panovník brzy zjistil, že o něm někteří nerozumní novináři píší nepěkné věci, které poškozují jeho pověst. Proto se v zájmu své dobré pověsti rozhodl zavést v zemi cenzuru. Spolu se svými nejbližšími spolupracovníky vytvořil seznam slov, která se prostě v tisku nesmí objevit. Každý z cenzorů dostal seznam slov a měl za úkol z cenzurovaného textu každé slovo ze seznamu vyškrtnout. Protože ovšem tiskovin je velmi mnoho a cenzoři jsou nespolehliví a drazí, rozhodl se panovník po čase celou tuto proceduru mechanizovat. A to je již úkol pro vás.

Váš program dostane na vstupu seznam slov, která mají být z textu vyškrtána. V naší úloze považujeme text prostě za posloupnost znaků a na takové detaily, jako že slovo bývá ohraničeno mezerami nehledíme. Dále dostane váš program na vstupu text k cenzuře. Na výstup má pak váš program vypsat text s vyškrtanými zakázanými slovy. Pozor! Vyškrtnutím nějakého slova vám může opět vzniknout zakázané slovo!

Příklad: Pro zakázaná slova voda, vodojem a cenzurovaný text prasklvodovodajemuneteklavoda má váš program vypsat text prasklunetekla. Bylo totiž vypuštěno slovo voda, čímž vzniklo slovo vodojem, které bylo následně také vypuštěno. Nakonec bylo ještě vypuštěno slovo voda na konci textu.

Řešení

14-2-3 Dekomprese (10 bodů)

Jak jistě víte, na pevném disku se dá ušetřit hodně místa kompresí souborů. Jednou z metod komprese je i metoda LZW. Nebudeme zde popisovat, jak tato metoda funguje. Postačí nám, když si řekneme, že soubor zakomprimovaný touto metodou obsahuje jednak normální data a jednak odkazy. Každý z odkazů ukazuje na nějaký předchozí úsek souboru (máme dánu jeho pozici a délku) a označuje, že při dekompresi se místo tohoto odkazu má vložit příslušný úsek souboru. Například soubor abc(0,3)(0,6)(10,2)d bude po dekompresi obsahovat abcabcabcabcbcd. Vaším úkolem bude rychle spočítat počet výskytů zadaného písmena v zakomprimovaném souboru.

Váš program dostane na vstupu počítané písmeno C a zakomprimovaný soubor (konkrétní formát vstupu necháme na vás, měl by ale přibližně odpovídat formátu v příkladu). Na výstup má vypsat počet výskytů C v odkomprimovaném souboru.

Příklad: V souboru abc(0,3)(0,6)(10,2)d je 5 výskytů písmena b.

Řešení

14-2-4 Seznamování (10 bodů)

Na soustředění KSP přijelo mnoho účastníků. Ačkoliv někteří se již znali z předchozích let, jiní byli na soustředění poprvé, a tak byly na počátek soustředění naplánovány seznamovací hry. Jelikož účastníků je poměrně hodně, je potřeba je rozdělit na dvě skupiny. Nemá ale samozřejmě smysl seznamovat účastníky, kteří se již znají, a proto musí být rozdělení na skupiny takové, aby se každý účastník znal ve své skupině nejvýše s tolika lidmi, s kolika se zná ve skupině druhé. A to je úkol pro vás.

Váš program dostane na vstupu počet účastníků N a dále seznam známostí mezi účastníky (tedy seznam dvojic účastníků, kteří se navzájem znají – účastníky si pro jednoduchost očíslujeme od jedné do N). Na výstup má váš program pro každého účastníka vypsat, do které skupiny je třeba ho zařadit. Pokud je možných rozdělení více, stačí vypsat libovolné z nich.

Příklad: Pro 5 účastníků a známosti (1,2), (2,3), (3,4), (4,5), (2,5), (1,4) může váš program například vypsat rozdělení do skupin 1 2 1 2 1.

Řešení

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

Ve druhé sérii budeme pracovat s vícepáskovými Turingovými stroji. Jak už název napovídá vícepáskový stroj nemá pásku jednu, ale pásek k, kde 1≤ k je nějaké pevné číslo nezávislé na vstupu. Každá páska je opět jednosměrně nekonečná, rozdělená na políčka a na každém políčku je nějaké písmeno z abecedy Σ. Nad každou páskou pracuje jedna hlava.

Řídící jednotka stroje je v každém okamžiku v nějakém stavu z množiny Q a rozhoduje se podle přechodové funkce f(q,(z1,… ,zk)). Ta pro každou kombinaci stavu q a k-tice znaků (z1,… ,zk), které jsou pod jednotlivými hlavami, dává trojici (q′,(z
′
1
,… ,z
′
k
),(m1,… ,mk)), kde q′ je stav, do kterého řídící jednotka přejde v dalším kroku, (z
′
1
,… ,z
′
k
) jsou znaky, kterými hlavy přepíší znaky (z1,… ,zk), a (m1,… ,mk) jsou pohyby, které mají provést hlavy. Mimo v první sérii zavedených pohybů L (doleva) a R (doprava) může být hlavě ještě předepsán pohyb N (zůstat na místě).

Výpočet vícepáskového Turingova stroje tedy probíhá obdobně, jako výpočet stroje jednopáskového, jen stroj najednou pracuje na několika páskách. Práce stroje končí pokud libovolná z hlav narazí do levého okraje pásky. Za výstup stroje se pak považuje obsah první pásky.

Protože u vícepáskových strojů je již občas trochu nepřehledné vše zapisovat pomocí tabulky, ukážeme vám v následujícím příkladu zápis ve tvaru „programu“.

Příklad: Následující 2-páskový Turingův stroj pracující nad abecedou Σ= {0, 1, Λ} převrátí slovo zadané na vstupu (první pásce).

(q0,(x,?))→ (q1,(Λ,x),(R,R))x∈{0,1}
(q1,(x,?))→ (q1,(x,x),(R,R))x∈{0,1}
(q1,(Λ,?))→ (q2,(Λ,Λ),(L,N))
(q2,(x,?))→ (q2,(x,?),(L,N))x∈{0,1}
(q2,(Λ,?))→ (q3,(Λ,?),(N,L))
(q3,(?,x))→ (q3,(x,Λ),(R,L))x∈{0,1}

Poznámka: ? v levé části znamená libovolný znak, v pravé části pak znak, který byl zastoupen ? v levé části.

Vaším úkolem v této úloze bude navrhnout vícepáskový (počet pásek si zvolte sami) Turingův stroj nad abecedou Σ= {0,1,Λ}, který číslo zapsané v jedničkové soustavě na první pásce převede do dvojkové soustavy (výstup má být též na první pásce). Cifry s nejnižší vahou by měly být nejvíce vlevo.

Příklad: Číslo 1111111111 by měl váš stroj převést na 0101.

Řešení