Fișierul intrare/ieșire clasa0.in, clasa0.out Sursă ad-hoc
Autor autor necunoscut Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.6 sec Limită de memorie 65536 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 emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Clasa0

Astăzi este prima zi de școală pentru foarte mulți preșcolari. Doamna învățătoare Cristina decide să formeze grupe de elevi după nivelul lor de colegialitate. Gradul de socializare al unei grupe este diferența maximă dintre nivelul de colegialitate a doi elevi. Dacă în grupă este doar un elev gradul de socializare al acelei grupe este 0.

Cerință

Doamna învățătoare vrea să știe care este suma maximă a gradelor de socializare ale grupelor. Voi trebuie să o ajutați!

Nivelurile de colegialitate se dau ca o secvență de numere A = a1, a2, ..., an astfel încît:

  • ai = (p * ai-1 + q * ai-2) % 232, pentru orice i ≥ 3.

Date de intrare

Pe prima linie a fisierului de intrare clasa0.in se va găsi N, numărul elevilor (lungimea secvenței A). Pe cea de-a doua linie se vor găsi numerele a1, a2, p și q, numere ce determină unic secvența A (nivelurile de colegialitate).

Date de ieșire

În fișierul de ieșire clasa0.out se va afla valoarea dorită de doamna învățătoare.

Restricții

  • 2 ≤ N ≤ 10 milioane
  • 0 ≤ a1, a2 ≤ 2 miliarde
  • -1 miliard ≤ p, q ≤ 1 miliard
  • se garantează că toate elementele secvenței A sînt non-negative
  • Putem forma oricîte grupe

Exemplu

clasa0.in clasa0.out Explicație
5
11 33 -1 6
154
N = 5
a1 = 11
a2 = 33
p = -1
q = 6
Secvența A este: 11 33 33=-33+6*11 165=-33+6*33 33=-165+6*33
Putem grupa elevii astfel:
Prima grupă elevii de pe pozițiile 1, 3 și 4, a doua grupă elevii de pe pozițiile 2 și 5.
O altă variantă de socializare maximă este:
Prima grupă elevii de pe pozițiile 1 și 4, a doua grupă elevii de pe pozițiile 2, 3 și 5

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

Indicii de rezolvare

Arată 5 categorii