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

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


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

Andrei, un tânăr cu un real talent literar, va recita la următoarea întâlnire a cenaclului literar ultimul său poem. O singură problemă are Andrei: poemul are prea multe rânduri şi este conştient că nimeni nu va avea răbdare
să-l asculte până la capăt. Pentru că nu mai are timp să-l rescrie, Andrei s-a hotărât să elimine rânduri din poem. Totuşi, nu va elimina rânduri la întâmplare, ci le va alege astfel încât valoarea artistică a poemului să nu se diminueze. După îndelungi frământări, poetul a descoperit criteriul de eliminare: un rând se poate elimina doar dacă imediat înaintea sa se află un rând (să-l notăm p), iar imediat după el se află un alt rând (să-l notăm u) astfel încât rândurile p şi u au muzicalitatea strict mai mare decât 6. Nu întrebaţi de ce 6, doar Andrei ştie de ce.
Ce înţelege poetul prin muzicalitatea a două rânduri ?
Fie rândurile: alinuta este acasa şi alin merge cu noi. Muzicalitatea este egală cu 9, adică exact numărul caracterelor scrise cu bold: alin ee c . Aşadar, muzicalitatea reprezintă dimensiunea celei mai lungi succesiuni formată din caractere ce apar în ordinea din succesiune atât în primul rând, cât şi în cel de al doilea, pe poziţii nu neapărat consecutive.
Astfel, rândul care este precedat, respectiv urmat de acestea două poate fi eliminat, pentru că 9>6. Evident, dacă eliminăm rândul existent între p şi u, rândurile p şi u devin consecutive.

Cerinţă

Determinaţi numărul maxim de rânduri care pot fi eliminate, respectând criteriul stabilit de poet.

Date de intrare

Fişierul de intrare randuri.in conţine rândurile poemului, câte unul pe linie.

Date de ieşire

Fişierul de ieşire randuri.out va conţine o singură linie pe care va fi scris numărul maxim de rânduri care pot fi eliminate, respectând criteriul stabilit de poet.

Restricţii

Rândurile sunt formate din maxim 100 caractere cu codul ASCII < 127.
Nu există rânduri goale.
Fişierul de intrare conţine cel mult 100 de rânduri.
Orice linie din fişierul de intrare se termină cu marcajul de sfârşit de linie (newline). Caracterul newline nu va fi va fi considerat ca făcând parte din rând.

Exemple

randuri.inranduri.outExplicaţii
Te-nalta pana-n nori Tot mai sus, Tot mai departe Ca siragul de cocori 2 Muzicalitatea rândurilor:
Te-nalta pana-n nori
Tot mai departe

este 7 (vezi caracterele scrise cu bold).
Prin urmare poate fi eliminat rândul
Tot mai sus,
După eliminarea acestui rând, obţinem:
Te-nalta pana-n nori
Tot mai departe
Ca siragul de cocori

Muzicalitatea rândurilor:
Te-nalta pana-n nori
Ca siragul de cocori

este 7. Prin urmare, se poate elimina şi rândul:
Tot mai departe

autor: Prof. Constantin Gălăţan
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, zidar, desc, felinar, joc6, log, maxq, tric, cover, dist, munte1, promo, puncte1, role
De acelaşi autor: ozn, pod, numere, vikingi, furtuna, livada, teatru, iepuras2, kimberley, novel, friends2, stalpi, tabara, sport, panouri, powerpuff, cartele, joc15, stalpi1, autostrazi, telecab, pseudobil, harta2
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, 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, dp, 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 programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
Chestionare recomandate
surse trimise | ajutor