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

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


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

Se consideră un text format numai din litere mici şi N cuvinte formate de asemenea numai din litere mici. Oricare două cuvinte se pot combina prin întrepătrunderea literelor lor, dar fără a schimba ordinea literelor. De exemplu, abc şi xyzt pot obţine prin combinare abcxyzt sau abxcyzt sau xaybczt, dar nu se poate obţine axbczyt, deoarece y trebuia să apară înaintea lui z, aşa cum este iniţial în xyzt.

Cerinţă

Scrieţi un program care să verifice numărul perechilor de cuvinte din cele N date iniţial care obţin prin combinare o subsecvenţă a textului.

Date de intrare

Fisierul de intrare combcuv.in conţine pe prima linie textul, pe a doua linie un număr natural N, iar pe următoarele N linii se află câte un cuvânt.

Date de ieşire

Fisierul de iesire combcuv.out va conţine un singur număr natural reprezentând numărul de perechi de cuvinte care prin combinare obţin o subsecvenţă a textului.

Restricţii

  • Textul conţine cel mult 200 de litere mici; textul nu conţine spaţii.
  • Orice cuvânt conţine cel puţin o literă şi cel mult 30
  • 2 <= N <= 100

Exemple

combcuv.in combcuv.out Explicaţii
faacbtbacabb
5
abac
acbta
bt
cb
atcb
2 Textul este faacbtbacabb şi sunt 5 cuvinte.
Combinând perechea de cuvinte (abac, acbta) putem obţine aacbtbaca, care este subsecvenţă a textului.
Combinând perechea de cuvinte (bt, cb) putem obţine cbtb, care este subsecvenţă a textului.
De remarcat că perechea (abac, atcb) nu poate obţine prin combinare subsecvenţa aacbtbac.

prof. Dan Pracsiu
Grupul Şcolar „Ştefan Procopiu” Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la XOR 2012: proddiv, perechi2, expeval, maxtri, dfs
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, 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, dominant
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, dp, cuvant, strings, antipatie, fractie1, links, ordonare, text3, concat, codif, cheie, alfabetar, cuvinte2, comp, litere, mxl, mesaj3, expresie2, grad2, antic, zuma, expeval, 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, 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, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Chestionare recomandate
surse trimise | ajutor