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

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


Timp maxim de execuţie/test:
0.1 secunde
Memorie totală disponibilă/stivă:
32 MB/1 MB

Considerând un şir de valori binare, numim secvenţă dominantă un set de elemente aflate pe poziţii consecutive în şir care are proprietatea că numărul valorilor egale cu 1 este strict mai mare decât numărul valorilor de 0.
De exemplu, în şirul 1,0,0,0,1,1,0,1,1,1,0,0 o secvenţă dominantă este 0,1,1 şi o alta, de lungime mai mare, este 0,1,1,0,1,1,1. Secvenţa dominantă maximală este secvenţa dominantă de lungime maximă. În şirul din exemplu secvenţa dominantă maximală este 1,0,0,0,1,1,0,1,1,1,0 (adică întreg şirul, fără ultimul zero).

Cerinţă

Dat un şir de valori binare, să se determine lungimea unei secvenţe dominante maximale precum şi numărul acestor secvenţe.

Date de intrare

Fişierul de intrare dominant.in conţine pe prima linie un număr natural V, iar pe linia a doua şirul de valori binare, fără spaţii.

Date de ieşire

Fişierul de ieşire dominant.out va conţine:

  • varianta 1: dacă V=1, atunci pe prima linie a fişierului de ieşire va fi un singur număr natural reprezentând lungimea unei secvenţe dominante maximale.
  • varianta 2: dacă V=2, atunci pe prima linie a fişierului de ieşire va fi un singur număr natural reprezentând numărul secvenţelor dominante maximale.

Restricţii

  • V ia valori din mulţimea {1,2}
  • Lungimea şirului de valori binare este de cel mult 300 000.
  • Pentru toate testele, şirul binar va conţine cel puţin o valoare de 1.
  • Pentru 60% din punctaj V = 1

Exemplu

dominant.in dominant.out Explicaţii
1
100011011100
11

Secvenţa dominantă maximală este 10001101110 şi are lungimea 11.

dominant.in dominant.out Explicaţii
2
100011011100
1

Secvenţa dominantă maximală este 10001101110 şi are lungimea 11. Este o singură secvenţă dominantă maximală.

dominant.in dominant.out Explicaţii
1
0000110000111
9

Secvenţa dominantă maximală are lungime 9; aceasta este 110000111.

dominant.in dominant.out Explicaţii
2
10000111000
3

Secvenţa dominantă maximală are lungimea 5. Sunt trei secvenţe dominante maximale: 00111, 01110 şi 11100.

prof. Dan Pracsiu
Liceul "Stefan Procopiu" Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la OJI 2015: panda, charlie, ech, lasere, 2sah, dragoni, arc, defrag, pavare1, ordine, covor1, speciale, cuart
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, ratb, 2sec, sport, pikachu, suma3, panouri, sir5, mare, hof, resturi, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, lcdr, 3max, ksecv, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, restaurare, roua
surse trimise | ajutor