Fişierul intrare/ieşire:propozitie2.in, propozitie2.outSursăAlgoritmiada 2009, Runda Finala
AutorStefan Alexandru FilipAdăugată deProstuStefan-Alexandru Filip Prostu
Timp execuţie pe test0.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Propozitie2

Dubota a primit ca tema de la profesoara de informatica sa imparta un text in propozitii si apoi in cuvinte. Insa cum el nu era atent si-a notat altceva ca tema. El primeste un sir S si un dictionar format din C cuvinte. Cuvintele se identifica insa numai prin caracterele din care sunt formate, asadar orice permutare a caracterelor unui cuvant reprezinta acelasi cuvant. De exemplu, daca avem un cuvant identificat prin caractere adt atunci si succesiunile de caractere urmatoare: dat sau tda sau tad reprezinta acelasi cuvant.
Acum Dubota trebuie sa imparta sirul initial in cuvinte care sa formeze o propozitie. O propozitie este o succesiune de cuvinte astfel incat fiecare caracter al sirului initial apartine unui cuvant si numai unul, iar orice cuvant face parte din dictionar. Intr-o propozitie un cuvant din dictionar poate sa apara de mai multe ori.

Cerinta

Sa se determine cate posibilitati are Dubota pentru a imparti sirul S in propozitii. Deoarece acest rezultat poate fi foarte mare, este de ajuns sa determinati rezultatul modulo 666019.

Date de intrare

În fişierul de ieşire propozitie2.in pe prima linie se afla un sir de caractere, S, iar pe a doua linie se afla un numar, C. Pe urmatoarele C linii se afla cate un sir de caractere reprezentant un cuvant al dictionarului.

Date de ieşire

În fişierul de ieşire propozitie2.out se va afisa un singur numar, reprezentant rezultatul cerut.

Restricţii

  • C ≤ 5000
  • lungimea sirului S ≤ 5000
  • lungimea unui cuvant din dictionar ≤ 100
  • Cuvintele sunt formate din litere mici ale alfabetului limbii engleze. ('a' - 'z')
  • Atentie: In dictionar pot exista cuvinte omografe. (cuvinte diferite dar care au aceiasi scriere)

Exemplu

propozitie2.inpropozitie2.out
acbad
5
bac
ad
a
bc
d
5

Explicaţie

Cele 5 posiblitati de a imparti sirul initial in cuvinte, identificate prin indicile cuvantelor din dictionar:

  • 1, 2
  • 1, 3, 5
  • 3, 1, 5
  • 3, 4, 2
  • 3, 4, 3, 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content