Fişierul intrare/ieşire:sumak.in, sumak.outSursăOlimpiada pe scoala 2016 clasa a 8-a
AutorTeodor PlopAdăugată defrancuCristian Francu francu
Timp execuţie pe test1.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.insumak.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici