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

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


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

Balaurul Arhirel se decide să înveţe biologie, aşa că doreşte să cumpere manualul de clasa a X-a. Din păcate, acesta nu se mai găseşte pe piaţă, dar Balaurul reuşeşte să găsească o copie la un prieten. După ce începe să citească, Balaurul Arhirel observă că există greşeli în copia prietenului, iar într-un impuls de energie, se hotărăşte să corecteze manualul. El are la dispoziţie un dicţionar de M cuvinte dintre care trebuie să extragă variante pentru cuvântul greşit. Asupra cuvântului greşit balaurul poate să facă următoarele schimbări în aşa fel încât acesta să ajungă la o variantă din dicţionar:
– poate şterge o literă ;
– poate insera o literă ;
– poate schimba o literă în altă literă.
Totuşi, Balaurul Arhirel este leneş, aşa că nu doreşte să opereze mai mult de K schimbări în cuvântul greşit pentru a-l aduce la o formă corectă (existentă în dicţionar).

Cerinţă

Ajutaţi-l pe Balaurul Arhirel să afle care dintre cuvintele din dicţionar ar putea fi variante ale cuvântului greşit.

Date de intrare

Fişierul de intrare cuvinte1.in conţine pe prima linie cele două numere M şi K, separate printr-un spaţiu, reprezentând numărul de cuvinte din dicţionar şi numărul maxim de modificări ce pot fi efectuate asupra cuvântului ce trebuie corectat. Pe a doua linie se găsesc separate printr-un spaţiu lungimea cuvântului greşit, Lcuvânt, şi cuvântul greşit. Pe următoarele M linii se găsesc cuvintele din dicţionar, câte un cuvânt pe o linie în forma următoare: pe linia i lungimea Li-2 a cuvântului i-2, separată printr-un singur spaţiu de cuvântul i-2.

Date de ieşire

Fişierul de ieşire cuvinte1.out va conţine M linii. Pe linia i se află valoarea 1 pentru cazul în care cuvântul i din dicţionar este o variantă pentru cuvântul greşit dat, respectiv valoarea 0 în caz contrar.

Restricţii

0 < M < 21
0 < K < 31
0 <
lungimea oricărui cuvânt (inclusiv cel greşit) < 10001
Cuvintele sunt formate doar din literele alfabetului latin, iar literele mici diferă de cele mari (de exemplu, Z nu este acelaşi lucru cu z).

Exemple

cuvinte1.incuvinte1.out
6 2 6 radiux 5 ladin 6 Radius 6 ridica 5 radio 6 adipos 5 cadiu 0 1 0 1 0 1

autor: Marius Andrei
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2004: gaina, materom, puncte3, rez, sortari, base3, coach, color, magic5, patrate6, turnuri, invsort, peri, trans, politie, sea, poligon3, sir7, poligon2, logic, coduri, snipers, sablon1, submdisj, v, jetoane, prodmax, printesa, palindrom, reziston
De acelaşi autor: conflicte, cadere, leaves, na, distanta, ivv, aparitii, tabara1, stop, hanoi, logn, cuburi1, viteza, masina3, anticip, cabane, spp, regine, comoara2, perle, sortari, triti
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, 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
surse trimise | ajutor