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).
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 $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 $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.
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
{$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.
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$}.
Intrucat Balaurul nu are prea multa rabdare, el nu ne cere decat sa spunem daca se poate sau nu obtine sirul respectiv de perle.
Deoarece Balaurul nu are prea multa rabdare, el nu ne cere decat sa spunem daca se poate sau nu obtine sirul respectiv de perle.
h2. 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).
h2. Date de Intrare
Fisierul de intrare perle.in are urmatoarea structura:
1. pe prima linie numarul N, reprezentand numarul de siruri din fisierul de intrare
h2. Date de intrare
2. 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 L[i], iar urmatoarele L[i] numere sunt tipurile de perle normale, in ordine, de la stanga la dreapta.
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, {$L{~i~}$}, iar urmatoarele {$L{~i~}$} numere sunt tipurile de perle normale, in ordine, de la stanga la dreapta.
h2. Date de Iesire
h2. Date de iesire
Fisierul perle.out va contine N linii. Pe linia i se va scrie un singur numar 1 sau 0 (1 daca se poate obtine sirul respectiv (al i-lea) si 0 daca nu se poate).
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).
h2. Restrictii
h2. Restrictii si precizari
1. 0 < N < 11
2. 0 < L[i] < 10001, pentru oricare i
* $0 < N < 11$
* $0 < L{~i~} < 10 001$, pentru $i$ de la $1$ la $N$
h2. Exemplu
|perle.in |perle.out |
|3 |1 |
|8 2 1 1 3 2 1 2 3 | |
| |0 |
|2 2 2 | |
| |1 |
|1 3 | |
table(example). |_. perle.in|_. perle.out|
|3
8 2 1 1 3 2 1 2 3
2 2 2
1 3
|1
0
1|
==Include(page="template/taskfooter" task_id="perle")==
