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

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


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

Să considerăm un şir s=s0s1s2...sn-1 format numai din caracterele 0 şi 1. Printr-o permutare circulară a şirului s obţinem şirul s1s2...sn-1s0.
De exemplu, din şirul s=01011 se obţin prin permutări circulare următoarele şiruri:
10110, 01101, 11010, 10101, 01011
Şirul s se numeşte primitivă dacă el este cel mai mic lexicografic considerând toate şirurile ce se pot obţine din el prin permutări circulare.
Observaţi că şirul 01011 este primitivă.
Orice şir poate fi scris în mod unic ca o concatenare de primitive s=P1P2...Pk, astfel încât:
- Pi+1<Pi, pentru orice i=1, 2, ..., k-1;
- PiPi+1 nu este primitivă, pentru orice i=1, 2, ..., k-1.
Vom denumi această scriere descompunere primitivă a şirului s.

Cerinţă

Scrieţi un program care să determine pentru un şir binar dat descompunerea sa primitivă.

Date de intrare

Fişierul de intrare dp.in conţine o singură linie pe care este scris şirul binar dat.

Date de ieşire

Fişierul de ieşire dp.out va conţine o singură linie pe care va fi scrisă descompunerea primitivă a şirului dat. Fiecare primitivă va fi scrisă încadrată între paranteze rotunde.

Restricţii

  • 1 <= Lungimea şirului dat <= 100
  • Spunem că şirul s=s0s1...sn-1 este mai mic din punct de vedere lexicografic decât şirul t=t0t1...tn-1 dacă există un indice i astfel încât sj=tj, pentru orice j=0, 1, ..., i-1 şi ti<si.

Exemple

dp.in dp.out dp.in dp.out
10010 (1)(001)(0)
110101111011
(11)(0101111011)

prof. Emanuela Cerchez
Liceul de Informatică „Grigore Moisil” Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, basm, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
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, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, 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 şiruri de caractere: scp, ab, sl, nrcuv, rv, kpal, chimie, reteta, replace, grad, index, cod, text, decript, spam, complex, cifre, anagrame, balbe, criptmat, mesaj, maxim, astre, sablon, formule, ed, balls, vocale, prop, bacan, novel, bitslang, text2, ref, scor2, convert, cod2, compress, pstring, sub, rima, program1, sms, circular, randuri, cezar, bifo, joc9, pal, bare, joc12, fractie, cod3, tunel, csir, top, ratina, cifru1, limbaj, adun, ecuatii, dir, paritate, virus, sir6, mesaj2, text1, sirul, ogorul, rez, sablon1, anag, sir8, seti, secvsir, cuvant, strings, antipatie, fractie1, links, ordonare, text3, concat, codif, cheie, alfabetar, cuvinte2, comp, litere, mxl, mesaj3, expresie2, grad2, antic, zuma, expeval, combcuv, lgdrum, subtitrare, compresie, zigzag, azeval, fraze, subsecvente, showroom, rebus1, agenda, opmult, betisoare, reziston, clase, vot2, ecp, smiley, charlie, cript, scadere, spioni1, sablon3, expand, culori3, virgule
Despre Greedy: lac, sumdif, checkin, baby, startrek, placi, gramezi, mese, jobs, politics, joc3, playlist, carte, exam, subperm, piloti, barca1, pitici, bombe, pic, bac, pal, antena, culmi, numar2, lover, sant1, volei1, ab3, camion1, aranjare, popas, reactivi, mesaj2, jocv, segm, calorii, album, kdtree, sport2, telecab, dag, cifre4, micro, triburi, testament, nor, eoliene, vintage, cifre5, agenda, monede2, charlie, scadere, barci
Software recomandat
Chestionare recomandate
surse trimise | ajutor