Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (2. soutěžní den) 54. ročníku

P-III-4 Zaklínadla

Program: magie.pas / magie.c / magie.cpp
Vstup: magie.in
Výstup: magie.out

Při výzkumu vlivu přesmyček na magická zaklínadla se podařilo dokázat, že výměna takových dvou sousedních písmen v zaklínadle, která se nevyskytují v (anglické) abecedě těsně vedle sebe, nemá vliv na magický účinek zaklínadla. Například místo oblíbeného abraka lze stejně dobře použít arbaka, ale nikoliv již baraka. Samozřejmě lze sousední písmena v zaklínadle prohazovat vícekrát, takže z abraka lze postupně odvodit následující (stejně účinná) zaklínadla:
abraka -> arbaka -> rabaka -> rabkaa -> rakbaa -> rkabaa -> krabaa.
Povšimněte si, že pořadí výměn sousedních písmen v zaklínadle můžeme otočit, a tedy ze zaklínadla krabaa lze též získat původní abraka.

Dvě zaklínadla nazveme ekvivalentní, jestliže je lze mezi sebou převést posloupností výměn dvou sousedních písmen, která se nevyskytují v abecedě těsně vedle sebe. Například zaklínadla abraka a krabaa jsou ekvivalentní, ale zaklínadla dabra a badar ne.

Soutěžní úloha

Napište program, který pro zadané dvojice zaklínadel určí, zda jsou či nejsou ekvivalentní.

Vstup:

Vstupní soubor magie.in obsahuje několik bloků, z nichž každý odpovídá jedné dvojici zaklínadel. Obě zaklínadla v jednom bloku mají vždy stejný počet písmen N, 1≤ N≤ 1,000,000, který je uveden na prvním řádku každého bloku. Následuje N řádků, z nichž každý obsahuje dvě malá písmena anglické abecedy (tzn. znaky z rozmezí a...z), která jsou oddělená jednou mezerou. První znak na i-tém z těchto řádků je i-tý znak prvního zaklínadla, druhý znak je i-tý znak druhého zaklínadla. Vstupní soubor je ukončen řádkem, který obsahuje jediné číslo 0.

Výstup:

Výstupní soubor magie.out obsahuje pro každý blok vstupního souboru jeden řádek. Tento řádek obsahuje slovo „ekvivalentni”, pokud jsou zadaná zaklínadla ekvivalentní, a slovo „neekvivalentni”, pokud nejsou. Řádky musí být vypsány v pořadí, v jakém se jim odpovídající bloky vyskytují v souboru magie.in.

Příklad:

Soubor magie.in:

6
a k
b r
r a
a b
k a
a a
5
d b
a a
b d
r a
a r
0

Soubor magie.out:

ekvivalentni
neekvivalentni

P-III-5 Asfaltéři

Program: asfalt.pas / asfalt.c / asfalt.cpp
Vstup: asfalt.in
Výstup: asfalt.out

Ve Viácii si občané již dlouho stěžovali na nekvalitní silnice. Když si jednou i vrchní cestář při cestě do práce v kočáře vyrazil zub, rozhodl se k radikální akci. Doslechl se, že v sousední zemi začali na cesty používat novinku zvanou asfalt, a myšlenka na vyasfaltování všech silnic ve Viácii byla na světě. A jak si vrchní cestář usmyslel, tak se i stalo. Při realizaci nápadu se ale nižší cestáři museli potýkat s nemilým problémem: asfalt se do Viácie dovážel v ohromných barelech, ve kterých bylo asfaltu tak akorát na dvě cesty (byly to opravdu ohromné barely). Potíž byla v tom, že jakmile se barel narazil a asfalt z něj začal vytékat, nedal se už proud asfaltu ničím zastavit a bylo tedy nutné vyasfaltovat najednou dvě na sebe navazující cesty. Jenže jak rozvrhnout asfaltování, aby cestáři neskončili ve městě s poloplným barelem a se všemi cestami vedoucími do města už vyasfaltovanými? Důsledky zalití náměstí a několika přilehlých čtvrtí do asfaltu by byly pro cestáře jistě nemilé... Rozhodli se proto přizvat k problému vás, jakožto na asfalt vzaté odborníky.

Soutěžní úloha

Napište program, který pro zadané propojení měst cestami rozhodne, zda je možno cesty podle popsaných pravidel vyasfaltovat, a pokud ano, vypíše jednu z možností, jak rozvrhnout, která dvojice cest bude asfaltována ze kterého barelu.

Vstup:

Na prvním řádku vstupního souboru asfalt.in se nacházejí dvě celá čísla N a M oddělená mezerou, 1 ≤ N ≤ 10,000, 1 ≤ M ≤ 40,000 — počet měst a počet cest ve Viácii. Dále ve vstupním souboru následuje M řádků popisujících jednotlivé cesty. Každý řádek obsahuje dvě celá čísla A a B oddělená mezerou — čísla měst (města číslujeme od jedné do N), mezi kterými cesta vede. Předpokládejte, že mezi každými dvěma městy se lze po cestách dostat (pokud ne přímo, tak přes jiná města).

Výstup:

Výstupní soubor asfalt.out bude buď obsahovat jediný řádek s textem „Cesty nelze vyasfaltovat.”, pokud neexistuje způsob, jak vyasfaltovat všechny cesty a neskončit s poloplným barelem v nějakém městě, nebo bude obsahovat M/2 řádků s popisem postupu asfaltování. Každý řádek postupu bude popisovat využití jednoho barelu s asfaltem. Bude obsahovat tři celá čísla oddělená mezerou — číslo města, ve kterém má asfaltování začít, číslo města, do kterého se má pokračovat a číslo města, ve kterém má asfaltování skončit. Každá cesta musí být vyasfaltována právě jednou.

Příklad 1:

Soubor asfalt.in:

Soubor asfalt.out:

Cesty nelze vyasfaltovat.

Příklad 2:

Soubor asfalt.in:

Soubor asfalt.out: