Fişierul intrare/ieşire:pedefe.in, pedefe.outSursăpreONI 2006 Runda Finala
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Pedefe

Zaharel se ocupa de securitatea subiectelor de la finala preONI si a scris textul problemelor sub forma unui sir S0 de numere naturale ordonate crescator. Fiind un pic paranoic, el s-a gandit sa aplice o criptare pe S0, folosind un algoritm inventat de el, algoritmul de criptare Pedefe™. Din pacate, calculatorul preONI a fost virusat si datele criptate s-au pierdut. Zaharel a putut recupera trei siruri de date din calculator pe care le vom nota S1,S2,S3. Dupa cateva investigatii si-a dat seama ca S3 este un subsir al lui S0, si in plus S0 se gaseste ca subsir atat in S1 cat si in S2.

Cerinta

Evident, cele trei siruri nu sunt deajuns pentru a-l gasi in mod unic pe S0. Ca sa nu-s iroseasca zilele sa recupereze datele, Zaharel vrea sa stie cate posibiltati exista de a-l gasi pe S0 folosind informatiile disponibile. Reamintim ca S0 trebuie sa fie un subsir atat al lui S1 si S2, sa-l contina pe S3 ca subsir, si sa fie crescator.

Date de Intrare

Prima linie a fisierului pedefe.in va contine pe prima linie numerele naturale N, M si P. Urmatoarele trei linii vor contine N, M, respectiv P numere naturale, reprezetand sirurile S1, S2, S3 in aceasta ordine.

Date de Iesire

In fisierul pedefe.out se va afisa numarul de posibilitati cautat, modulo 666013.

Restrictii si observatii

  • 1 ≤ N, M ≤ 500
  • 0 ≤ P ≤ 100, P ≤ min(N, M)
  • Sirurile vor contine numere naturale din intevalul [1, 500]
  • Pentru 50% din teste N, M ≤ 256, iar pentru inca 25% din teste numarul de caractere distincte din sirurile S1, S2, S3 este ≤ 20
  • Considerand un sir A=(a1,a2...aN), se numeste subsir al lui A, un sir B=(ai1,ai2...aiK) cu proprietatea 1 ≤ i1<i2<...<iK ≤ N.
  • Doua solutii se considera distincte considerand pozitiile numerelor in sirurile S1 si S2, nu valoarea acestora (vezi exemplu)
  • Se recomanda evitarea folosirii operatiei modulo din limbajul in care lucrati deoarece este foarte consumatoare de timp; se recomanda folosirea operatiei de scadere in schimb

Exemplu

pedefe.inpedefe.out
8 9 2
14 1 2 2 15 24 3 4
17 18 1 2 2 3 24 4 19
1 24
6

Explicatii

S0 poate fi:
1 24 (S1,2 S1,6 S2,3 S2,7)
1 2 24 (S1,2 S1,3 S1,6 S2,3 S2,4 S2,7)
1 2 24 (S1,2 S1,4 S1,6 S2,3 S2,4 S2,7)
1 2 24 (S1,2 S1,3 S1,6 S2,3 S2,5 2,7)
1 2 24 (S1,2 S1,3 S1,6 S2,3 S2,5 S2,7)
1 2 2 24 (S1,2 S1,3 S1,4 S1,6 S2,3 S2,4 S2,5 S2,7)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content