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

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


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

Dintr-o regretabilă eroare, redactorul Vasile a şters toate spaţiile din textul la care lucra.
Textul este scris într-o limbă necunoscută, numai cu litere mici ale alfabetului englez. Vasile ştie că un cuvânt trebuie să conţină cel puţin o vocală şi că nu poate avea lungimea mai mare de 20 de litere. De asemenea, fiind un tip meticulos, el ştie că în text erau (înainte de ştergerea spaţiilor) exact N cuvinte.
Vasile trebuie să restaureze textul, inserând spaţii între cuvinte. Cum există numeroase modalităţi de restaurare a textului, Vasile a hotărât să aleagă varianta în care literele sunt distribuite în cuvinte într-un mod cât mai armonios. Pentru a măsura armonia, Vasile a calculat suma pătratelor lungimilor cuvintelor. Textul este cu atât mai armonios, cu cât suma obţinută este mai mică.

Cerinţă

Dat fiind textul fără spaţii, să se determine câte posibilităţi de restaurare există (în total, indiferent de armonia lor), precum şi cea mai armonioasă modalitate de restaurare.

Date de intrare

Fişierul de intrare text.in conţine pe prima linie textul fără spaţii. Pe cea de a doua linie este scris numărul natural N, reprezentând numărul de cuvinte din textul iniţial.

Date de ieşire

Fişierul de ieşire text.out va conţine pe prima linie un număr natural reprezentând numărul total de posibilităţi de restaurare modulo 1 000 003 (restul împărţirii la 1 000 003). Pe cea de-a doua linie va fi scrisă măsura armoniei textului restaurat (suma minimă a pătratelor lungimilor cuvintelor din text). Pe a treia linie va fi scris cel mai armonios text obţinut după restaurare. Între orice două cuvinte consecutive va fi scris un singur spaţiu.

Restricţii

0 < Lungimea şirului ≤ 200
Vocalele alfabetului englez sunt ′a′, ′e′, ′i′, ′o′, ′u′, ′y′.
Pentru datele de test există întotdeauna soluţie.
Dacă există mai multe soluţii optime de restaurare, va fi scrisă prima variantă în ordine lexicografică (se ştie că ′ ′<′a′).
Şirul (x1, x2, ..., xn) este mai mic lexicografic decât (y1, y2, ..., yn) dacă există k (1≤k≤n) astfel încât xi=yi (pentru orice 1≤i<k) şi xk<yk.
Pentru 40% dintre teste lungimea textului este <70 şi N≤7.
Punctajul pe test se va acorda astfel: 50% pentru numărul total de modalităţi de restaurare modulo
1 000 003; 80% pentru numărul de modalităţi de restaurare modulo 1 000 003 şi suma minimă; 100% pentru rezolvarea corectă a tuturor cerinţelor.

Exemple

text.intext.outExplicaţii
bcaeiouxtz 3 6 34 bca eio uxtz Posibilităţile de restaurare sunt:
bca eio uxtz (armonie: 9+9+16=34)
bca ei ouxtz (armonie: 9+4+25=38)
bca e iouxtz (armonie: 9+1+36=46)
bcae io uxtz (armonie: 16+4+16=36)
bcae i ouxtz (armonie: 16+1+25=42)
bcaei o uxtz (armonie: 25+1+16=42)
Varianta cea mai armonioasă este bca eio uxtz.

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2009: bile, checkin, numere, reactii, volei, magic2, sirag, taste, tetris, origami, rafturi, joc2, br, reinvent, perspic, tir, patrate2, nrcuv2, matrice, patrate1, pikachu, taxe, cartonas, case, desen2
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, 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, 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 şiruri de caractere: scp, ab, sl, nrcuv, rv, kpal, chimie, reteta, replace, grad, index, cod, 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, 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, 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, randuri, 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
Software recomandat
Chestionare recomandate
surse trimise | ajutor