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

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


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

Limba ratină are doar N cuvinte, numerotate de la 1 la N. Două sau mai multe cuvinte se numesc k-asemenea dacă au primele k litere identice.
Gradul de asemănare între t cuvinte este k dacă cele t cuvinte sunt k-asemenea, dar nu sunt (k+1)-asemenea.

Cerinţă

Scrieţi un program care pentru un set de t cuvinte dat, răspunde la interogări de genul: ″Care este gradul de asemănare între cuvintele x1 x2 ... xt″ ?

Date de intrare

Fişierul de intrare ratina.in va conţine pe prima linie două numere naturale N M, separate printr-un spaţiu, reprezentând numărul de cuvinte din limba ratină, respectiv numărul de interogări.
Următoarele N linii vor conţine cuvintele din limba ratină, câte un cuvânt pe o linie. Mai exact, pe linia i+1 este scris cuvântul cu numărul de ordine i. Cuvintele sunt formate din litere mici din alfabetul englez.
Urmează M linii, fiecare linie reprezentând câte o interogare exprimată astfel: primul număr de pe linie este un număr natural t cuprins între 2 şi 10 reprezentând numărul de cuvinte din interogare, apoi vor urma cele t numere de ordine ale cuvintelor din interogare, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire ratina.out va conţine M linii, câte una pentru fiecare interogare din fişierul de intrare. Pe linia i va fi scris gradul de asemănare al cuvintelor din interogarea i.

Restricţii

0 < N < 10 001
0 <
lungimea maximă a unui cuvânt < 2000
0 <
suma lungimilor tuturor cuvintelor < 200 000
1 < M < 100 001

Pentru teste cu N ≤ 200, se acordă 50 de puncte din care 30 de puncte pentru teste şi cu M ≤ 10000.

Exemple

ratina.inratina.outExplicaţii
6 5 asdf asdeffff gata gara pesistem pestesistem 2 1 2 2 3 4 2 5 6 3 1 3 5 2 1 1 3 2 3 0 4 Prima interogare cere gradul de asemănare între cuvintele asdf şi asdeffff, care este 3 (deoarece cele două cuvinte au primele 3 litere identice, dar nu şi primele 4 litere).
Cea de a doua interogare cere gradul de asemănare între cuvintele gata şi gara, care este 2.
Cea de a treia interogare cere gradul de asemănare între cuvintele pesistem şi pestesistem care este 3.
Cea de a patra interogare cere gradul de asemănare între cuvintele asdf, gata şi pesistem care este 0.
Ultima interogare este evidentă: un cuvânt este k-asemenea cu el însuşi unde k este chiar lungimea cuvântului.

autor: Dan Ionut Fechete
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2006: borg, diamant, matrice1, petrom, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, sg1, fact, limbaj, panouri, pereti, sant1, zumzi, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
De acelaşi autor: 2sec, croco, judete, tetris2, trafic, monede1, mesaj1, diamant, import, drept1, gard, pitici1, curent
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, 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 arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
Chestionare recomandate
surse trimise | ajutor