== include(page="template/taskheader" task_id="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.
h2. 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* = *a[~1~]*, *a[~2~]*, ..., *a[~n~]* astfel încît:
* *a[~i~]* = ([*p*] * *a[~i-1~]* + *q* * *a[~i-2~]*) % 2[^32^], pentru orice *i* ≥ 3.
Astăzi este prima zi de școală pentru foarte mulți pre școlari. Doamna învățătoare Cristina decide să își facă grupe de elevi după gradul de colegiabilitate. Socializarea grupului respectiv depinde de diferența dintre gradul de colegiabilitate alor doi elevi(dacă este doar un elev socializare este 0). Doamna învățătoare vrea să știe care este suma socializării grupurilor să fie maximă. Voi trebuie să o ajutați!
h2. 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 *a[~1~]*, *a[~2~]*, *p* și *q*, numere ce determină unic secvența *A* (nivelurile de colegialitate).
Fișierul de intrare $clasa0.in$ pe prima linie *N*, numărul de copii din clasă. Pe a doua linii gradul de sociabilitate al fiecărui copil.
h2. Date de ieșire
În fișierul de ieșire $clasa0.out$ se va afla valoarea dorită de doamna învățătoare.
În fișierul de ieșire $clasa0.out$ trebuie să se afle valoarea dorită de doamna profesoară.
h2. Restricții
* 2 ≤ *N* ≤ 10 milioane
* 0 ≤ *a[~1~]*, *a[~2~]* ≤ 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
* $1 ≤ *N* ≤ 1000000$
* $-1000000000 ≤ *s[~i~]* ≤ 1000000000$
h2. Exemplu
table(example).
|_. clasa0.in |_. clasa0.out |_. Explicație |
table(example).
|_. clasa0.in |_. clasa0.out |_. Explicație
| 5
11 33 -1 6
| 154
| *N* = 5
*a[~1~]* = 11
*a[~2~]* = 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
1 2 3 1 2
| 3
| Prima grupă este formată din elevii de pe pozițiile 1, 3 și 5, iar a doua grupă din elevii de pe pozițiile 2 și 4.
|
== include(page="template/taskfooter" task_id="clasa0") ==
