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

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


Timp maxim de execuţie / test:
1.2s
Memorie totala disponibilă / stivă:
64MB / 8MB

Green şi Riemann sunt doi prieteni buni cărora le place să joace un joc numit “enigma”. În acest joc, unul dintre ei scrie un cuvânt format din N caractere, iar celalalt vine cu M cuvinte de maxim S caractere. Scopul celui de-al doilea jucător este să îşi dea seama în câte moduri poate primul cuvânt să fie format din concatenarea prefixelor unor cuvinte dintre cele M.
Dacă s-a găsit un mod de a forma primul cuvânt, atunci fiecare poziţie i a acestuia va avea asociată o pereche (x, y), semnificând faptul că poziţia i este acoperită de al y-lea caracter din cuvântul x. Astfel, două moduri de a forma primul cuvânt sunt considerate diferite dacă există două poziţii i şi j, cu perechile asociate (x1, y1) şi (x2, y2) astfel încât x1 != x2 sau y1 != y2.

Cerinţă

Realizaţi un program care să rezolve jocul “enigma”!

Date de intrare

Fişierul de intrare enigma.in va conţine pe prima linie două numere N şi M cu semnificaţia din enunţ. A doua linie va conţine primul cuvânt format din N caractere. Urmează M linii, fiecare conţinând un cuvânt de maxim S caractere.

Date de ieşire

Fişierul de ieşire enigma.out va conţine pe prima linie numărul de moduri în care primul cuvânt poate fi obţinut din concatenarea prefixelor unor cuvinte dintre cele M, modulo 31 333.

Restricţii

1 ≤ N ≤ 300 000
1 ≤ M ≤ 4 500
1 ≤ S ≤ 100
• un caracter este definit ca fiind o literă mică din alfabetul englez
• un cuvânt poate apărea de mai multe ori
• prefixele cuvintelor pot fi doar concatenate, nu şi suprapuse

Exemple

enigma.inenigma.outExplicaţii
7 3 xxxabdc xxx abdc c 8 Considerând numerotarea cuvintelor cea din fişierul de intare, perechile asociate poziţiilor primului cuvânt sunt:
1. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4);
2. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4);
3. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (2, 4);
4. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (2, 4);
5. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1);
6. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1);
7. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (3, 1);
8. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1)


autor: Andrei Parvu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la LOT SB 2011: cifre4, grad2, risipa, liste, pixy, domino2, neconex, testament, asfalt1, intervale, lant1, lcdr, jocs, jb
De acelaşi autor: radare, hacker, terenuri3d, jocs, 3max, confuzie
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, 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 trie: agendatelefonica
surse trimise | ajutor