.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » peg

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
peg


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 1MB

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.

Restricţii

1 ≤ T ≤ 10
1 ≤
Lungimea oricărei configuraţii ≤ 150 000

Exemple

peg.inpeg.outExplicaţii
5 1 110 001111010 1101110 11 1 1 1 0 0 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

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot AB 2006: bcolor, poze, import, oypara, perfect, ab3, camion1, soc
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre Inducţie matematică: 2sir, h, gray, poligon, patrate1, set, descfib, suma1, mutare, sir1, prieteni1, excursie1, galax, prieteni2, perfect, borcane, regine, comoara2, domino, arctir, partitie, acoperire1, xpn
Software recomandat
surse trimise | ajutor