| Fişierul intrare/ieşire: | peg.in, peg.out | Sursă | Lot 2006 Alba |
| Autor | Emanuela Cerchez | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Peg
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.
Cerinta
Dat fiind un set de configuratii, sa se determine pentru care configuratii din set jocul se termina cu succes.
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.
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.
Restrictii
- 1 ≤ T ≤ 10
- 1 ≤ Lungimea oricarei configuratii ≤ 150 000
Exemplu
| peg.in | peg.out |
|---|---|
| 5 1 110 001111010 1101110 11 | 1 1 1 0 0 |
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
