Fișierul intrare/ieșire ab.in, ab.out Sursă Baraj Shumen juniori 2014
Autor Cristian Frâncu Adăugată de avatar francu Cristian Francu francu
Timp de execuție pe test 0.6 sec Limită de memorie 131072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii