Peg Solitaire este un joc pentru un singur jucator. Tabla de joc este o banda cu $N$ pozitii. Pe fiecare pozitie poate fi plasat un singur jeton.
Orice configuratie de joc poate fi codificata ca o secventa binara de lungime $N$, unde $1$ reprezinta un jeton, iar $0$ reprezinta o pozitie libera.
O mutare este un salt la stanga sau un salt la dreapta.
* In saltul la dreapta jetonul de pe pozitia $i$ sare peste jetonul de pe pozitia $i+1$; jetonul de pe pozitia $i+1$ este eliminat; jetonul de pe pozitia $i$ ajunge pe pozitia $i+2$ (aceasta trebuie sa fie libera).
* In saltul la stanga jetonul de pe pozitia $i$ sare peste jetonul de pe pozitia $i-1$ ; jetonul de pe pozitia $i-1$ este eliminat; jetonul de pe pozitia $i$ ajunge pe pozitia $i-2$ (aceasta trebuie sa fie libera).
O mutare este un salt la stânga sau un salt la dreapta.
In saltul la dreapta jetonul de pe poziţia $i$ sare peste jetonul de pe poziţia $i+1$; jetonul de pe pozitia $i+1$ este eliminat; jetonul de pe poziţia $i$ ajunge pe poziţia $i+2$ (aceasta trebuie sa fie libera).
In saltul la stanga jetonul de pe poziţia $i$ sare peste jetonul de pe pozitia $i-14; jetonul de pe pozitia $i-1$ este eliminat; jetonul de pe pozitia $i$ ajunge pe pozitia $i-2$ (aceasta trebuie sa fie libera).
De exemplu:
In configuratia $011$ sare la stanga jetonul de pe pozitia $3$ peste jetonul de pe pozitia $2$ si se obtine configuratia $100$.
In configuratia $110$ sare la dreapta jetonul de pe pozitia $1$ peste jetonul de pe pozitia $2$ si se obtine configuratia $001$.
* In configuratia $011$ sare la stanga jetonul de pe pozitia $3$ peste jetonul de pe pozitia $2$ si se obtine configuratia $100$.
* In configuratia $110$ sare la dreapta jetonul de pe pozitia $1$ peste jetonul de pe pozitia $2$ si se obtine configuratia $001$.
Jocul se termina cu succes atunci cand pe tabla ramane un singur jeton.
Jocul se termină cu succes atunci când pe tablă rămâne un singur jeton.
h2. Cerinta
Dat fiind un set de configuratii, sa se determine pentru care configuratii din set jocul se termina cu succes.
h2. Date de intrare
Fisierul de intrare $peg.in$ contine pe prima linie un numar natural nenul $T$, reprezentand numarul de configuratii din fisier. Pe fiecare dintre urmatoarele $T$ linii se afla cate o secventa binara reprezentand o configuratie de joc.
Fisierul de intrare $peg.in$ ...
h2. Date de iesire
Fisierul de iesire $peg.out$ va contine $T$ linii, cate una pentru fiecare configuratie. Pe linia $i$ va fi scrisa cifra $1$ daca pentru cea de a i-a configuratie din fisierul de intrare jocul se termina cu succes, respectiv cifra $0$ in caz contrar.
In fisierul de iesire $peg.out$ ...
h2. Restrictii
* {$1 ≤ T ≤ 10$}
* {$1 ≤ Lungimea oricarei configuratii ≤ 150 000$}
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. peg.in |_. peg.out |
| 5
1
110
001111010
1101110
11
| 1
1
1
0
0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
# Jocul se termina cu succes in {$0$} mutari.
# Jocul se termina cu succes intr-o singura mutare (primul jeton sare peste cel de al doilea).
# Jocul se termina cu succes in {$4$} mutari: {$001111010->001100110->000010110->000011000->000100000$}
...
== include(page="template/taskfooter" task_id="peg") ==
