Fișierul intrare/ieșire | sumak.in, sumak.out | Sursă | Olimpiada pe scoala 2016 clasa a 8-a |
---|---|---|---|
Autor | Teodor Plop | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 1.8 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Suma K (clasa a 8-a)
Fie șirul X de numere întregi definit astfel:
- X1 este un număr întreg dat
- Xi = [A · (Xi-1 + C) + B] mod D – C, pentru orice i > 1
Se consideră primele N elemente ale șirului X. Să se elimine dintre acestea maxim K numere, astfel încît suma celor rămase să fie maximă.
Date de intrare
Fișierul de intrare sumak.in conține pe prima linie numerele N și K. Pe a doua linie conține numerele X1, A, B, C și D.
Date de ieșire
În fișierul de ieșire sumak.out se va scrie un singur număr și anume suma maximă rezultată în urma eliminării a cel mult K numere.
Restricții
- 0 < K ≤ N ≤ 10 milioane
- -1 miliard ≤ X1 ≤ 1 miliard
- 0 < A ≤ 2 miliarde
- 0 < B ≤ 2 miliarde
- 0 ≤ C ≤ 1 miliard
- 0 < D ≤ 1 miliard
- Pentru 50% din teste N ≤ 5 milioane
- Pentru 20% din teste N ≤ 35000
Exemplu
sumak.in | sumak.out | Explicație |
---|---|---|
10 3 5 7 5 5 11 |
14 |
X1 = 5 X2 = [7 · (5 + 5) + 5] mod 11 – 5 = 4 X3 = [7 · (4 + 5) + 5] mod 11 – 5 = -3 X4 = [7 · (-3 + 5) + 5] mod 11 – 5 = 3 X5 = [7 · (3 + 5) + 5] mod 11 – 5 = 1 X6 = [7 · (1 + 5) + 5] mod 11 – 5 = -2 X7 = [7 · (-2 + 5) + 5] mod 11 – 5 = -1 X8 = [7 · (-1 + 5) + 5] mod 11 – 5 = -5 X9 = [7 · (-5 + 5) + 5] mod 11 – 5 = 0 X10 = [7 · (0 + 5) + 5] mod 11 – 5 = 2 Suma acestor numere este 4. Deoarece putem elimina cel mult 3 numere vom elimina -5, -3 și -2, obținînd suma maximală 14. |