Fişierul intrare/ieşire:afacere.in, afacere.outSursăLot Cluj 2009, Baraj 4
AutorCatalin-Stefan TiseanuAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.75 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Afacere

Lunasorab s-a decis să îşi deschidă o afacere. Astfel, el s-a apucat de spart coduri (contra cost, bineînţeles). El primeşte o listă de N cuvinte candidat, de aceeaşi lungime L şi trebuie să afle câte cuvinte complete distincte compatibile cu cel puţin unul dintre ele există. Un cuvânt se numeşte candidat dacă conţine numai litere mici din alfabetul latin şi caracterul ? (care poate fi înlocuit cu orice literă mică a alfabetului latin). Spunem că un cuvânt este complet dacă este format doar din litere mici ale alfabetului latin, şi spunem că un cuvânt complet este compatibil cu un cuvânt candidat dacă există o asignare a caracterelor ? astfel încât cele două cuvinte să devină identice.

Totuşi, deoarece este vorba de mulţi bani şi crede că poate fi singura lui şansă de „a face succes”, el vă testează dându-vă NR extinderi ale alfabetului. O extindere a alfabetului constă din reuniunea literelor mici ale alfabetului latin cu un set de caractere adiţionale distincte (doar cardinalul extinderilor este important). Aceste caractere din extindere pot reprezenta asignări posibile ale caracterelor ?.

Deoarece răspunsul pe care Lunasorab îl caută poate fi destul de mare, el vă cere rezultatul modulo 1 000 000 007.

Cerinţă

Dată fiind o listă de cuvinte candidat şi NR extinderi, să se determine câte cuvinte complete distincte compatibile cu cel puţin unul dintre cuvintele candidat există, pentru fiecare extindere.

Date de intrare

Fişierul de intrare afacere.in conţine pe prima linie numerele naturale N L NR. Pe următoarele N linii se vor afla cuvintele candidat. Pe următoarele NR linii fiecare linie va conţine un număr natural v, reprezentând cardinalul unei extinderi.

Date de ieşire

Fişierul de ieşire afacere.out va conţine pentru fiecare dintre cele NR extinderi câte o linie pe care se va scrie un număr natural reprezentând numărul de cuvinte complete distincte compatibile cu cel puţin unul dintre cuvintele candidat din listă, folosind alfabetul format din literele alfabetului latin împreună cu un număr adiţional de caractere egal cu cardinalul extinderii.

Restricţii

  • 1 ≤ N ≤ 20
  • 1 ≤ L ≤ 100
  • 1 ≤ NR ≤ 100
  • Pentru 10% din teste, N ≤ 5 şi L ≤ 5.
  • Pentru încă 30% din teste N ≤ 15 şi L ≤ 50.
  • Cardinalul unei extinderi va fi mai mic sau egal cu 1000.
  • Cuvintele candidat din fişierul de intrare vor conţine doar caractere mici ale alfabetului latin şi ?.

Exemplu

afacere.inafacere.out
3 2 2
ab
a?
cb
0
2
27
29

Explicaţie

Pentru prima extindere nu avem niciun caracter adiţional, deci cuvintele complete compatibile posibile sunt aa, ab, ac, …, az şi cb. Pentru al doilea exemplu, avem două caractere adiţionale în care poate fi transformat ?, deci cuvintele complete compatibile posibile sunt aa, ab, ac, …, az, aA, aB şi cb, unde prin A şi B am notat cele două caractere adiţionale.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content