Fişierul intrare/ieşire:peg.in, peg.outSursăLot 2006 Alba
AutorEmanuela CerchezAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inpeg.out
5
1
110
001111010
1101110
11
1
1
1
0
0

Explicatie

  1. Jocul se termina cu succes in 0 mutari.
  2. Jocul se termina cu succes intr-o singura mutare (primul jeton sare peste cel de al doilea).
  3. Jocul se termina cu succes in 4 mutari: 001111010->001100110->000010110->000011000->000100000
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content