| Fişierul intrare/ieşire: | lss.in, lss.out | Sursă | Algoritmiada 2017, Runda 1 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | lss.out |
|---|---|
| 3 4 3 4 5 6 | 6 |
