Fişierul intrare/ieşire:	ab.in, ab.out	Sursă	Baraj Shumen juniori 2014
Autor	Cristian Francu	Adăugată de	Cristian Francu •francu
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	4/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

AB (clasa a 8-a)

Fie două secvenţe de numere intregi A = a₁a₂...a_k şi B = b₁b₂...b_n. Spunem că secvenţa A "încape" în secvenţa B la poziţia i dacă a₁ ≤ b_i, a₂ ≤ b_i+1, ... a_k ≤ b_i+k-1, unde i ≤ n-k+1.

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ă b_i = b_i-1 + (s*b_i-1 + t*b_i-2) % u pentru i ≥ 3.

Cerinţă

Date două secvenţe A şi B specificate prin numerele care le definesc unic, k, a₁, a₂, p, q, r, n, b₁, b₂, s, t, u să se găsească cea mai mică poziţie i unde secvenţa A încape în secvenţa B.

Date de intrare

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₁, a₂, 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₁, b₂, s, t şi u, numere ce determină unic secvenţa B.

Date de ieşire

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.

Restricţii

• 2 ≤ k ≤ n ≤ 4000000
• 0 ≤ a₁, a₂, r, s, t ≤ 2 miliarde
• -1 miliard ≤ p, q ≤ 1 miliard
• 0 ≤ b₁ ≤ b₂ ≤ 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)

Exemple