==Include(page="template/taskheader" task_id="pedefe")==
Zaharel se ocupa de securitatea subiectelor de la finala preONI si a scris textul problemelor sub forma unui sir S[0] de numere naturale ordonate crescator. Fiind un pic paranoic, el s-a gandit sa aplice o criptare pe S[0], folosind un algoritm inventat de el, algoritmul de criptare Pedefe(TM). 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 S[1,]S[2,]S[3]. Dupa cateva investigatii si-a dat seama ca S[3] este un subsir al lui S[0], si in plus S[0] se gaseste ca subsir atat in S[1] cat si in S[2].
Zaharel se ocupa de securitatea subiectelor de la finala preONI si a scris textul problemelor sub forma unui sir $S{~0~}$ de numere naturale ordonate crescator. Fiind un pic paranoic, el s-a gandit sa aplice o criptare pe $S{~0~}$, folosind un algoritm inventat de el, algoritmul de criptare Pedefe(TM). 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 $S{~1~},S{~2~},S{~3~}$. Dupa cateva investigatii si-a dat seama ca $S{~3~}$ este un subsir al lui $S{~0~}$, si in plus $S{~0~}$ se gaseste ca subsir atat in $S{~1~}$ cat si in $S{~2~}$.
h2. Cerinta
Evident, cele trei siruri nu sunt deajuns pentru a-l gasi in mod unic pe S[0]. Ca sa nu-s iroseasca zilele sa recupereze datele, Zaharel vrea sa stie cate posibiltati exista de a-l gasi pe S[0] folosind informatiile disponibile. Reamintim ca S[0] trebuie sa fie un subsir atat al lui S[1] si S[2], sa-l contina pe S[3] ca subsir, si sa fie crescator.
Evident, cele trei siruri nu sunt deajuns pentru a-l gasi in mod unic pe $S{~0~}$. Ca sa nu-s iroseasca zilele sa recupereze datele, Zaharel vrea sa stie cate posibiltati exista de a-l gasi pe $S{~0~}$ folosind informatiile disponibile. Reamintim ca $S{~0~}$ trebuie sa fie un subsir atat al lui $S{~1~}$ si $S{~2~}$, sa-l contina pe $S{~3~}$ ca subsir, si sa fie crescator.
h2. 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 S[1], S[2], S[3], in aceasta ordine.
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 $S{~1~}, S{~2~}, S{~3~}$ in aceasta ordine.
h2. Date de Iesire
In fisierul pedefe.out se va afisa numarul de posibilitati cautat, modulo 666013.
In fisierul $pedefe.out$ se va afisa numarul de posibilitati cautat, modulo $666013$.
h2. Restrictii si observatii
S 1 <= N, M <= 500
S 0 <= P <= 100, P <= min(N, M)
S Sirurile vor contine numere naturale din intevalul [1, 500]
S Pentru 50% din teste N, M <= 256, iar pentru inca 25% din teste numarul de caractere distincte din sirurile S[1], S[2], S[3] este <= 20
S Considerand un sir A=(a[1],a[2]...a[N]), se numeste subsir al lui A, un sir B=(a[i1],a[i2]...a[iK]) cu proprietatea 1<=i[1]<i[2]<...<i[K]<=N.
S Doua solutii se considera distincte considerand pozitiile numerelor in sirurile S[1] si S[2], nu valoarea acestora (vezi exemplu)
S 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
* $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 $S{~1~}, S{~2~}, S{~3~}$ este $≤ 20$
* Considerand un sir $A=(a{~1~},a{~2~}...a{~N~})$, se numeste subsir al lui $A$, un sir $B=(a{~i1~},a{~i2~}...a{~iK~})$ cu proprietatea $1 ≤ i{~1~}<i{~2~}<...<i{~K~} ≤ N$.
* Doua solutii se considera distincte considerand pozitiile numerelor in sirurile $S{~1~}$ si $S{~2~}$, 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
h2. Exemplu
pedefe.in pedefe.out Explicatii
8 9 2 6 S[0] poate fi:
14 1 2 2 15 24 3 4 1 24 (S[1,2] S[1,6] S[2,3] S[2,7])
17 18 1 2 2 3 24 4 19 1 2 24 (S[1,2] S[1,3] S[1,6] S[2,3] S[2,4] S[2,7])
1 24 1 2 24 (S[1,2] S[1,4] S[1,6] S[2,3] S[2,4] S[2,7])
1 2 24 (S[1,2] S[1,3] S[1,6] S[2,3] S[2,5] S[2,7])
1 2 24 (S[1,2] S[1,4] S[1,6] S[2,3] S[2,5] S[2,7])
1 2 2 24 (S[1,2] S[1,3] S[1,4] S[1,6] S[2,3] S[2,4] S[2,5] S[2,7])
table(example). |_. pedefe.in |_. pedefe.out |_. Explicatii |
| 8 9 2
14 1 2 2 15 24 3 4
17 18 1 2 2 3 24 4 19
1 24 | 6 | S{~0~} poate fi:
1 24 (S{~1,2~} S{~1,6~} S{~2,3~} S{~2,7~})
1 2 24 (S{~1,2~} S{~1,3~} S{~1,6~} S{~2,3~} S{~2,4~} S{~2,7~})
1 2 24 (S{~1,2~} S{~1,4~} S{~1,6~} S{~2,3~} S{~2,4~} S{~2,7~})
1 2 24 (S{~1,2~} S{~1,3~} S{~1,6~} S{~2,3~} S{~2,5~} {~2,7~})
1 2 24 (S{~1,2~} S{~1,3~} S{~1,6~} S{~2,3~} S{~2,5~} S{~2,7~})
1 2 2 24 (S{~1,2~} S{~1,3~} S{~1,4~} S{~1,6~} S{~2,3~} S{~2,4~} S{~2,5~} S{~2,7~}) |
==Include(page="template/taskfooter" task_id="pedefe")==
