Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | clasa0.in, clasa0.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | autor necunoscut | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.2 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
   2.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Clasa0
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ă nivelul lor de colegiabilitate. Gradul de sociabilitate al unui grup este diferența maximă dintre nivelul de colegiabilitate a doi elevi. Dacă în grup este doar un elev gradul de sociabilitate al acelui grup este 0.
Cerință
Doamna învățătoare vrea să știe care este suma maximă a gradelor de sociabilitate a grupurilor. 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 trebuie să se afle valoarea dorită de doamna profesoară.
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 grupuri
Exemplu
| clasa0.in | clasa0.out | Explicație |
|---|---|---|
| 5 0 1 2 1 4 |
3 |
N = 5 a1 = 0 a2 = 1 p = 2 q = 1 r = 4 Secvența A este: 0 1 2 1 0 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 3, a doua grupă elevii de pe pozițiile 2, 4 și 5 |
