Fişierul intrare/ieşire:enigma.in, enigma.outSursăLot Sibiu 2011
AutorAndrei ParvuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Enigma

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 .

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 cuvant poate fi obţinut din concatenarea prefixelor unor cuvinte dintre cele M, modulo 31333 .

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

Exemplu

enigma.inenigma.out
7 3
xxxabdc
xxx
abdc
c
8

Explicaţie

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);

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content