E - Myš rúrovitá I.Časový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Psychológovia sa rozhodli, že na skúmanie ľudskej mysle zvolia novú metódu - budú pozorovať správanie myší. Uvedomili si totiž, že taký myš a človek majú toho veľa spoločného. Vytvorili preto experiment. V laboratórnom prostredí postavili pozdĺžne vedľa seba niekoľko rúr a každej z nich pridelili jednoznačný identifikátor obsahujúci práve štyri veľké písmená anglickej abecedy a jednu číslicu. Následne postavili nad rúrami veľkú stenu, čím rozdelili celé laboratórium na dve časti, pričom jediná cesta medzi dvoma časťami bola cez rúry. Cieľom pokusu bolo vystaviť myš niekoľkým psychologickým sedeniam a na nich ju prinútiť, aby prebehla každou rúrou práve raz tak, aby sa jej cesta nikdy neprekrížila. Myš začína pritom v niektorej rúre a celú cestu si vyberá sama. Experiment sa končí, keď prebehne každou rúrou práve raz a zastane na mieste, na ktorom začínala. ÚlohaVašou úlohou je analyzovať zápis experimentu a zistiť, či bol úspešný. Dostanete teda zoznam rúr a zápis cesty myši. Samotný zoznam rúr nie je nutne zhodný s reálnym rozložením. Môžete si teda zvoliť akékoľvek poradie tak, aby bol experiment úspešný (ak taká možnosť existuje).VstupPrvý riadok vstupu obsahuje prirodzené párne číslo, počat rúr N (1≤N≤50 000). Ďalej nasleduje N riadkov, každý obsahuje identifikátor rúry pozostávajúci zo štyroch veľkých písmen a jedného čísla. Za nimi nasleduje N+1 riadkov, popis cesty myši vo forme identifikátora rúry, cez ktorú myš prebehla. Môžete si byť istý, že každá rúra sa v ceste nachádza práve raz, pričom začiatok a koniec cesty je totožný.VýstupNa výstupe je potrebné napísať jediný riadok obsahujúci slovo "Ano", ak je možné, že sa cesta myši nikdy neprekrížila alebo slovo "Nie", ak sa určite musela prekrížiť.PríkladVstup:4 EFGH1 ABCD1 EFGH2 ABCD2 ABCD1 EFGH1 ABCD2 EFGH2 ABCD1 Výstup:Ano Vysvetlenie:Myš začína v rúre ABCD1. Následne vybehne von a vbehne do rúry EFGH1, ňou prebehne na druhú stranu laboratória, vybehne z nej von a následne vbehne do rúru ABCD2. Cez ňu prebehne a vbehne do EFGH2. Z nej vybehne a vbehne do ABCD1, v ktorej pôvodne začínala. Existuje teda cesta, ktorá sa nikdy nemusí prekrížiť (viď obrázok). |