Fişierul intrare/ieşire:perle.in, perle.outSursăOJI 2004
AutorMarius AndreiAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Perle

Granita nu se trece usor. Asta pentru ca Balaurul Arhirel (mare pasionat de informatica) nu lasa pe nimeni sa treaca decat dupa ce raspunde la niste intrebari!

In acea tara exista 3 tipuri de perle normale (le vom nota cu 1, 2 si 3) si 3 tipuri de perle magice (le vom nota cu A, B si C). Perlele magice sunt deosebite prin faptul ca se pot transforma in alte perle (una sau mai multe, normale sau magice).

Perla magica de tipul A se poate transforma in orice perla normala (una singura).

Perla magica de tipul B se poate transforma intr-o perla normala de tipul 2 si una magica de tipul B, sau intr-o perla normala de tipul 1, una magica de tipul A, una normala de tipul 3, una magica de tipul A si una magica de tipul C.

Perla magica de tipul C se poate transforma intr-o perla normala de tipul 2 sau intr-o perla normala de tipul 3, una magica de tipul B si una magica de tipul C sau intr-o perla normala de tipul 1, una normala de tipul 2 si una magica de tipul A.

Ca sa rezumam cele de mai sus putem scrie:

       A -> 1 | 2 | 3
       B -> 2B | 1A3AC
       C -> 2 | 3BC | 12A

Balaurul Arhirel ne lasa la inceput sa ne alegem o perla magica (una singura), iar apoi folosind numai transformarile de mai sus trebuie sa obtinem un anumit sir de perle normale. Cand o perla magica se transforma, perlele din stanga si din dreapta ei raman la fel (si in aceeasi ordine). De asemenea ordinea perlelor rezultate din transformare este chiar cea prezentata mai sus.

De exemplu, daca balaurul ne cere sa facem sirul de perle 21132123, putem alege o perla magica de tipul B si urmatorul sir de transformari: B -> 2B -> 21A3AC -> 21A3A12A -> 21132123.

Deoarece Balaurul nu are prea multa rabdare, el nu ne cere decat sa spunem daca se poate sau nu obtine sirul respectiv de perle.

Cerinta

Sa se determine pentru fiecare sir de intrare daca se poate obtine prin transformarile de mai sus sau nu (alegand orice prima perla magica, la fiecare sir).

Date de intrare

Fisierul de intrare perle.in are urmatoarea structura: pe prima linie numarul N, reprezentand numarul de siruri din fisierul de intrare. Urmeaza N linii; a i-a linie dintre cele N descrie sirul i, printr-o succesiune de numere naturale despartite de cate un spatiu. Primul numar reprezinta lungimea sirului, Li, iar urmatoarele Li numere sunt tipurile de perle normale, in ordine, de la stanga la dreapta.

Date de iesire

Fisierul de iesire perle.out va contine N linii. Pe linia i se va scrie un singur numar 1 sau 0 (1 daca se poate obtine sirul al i-lea si 0 daca nu se poate).

Restrictii si precizari

  • 0 < N < 11
  • 0 < Li < 10 001, pentru i de la 1 la N

Exemplu

perle.inperle.out
3
8 2 1 1 3 2 1 2 3
2 2 2
1 3
1
0
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content