Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | aby.in, aby.out | Sursă | .com 2012 Runda 3 |
| Autor | Ioan Petcu | Adăugată de |  Edp100 •edp100 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 66432 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Aby
Se spune ca odata, demult , in vechea tara Lapestina exista un castel magic.
De curand maleficul Rainbowdash din Rasiel a rapit-o pe printesa Lolita, iar eroul nostru, Abu, este pregatit sa faca orice ca sa o salveze. Dupa o calatorie epica cu multe peripetii Abu afla in final ca printesa este tinuta prizoniera de Rainbowdash in ultima camera a castelului pomenit anterior.
Castelul este format din N (numerotate de la 0 la N - 1) camere si M pereti magici ce fac legatura dintre aceste camere. Peretii acestia sunt speciali si un om cu vointa puternica (cum ar fi eroul nostru) poate trece prin ei, dar numai intr-un sens prestabilit.
Deoarece eroul nostru are un dispozitiv magic de teleportare numit lucoj, el nu trebuie decat sa ajunga la Lolita(aflata in camera N - 1) trecand prin pereti incepand din prima camera (numerotata cu 0) si apoi aventura lui va lua sfarsit, intorcandu-se cu printesa acasa.
Din pacate pentru noi treaba se complica. Rainbowdash a aflat de planul lui Abu, si fiind un magician puternic el are la dispozitie urmatorul truc pentru a-l impiedica sa ajunga la Lolita: Deoarece a rostit niste incantatii magice, de fiecare data cand Abu trece printr-un perete, Rainbowdash este obligat sa aleaga o camera iar toti peretii ce au o fata spre acea camera isi vor schimba sensul magic.
Spre exemplu sa spunem ca avem un castel cu 3 camere. Exista un perete de la camera 0 la camera 1 si un perete de la camera 1 la camera 2. Abu nu se poate muta decat din camera 0 in camera 1, dupa aceasta, Rainbowdash poate vrajii fie camera 1 caz in care se schimba sensul peretilor de la 0 la 1 si de la 1 la 2, sau camera 2 ,caz in care se schimba sensul peretelui de la camera 1 la camera 2. De observat ca in acest caz Abu nu poate sa salveze printesa. Pe de alta parte daca ar mai exista inca un perete de la camera 2 la camera 1, orice ar face Rainbowdash , Abu poate ajunge in camera 2.
Abu a obtinut in calatoriile lui T harti dintre care una sigura corespunde castelului, dar nefiind sigur care dintre ele , el va roaga sa-i spuneti pentru fiecare daca este posibil sa-si salveze printesa, presupunand ca maleficul Rainbowdash nu-si greseste miscarile.
Date de intrare
Fişierul de intrare aby.in contine pe prima linie un numar T de teste, iar pe urmatoarele linii, pentru fiecare test , avem : o line cu numerele N si M iar apoi M linii continand perechi de numere X si Y semnificand faptul ca exista un perete orientat de la camera X la camera Y.
Date de ieşire
În fişierul de ieşire aby.out veti afisa T linii, fiecare linie i continand raspunsul pentru configuratia de la testul i, si anume 1 daca Abu poate ajunge in ultima camera, iar in caz contrat 0.
Restricţii si precizari
- Intre teste exista cate o linie libera
- Pot exista mai multi pereti intre doua camere
- Pot exista pereti cu ambele capete in aceeasi camera
- Dupa fiecare mutare a lui Abu, Rainbowdash este obligat sa aleaga si el o camera si s-o vrajeasca
- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 12
- 0 ≤ M ≤ 9000
- Abu si Rainbowdash isi fac miscarile optim.
Exemplu
| aby.in | aby.out |
|---|---|
| 3 3 2 0 1 1 2 3 3 0 1 1 2 2 1 5 9 0 1 1 2 2 1 1 3 4 1 3 2 4 2 3 4 4 2 | 0 1 0 |
Explicaţie
Primele doua teste au fost explicate in enunt, iar la ultimul, Abu se va muta de la 0 la 1, Rainbowdash va vrajii camera 3, Abu se va muta de la 1 la 2, rainbowdash va vrajii din nou camera 3, apoi Abu se muta de la 2 la 1... si tot asa, astfel abu nu va ajunge niciodata in ultima camera.
