== include(page="template/taskheader" task_id="ab") ==
Fie două secvențe de numere intregi A = a[~1~]a[~2~]...a[~k~] si B = b[~1~]b[~2~]...b[~n~]. Spunem că secvența A "încape" în secvența B la poziția i dacă a1 <= bi, a2 <= bi+1, ... ak <= bi+k-1, unde i <= n-k+1.
Fie două secvențe de numere intregi A = a[~1~]a[~2~]...a[~k~] și B = b[~1~]b[~2~]...b[~n~]. Spunem că secvența A "încape" în secvența B la poziția i dacă a[~1~] ≤ b[~i~], a[~2~] ≤ b[~i+1~], ... a[~k~] ≤ b[~i+k-1~], unde i ≤ n-k+1.
Secvența A are proprietatea că ai = (p*ai-1 + q*ai-2) % r, pentru i >= 3.
Secvența A are proprietatea că a[~i~] = (p*a[~i-1~] + q*a[~i-2~]) % r, pentru i ≥ 3.
Secvența B are proprietatea că bi = bi-1 + (s*bi-1 + t*bi-2) % u pentru i >= 3.
Secvența B are proprietatea că b[~i~] = b[~i-1~] + (s*b[~i-1~] + t*b[~i-2~]) % u pentru i ≥ 3.
Cerință
h2. Cerință
Date două secvențe A și B specificate prin numerele care le definesc unic, k, a1, a2, p, q, r, n, b1, b2, s, t, u [și știind că secvența B este nedescrescătoare (bi <= bi+1 pentru orice i)] să se găsească cea mai mică poziție i unde secvența A încape în secvența B.
Date două secvențe A și B specificate prin numerele care le definesc unic, k, a[~1~], a[~2~], p, q, r, n, b[~1~], b[~2~], s, t, u să se găsească cea mai mică poziție i unde secvența A încape în secvența B.
h2. Date de intrare
Fișierul de intrare $ab.in$ ...
Pe prima linie a fisierului de intrare $ab.in$ se va găsi k, număr zecimal, lungimea secvenței A. Pe cea de-a doua linie se vor găsi numerele a[~1~], a[~2~], p, q și r, numere ce determină unic secvența A. Pe a treia linie se va găsi n, număr zecimal, lungimea secvenței B. Pe a patra linie se vor găsi numerele b[~1~], b[~2~], s, t și u, numere ce determină unic secvența B.
h2. Date de ieșire
În fișierul de ieșire $ab.out$ ...
Fișierul de ieșire $ab.out$ va conține un singur număr, și anume poziția i unde secvența A încape în secvența B. Dacă nu există nici o astfel de poziție veți afișa valoarea 0.
h2. Restricții
* $... ≤ ... ≤ ...$
* $2 ≤ k ≤ n ≤ 4000000$
* $0 ≤ a[~1~], a[~2~], r, s, t ≤ 2 miliarde$
* $-1 miliard ≤ p, q ≤ 1 miliard$
* $0 ≤ b[~1~] ≤ b[~2~] ≤ 1000$
* $0 ≤ u ≤ 500$
* se garantează că toate elementele secvenței A sînt non-negative
* pozițiile în secvențele A și B se numerotează începînd cu unu (nu cu zero)
h2. Exemplu
h2. Exemple
table(example).
|_. ab.in |_. ab.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|_. ab.in |_. ab.out |_. Explicație |
| 6
500 1000 1 1 1500
12
0 300 15 1 450
| 5
| Secvențele codificate sînt:
500 1000 0 1000 1000 500
0 300 300 600 900 1050 1050 1200 1350 1650 1650 1950
Prima poziție pe care încape A în B este 5
|
| 5
1000 2500 2 3 3500
12
200 500 1 2 500
| 0
| Secvențele codificate sînt:
1000 2500 1000 2500 1000
200 500 900 1300 1400 1400 1600 2000 2200 2400 2700 2700
A nu încape în B la nici o poziție
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="ab") ==
