pedefe

Pedefe

== include(page="template/taskheader" task_id="pedefe") ==

==Include(page="template/taskheader" task_id="pedefe")==

Poveste ...

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. Restrictii

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 intrare

h2. Date de Iesire

...

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

h2. Date de iesire

h2. 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 $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 &le; i{~1~}<i{~2~}<...<i{~K~} &le; 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 |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. pedefe.in |_. pedefe.out |
| 8 9 2
14 1 2 2 15 24 3 4
17 18 1 2 2 3 24 4 19
1 24 | 6 |
 
h3. Explicatii
 
$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") ==

==Include(page="template/taskfooter" task_id="pedefe")==
 
 

933