Peg Solitaire este un joc pentru un singur jucător. Tabla de joc este o bandă cu N poziţii. Pe fiecare poziţie poate fi plasat un singur jeton.
Orice configuraţie de joc poate fi codificată ca o secvenţă binară de lungime N, unde 1 reprezintă un jeton, iar 0 reprezintă o poziţie liberă.
O mutare este un salt la stânga sau un salt la dreapta.
În saltul la dreapta jetonul de pe poziţia i sare peste jetonul de pe poziţia i+1; jetonul de pe poziţia i+1 este eliminat; jetonul de pe poziţia i ajunge pe poziţia i+2 (aceasta trebuie să fie liberă).
În saltul la stânga jetonul de pe poziţia i sare peste jetonul de pe poziţia i-1; jetonul de pe poziţia i-1 este eliminat; jetonul de pe poziţia i ajunge pe poziţia i-2 (aceasta trebuie să fie liberă).
De exemplu:
În configuraţia 011 sare la stânga jetonul de pe poziţia 3 peste jetonul de pe poziţia 2 şi se obţine configuraţia 100.
În configuraţia 110 sare la dreapta jetonul de pe poziţia 1 peste jetonul de pe poziţia 2 şi se obţine configuraţia 001.
Jocul se termină cu succes atunci când pe tablă rămâne un singur jeton.
Cerinţă
Dat fiind un set de configuraţii, să se determine pentru care configuraţii din set jocul se termină cu succes.
Date de intrare
Fişierul de intrare peg.in conţine pe prima linie un număr natural nenul T, reprezentând numărul de configuraţii din fişier. Pe fiecare dintre următoarele T linii se află câte o secvenţă binară reprezentând o configuraţie de joc.
Date de ieşire
Fişierul de ieşire peg.out va conţine T linii, câte una pentru fiecare configuraţie. Pe linia i va fi scrisă cifra 1 dacă pentru cea de a i-a configuraţie din fişierul de intrare jocul se termină cu succes, respectiv cifra 0 în caz contrar.
Configuraţia 1: jocul se termină cu succes în 0 mutări.
Configuraţia 110: jocul se termină cu succes într-o singură mutare (primul jeton sare peste cel de al doilea)
Configuraţia 001111010: jocul se termină cu succes în 4 mutări 001111010→001100110→000010110→000011000→000100000