Třetí série sedmnáctého ročníku KSP

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

Zadání úloh

Milí řešitelé!

Hroch s notebookem

Poněkud s předstihem dostáváte do rukou zadání třetí série našeho semináře. S ním dostáváte taktéž opravená řešení série první, takže špinavé a podlé fígly, které se z nich naučíte, můžete použít ještě při řešení série druhé :–)

17-3-1 Spisovatel Vilík (10 bodů)

Spisovatel Vilík Šekjrspír (v originále Shaker's Pear, neboli šejkařova hruška, oblíbený to alkoholický nápoj) byl velmi známý autor. Nicméně měl pocit, že jeho knihám se nedostává tolik pozornosti, kolik by si jí podle něj zasloužily. Nakonec se mu dokonce povedlo přijít na to, čím by to mohlo být. (A vzhledem k tomu, že ho dnes zná skoro každý, měl asi pravdu.)

Zjistil, že jeho knihy jsou poněkud nudné, protože se v nich často opakují celé kusy textu. A tak si řekl, že všechna opakování nějakého textu ze svých knih smaže, nebudou potom tak nudné a navíc budou mít otevřený konec.

Když takto upravil první knihu, zjistil, že z ní zbyla ještě celá třetina. Známý myslitel Cibulka mu tedy poradil, že za stejná slova může považovat i dva kusy textu, které mají stejnou délku a skládají se ze stejných znaků. (Nezáleží tedy na pořadí znaků v obou slovech.)

Vilík teď už ale sám nedokáže najít stejná slova, Cibulka mu sám také nechce pomoci (prý řeší zajímavější problém), a tak to zbyde na Vás.

Napište program, který dostane na vstupu číslo k a text délky N znaků skládající se z písmen `a'..`z', `A'..`Z', mezer, teček, otazníků a vykřičníků. Má spočítat délku nejdelšího začátečního úseku tohoto textu, ve kterém se ještě nevyskytují dvě shodná slova. Dvě slova jsou shodná, pokud to jsou souvislé podřetězce zadaného textu a obě se skládají z právě k stejných písmen, i když pořadí těchto písmen může být různé. Velká a malá písmena nerozlišujte, čili `a'=`A'.

Příklad: Pro k=3, N=14 a text `Den bude hned.' je správný výsledek 12 (v prvních dvanácti písmenech nejsou žádná shodná slova). Pro text `Den je tu hned' je správná odpověď 6 (protože ` je'=`je ').

Řešení

17-3-2 Popleta Truhlík (10 bodů)

Pan Truhlík byl veliký popleta. Nedokázal si zapamatovat, jak se jmenuje, kde pracuje, a často se mu stalo, že nepoznal svou vlastní dceru a ptal se jí: „Holčičko, nevíš, kde bydlím?“ (Zaměstnáním by se nejlépe hodil na matematika.)

Dokud žil s maminkou, bylo vše v pořádku, ale jakmile se odstěhoval z domu, začal mít se svou popleteností veliké problémy. A tak si řekl, že když by mamince občas zavolal, určitě by mu pomohla. Problém byl ale v tom, že i když si vzpomněl, že má maminku, nedokázal si vzpomenout na její telefonní číslo. Jednou se mu povedlo si celý problém uvědomit a svěřil se s ním prvnímu kolemjdoucímu, kterým byl zrovna myslitel Cibulka.

Pan Cibulka po chvíli hovoru zjistil, že Truhlík je sice veliký popleta (nebo pan Popletal je veliký truhlík?), ale pamatuje si všechny večerníčkové postavy. A tak vymyslel následující zlepšovák: místo telefonního čísla si bude Truhlík pamatovat větu, která se bude skládat ze jmen večerníčkových postav takovou, že když se napíše na klávesnici telefonu, vznikne chtěné číslo. Klávesnice telefonu vypadá následovně:

123
abcdefgh
456
ijklmno
789
pqrstuvw
0
xyz

(Číslo 7951140151651 jde zapsat jako „Rumcajz a Manka“.)

Jenomže Truhlík si sám takovou větu nedokáže vymyslet, Cibulku už o pomoc kvůli panu Popletalovi požádat nestihl, a tak zbýváte jen Vy.

Na vstupu dostanete seznam slov, které si pan Truhlík dokáže zapamatovat. Tato slova se skládají pouze ze znaků `a'..`z' a celková velikost slovníku je P písmen. Dále dostanete seznam N telefonních čísel, každé o délce Ci. Vaším úkolem je pro každé telefonní číslo najít posloupnost slov ze slovníku takovou, že pokud se napíše na klávesnici, vznikne kýžené telefonní číslo, případně říci, že to není možné.

Příklad: Jsou-li ve slovníku slova „brok, kuba, je“, číslo 5911425911 můžeme nahradit větou „kuba je kuba“, ale číslo 1765911 není možné žádnou větou složenou ze slovníkových slov nahradit.

Bonus: Pokud dokážete navíc vypsat pro každé telefonní číslo takovou větu, která má ze všech možných správných vět nejmenší počet slov, Truhlík se Vám určitě bohatě (bodově) odmění za to, že si ji zapamatuje brzy.

Řešení

17-3-3 Starosta Hafák (10 bodů)

Pan Hafák se stal navzdory svému nevhodnému jménu starostou Kocourkova a jako starosta dostal za úkol starat se o bezpečnost chodců na silnicích. Nechal provést několik nezávislých odborných průzkumů a zjistil, že k největšímu počtu nehod dochází, když chodci přecházejí na zelenou. Rozhodl se tedy, že přikáže chodcům přecházet na červenou.

Slavný myslitel Cibulka mu ovšem vysvětlil, že takhle by rozhodně dopravních nehod neubylo, a poradil mu jiný způsob: pokud by všechny ulice v Kocourkově byly jednosměrné, bude šance, že nějakého chodce přejede auto, jenom poloviční.

To se Hafákovi velmi zalíbilo a ihned nechal udělal ze všech silnic jednosměrky. Při cestě domů ale zjistil, že to nebyl úplně dobrý nápad, protože už z první křižovatky, na kterou dojel, nevedla žádná silnice v jeho směru. A protože se Cibulka mezitím, mumlaje si nějaké nuly a jedničky, ztratil, budete muset Hafákovi poradit Vy.

Váš program dostane na vstupu popis silniční sítě v Kocourkově. Ta se skládá z N křižovatek a M silnic, každá silnice je obousměrná a spojuje dvě různé křižovatky. Žádné dvě silnice se mimo křižovatky nestýkají, mohou se ale mimoúrovňově křížit. Vaším úkolem je zjistit, kolik nejvýše silnic jde zjednosměrnit tak, aby bylo možné se ve výsledné zjednosměrněné síti dostat z nějaké křižovatky na jinou právě tehdy, když to šlo i v původní síti. A kromě počtu by měl Váš program vypsat, jak má zjednosměrněná síť vypadat.

Hroch v autě

Příklad: V síti N=3, M=3 se silnicemi spojujícími každé dvě křižovatky lze zjednosměrnit všechny tři silnice, výsledná síť bude vypadat třeba (1→2),(2→3),(3→1). Pokud by v síti byla ještě čtvrtá křižovatka, která by byla spojena silnicí s první křižovatkou, silnice mezi touto čtvrtou a první křižovatkou by zjednosměrnit nešla.

Řešení

17-3-4 Myslitel Cibulka (10 bodů)

Poté, co jste snadno vyřešili problémy, které Vám myslitel Cibulka (vlastním jménem Filip Bonifác Narcis Cibulka) vymyslil, získali jste si jeho respekt, a tak se rozhodl obrátit se na Vás se svým vlastním problémem.

Cibulka si vymyslel zvláštní posloupnost čísel, kterou nazval po sobě Filipova Bonifácova Narcisova Cibulkova posloupnost. (Protože si to ale nikdo nemohl zamapatovat, zkrátil to na FiBoNaCiho.) Její první dva členy jsou 1 a 2 a každý další člen jest roven součtu dvou členů předchozích. Matematicky máme tedy posloupnost {Fn}
∞
i=0
, kde F0=1, F1=2 a Fn=Fn-1+Fn-2 pro n ≥ 2.
Tato posloupnost se Cibulkovi tolik zalíbila, že se rozhodl zapisovat pomocí ní veškerá čísla, se kterými bude pracovat. Každé takto zapsané číslo je posloupnost nul a jedniček anan-1… a1a0 a jeho hodnota je ∑
n
i=0
ai·Fi. Po krátké úvaze si uvědomil, že takový zápis nebude jednoznačný (třeba 011=100), a proto vymyslil ještě normalizovaný zápis, který je stejný jako právě popsaný, jen se v něm nesmí vyskytnout dvě jedničky vedle sebe a nesmí začínat nulou (čili 11 ani 0100 není normalizované, ale 100 je).

Poté, co se dostatečně vychválil za svou genialitu, zjistil, že není schopen s takovými čísly vůbec pracovat. Už jenom je sečíst je veliký problém. A tak se nyní obrátil na Vás, zda byste mu nemohli vypomoci.

Zkuste napsat Cibulkovi program, který dostane na vstupu dvě čísla v nenormalizovaném FiBoNaCiho zápisu (tyto zápisy mají délky N a M) a vypíše zadaná čísla a jejich součet v normalizovaném tvaru. Není snad nutno dodávat, že skutečná hodnota zadaných čísel bude tak velká, že se nemůže vejít do žádného celočíselného typu (může jít o tisíce cifer ve FiBoNaCiho zápisu).

Příklad: Pro vstup 11101 a 1101 by měl Vás program vypsat 100101 + 10001 = 1001000.

Hintík: Cibulka Vám ještě prozradil, že každé nezáporné číslo v normalizovaném tvaru zapsat jde.

Řešení

17-3-5 Jazykozpytcova naděje (9 bodů)

Na jisté nejmenované univerzitě vědecky působil a samozřejmě též vyučoval nadšený lingvista, pan Choam Nomsky. Svým studentům často zadával domácí úkoly a nejčastějším úkolem bylo sestrojení konečného automatu, který má rozpoznávat nějaký zadaný jazyk. (Pro nezasvěcené: pokud netušíte, o čem je řeč, nahlédněte do zadání první série, kde jsou potřebné pojmy definovány.)

Jenže jeho studenti nepatřili zrovna k nejbystřejším a často nosili automaty, které používaly obrovské množství stavů, i když jazyk šlo rozpoznávat automatem s podstatně méně stavy. Kontrola správnosti obrovských automatů způsobovala panu Nomskému četné vrásky a bolesti hlavy, rozhodl se tedy, že před kontrolou správnosti si musí automat zjednodušit. Za zjednodušený automat, říkejme mu odborně redukovaný, považoval takový automat (Q,A,δ,q0,F) ekvivalentní s původním, který neměl žádné nedosažitelné stavy a žádné dva stavy nebyly ekvivalentní. Co to znamená:

O redukovaných automatech se dají dokázat některé zajímavé skutečnosti, například že libovolné dva ekvivalentní automaty se zredukují na stejně velký a „stejně vypadající“ automat, ale tím vás tentokrát zatěžovat nebudeme. Nyní po vás nechceme nic snazšího, než vymyslet co nejefektivnější algoritmus a posléze napsat program, který panu Choamu Nomskému usnadní jeho úděl, čili ke konečnému automatu zadanému na vstupu najde příslušný redukovaný automat (což vlastně není nic jiného než ekvivalentní automat s co nejmenším počtem stavů).

Program nejprve načte z první řádky vstupu počet stavů n (očíslujme si je tedy 1 až n), počet symbolů abecedy a (taktéž si je očíslujme 1 až a), číslo počátečního stavu p a počet přijímacích stavů f. Následuje řádek s f čísly, které udávají přijímací stavy. Pak je na vstupu n řádků, každý s a čísly. Číslo c umístěné v i-tém řádku a j-tém sloupci znamená, že δ(i,j)=c. Program by měl na výstup vypsat redukovaný automat v podobném formátu.

Příklad: vstup je vlevo, vzorový výstup vpravo.

       5 2 1 2                2 2 1 1
       1 3                    1
       1 2                    1 2
       2 3                    2 1
       3 4
       4 1
       3 5

Řešení