peg

Peg

== include(page="template/taskheader" task_id="peg") ==

Poveste si cerinta...

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).
 
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$.
 
Jocul se termina cu succes atunci cand pe tabla ramane 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$ ...

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.

h2. Date de iesire

In fisierul de iesire $peg.out$ ...

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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* {$1 ≤ T ≤ 10$}
* {$1 ≤ Lungimea oricarei configuratii ≤ 150 000$}
 

h2. Exemplu
table(example). |_. peg.in |_. peg.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
  1
  110
  001111010
  1101110
  11
| 1
  1
  1
  0
  0

|
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") ==

3134