==Include(page="template/taskheader" task_id="pedefe")==
== include(page="template/taskheader" task_id="pedefe") ==
Poveste ...
h2. Cerinta
...
h2. Restrictii
...
h2. Date de intrare
...
h2. Date de iesire
...
h2. Exemplu
| pedefe.in | pedefe.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="pedefe") ==
==Include(page="template/raw")==
Pedefe
(putea fi Subsir 3)
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.
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.
h2. Date de Iesire
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
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])
==Include(page="template/taskfooter" task_id="pedefe")==
