Fişierul intrare/ieşire:ab.in, ab.outSursăBaraj Shumen juniori 2014
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

AB (clasa a 8-a)

Fie două secvenţe de numere intregi A = a1a2...ak şi B = b1b2...bn. 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.

Secvenţa A are proprietatea că ai = (p*ai-1 + q*ai-2) % r, pentru i ≥ 3.

Secvenţa B are proprietatea că bi = bi-1 + (s*bi-1 + t*bi-2) % u pentru i ≥ 3.

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 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 a1, a2, 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 b1, b2, 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 ≤ a1, a2, r, s, t ≤ 2 miliarde
  • -1 miliard ≤ p, q ≤ 1 miliard
  • 0 ≤ b1 ≤ b2 ≤ 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

ab.inab.outExplicaţ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
Trebuie sa te autentifici pentru a trimite solutii. Click aici