Fișierul intrare/ieșire sumak.in, sumak.out Sursă Olimpiada pe scoala 2016 clasa a 8-a
Autor Teodor Plop Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1.8 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 emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

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

Indicii de rezolvare

Arată 4 categorii