Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | soldiers.in, soldiers.out | Sursă | Lot Seniori Dorohoi 2019 - Baraj 1 |
| Autor | Andrei Constantinescu | Adăugată de |  brebenel mihnea stefan •tryharderul |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Soldiers
N soldati se aseaza in linie, de la stanga la dreapta. Fiecare soldat are un numar distinct de la 1 la n asociat. In fiecare dimineata sergenrul responsabil vine si cheama in fata pe soldatii corespunzatori numerelor 1 2 ... K
Daca acestia nu se afla chiar in ordinea 1 2 ... K pe toti cei N soldati ii va astepta o pedeapsa crunta. Sergentul, observand ca cei K soldatu nu sunt asezati corect, va incepe sa ordoneze soldatii. El ii va ordona pe cei K soldati folosind interschimbari adiacenti. La fiecare pas va alege 2 soldati aflati in ordine consecutive (din cei n) si ii va obliga sa isi interschimve pozitiile.
Sergentul este foarte eficient si ii va ordona pe soldatii cu numerele 1 2 ... K folosind un numar minim de interschimbari, insa pentru fiecare astfel de interschimbare ii va obliga pe toti soldatii sa execute o flotare.
Astazi sergentul este prea nervos si ocupat, si drept urmare va roaga pe voi sa ii spuneti cate flotari trebuie sa execute cei N soldati.
Date de intrare
- linia 1: N K, reprezentand numarul de soldati, respectiv numarul de soldati chemati in fata.
- linia 2: S0 S1 ... SN-1 (separate prin cate un spatiu)
Date de ieşire
In fisierul de iesire se va afla numarul cerut.
Punctare
| Subtask | Punctaj | Constrangeri |
|---|---|---|
| 1 | 6 puncte | 1 ≤ N ≤ 15 |
| 2 | 6 puncte | 1 ≤ N ≤ 100 |
| 3 | 5 puncte | 1 ≤ N ≤ 20 000 K ≤ 50 |
| 4 | 6 puncte | 1 ≤ N ≤ 20 000 K ≤ 500 |
| 5 | 37 puncte | 1 ≤ N ≤ 200 000 k ≤ 5000 |
| 6 | 5 puncte | 1 ≤ N ≤ 200 000 K=N |
| 7 | 20 puncte | 1 ≤ N ≤ 200 000 |
Exemplu
| soldiers.in | soldiers.out |
|---|---|
| 6 3 6 1 5 2 4 3 | |
| 6 5 6 1 5 2 4 3 | 4 |
| 7 4 4 5 1 7 2 6 3 | 6 |
Explicaţie
In primul exemplu, sergentul ii cheama pe cei cu numerele 1, 2 si 3. Din fericire acestia se afla deja in ordinea corecta asa ca soldatii nu sunt obligati sa execute flotari.
In al doilea exemplu, din cauza soldatilor cu numerele 4 si 5 ordinea soldatilor nu mai este corecta corecta. Sergentul ii poate aranja in felul urmator folosind 4 interschimbari:
6 1 (5 2) 4 3 -> 6 1 2 5 (4 3) -> 6 1 2 (5 3) 4 -> 6 1 2 3 (5 4) -> 6 1 2 3 4 5
In cel de-al treilea exemplu, una din metodele de a ordona soldatii cu numere 1 2 3 si 4 folosind 6 interschimbari este:
(4,5) 1 7 2 6 3 -> 5 4 1 7 2 (6,3) -> 5 (4,1) 7 2 3 6 -> 5 1 (4,7) 2 3 6 -> 5 1 7 (4,2) -> 5 1 7 2 (4,3) 6 -> 5 1 7 2 3 4 6
