Fişierul intrare/ieşire:lss.in, lss.outSursăAlgoritmiada 2017, Runda 1
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Long Story Short

Povestea este lunga, dar long story short:

Se da un numar K. Consideram urmatorul vector infinit cu elementele: 1,2,3,.....,K,1,2,3,....,K,1,2,3,..... Task-ul nostru este sa stergem P elemente date. De fiecare data cand stergem un element X aflat la pozitia Poz, trebuie sa platim X unitati valoroase. De asemenea, toate elementele aflate dupa Poz ( Poz + 1, Poz + 2, ...) scad cu 1. In schimb, daca costul lor este deja 1, acestea se transforma in K.

Voi trebuie sa gasiti o ordine in care sa stergeti cele P numere date astfel incat sa consumati cat mai putine unitati valoroase.

Date de intrare

Fişierul de intrare lss.in va contine pe prima linie 2 numere K si P. Pe urmatoarea linie se afla P numere reprezentand pozitiile pe care trebuie sa le stergeti.

Date de ieşire

Fişierul de ieşire lss.out va contine pe prima linie un singur numar natural reprezentand numarul minim de unitati valoroase pe care le puteti consuma.

Restricţii

  • 1 ≤ K ≤ 1.000.000.000
  • 1 ≤ P ≤ 100.000
  • Pozitiile date sunt numere naturale din intervalul [1,1.000.000.000]
  • Atunci cand un element este sters, el nu dispare din vector, ci valoarea lui devine 0 si nu se mai modifca ulterior.

Exemplu

lss.inlss.out
3 4
3 4 5 6
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?