| Fişierul intrare/ieşire: | permsort.in, permsort.out | Sursă | Lot Botosani 2012 - Baraj 2 Seniori |
| Autor | Vlad Ionescu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Permsort
Grădinarul Marian are la dispoziţie o permutare cu n elemente şi un număr natural S care iniţial are valoarea 0. Marian execută n operaţii de forma:
- alege elementul minim din permutare, fie x poziţia sa în cadrul permutării
- elimină acest element din permutare, iar toate elementele de la stânga sa le mută la sfârşitul permutării (păstrând ordinea elementelor din stânga)
adună la S pe x.
Astfel, după ce permutarea devine vidă, S va avea o anumită valoare.
Cerinta
Determinaţi valoarea lui S după ce grădinarul Marian termină de executat toate cele n operaţii.
Date de intrare
Fişierul de intrare permsort.in va conţine pe prima linie un număr natural n, reprezentând numărul de elemente ale permutării, iar pe a doua linie n numere naturale distincte cuprinse între 1 şi n, separate prin câte un spaţiu, reprezentând permutarea asupra căreia Marian aplică operaţiile.
Date de ieşire
Fişierul de ieşire permsort.out va conţine pe prima linie un număr natural reprezentând valoarea lui S după execuţia celor n operaţii.
Restricţii
- 1 ≤ n ≤ 1.000.000
- pentru 30% din teste, 1 ≤ n ≤ 5.000
Exemplu
| permsort.in | permsort.out |
|---|---|
| 5 5 4 1 3 2 | 11 |
| permsort.in | permsort.out |
| 7 7 5 6 3 1 2 4 | 16 |
Explicaţie
In primul exemplu:
1) Elementul minim din permutare este 1 şi se află pe poziţia 3. După acest pas, S devine 0+3=3, iar permutarea rămâne (elementele din stânga lui 1 se mută în aceeaşi ordine la sfârşit): (3 2 5 4).
2) Elementul minim din permutare este 2 şi se află pe poziţia 2. După acest pas, S devine 3+2=5, iar permutarea rămâne: (5 4 3).
3) Elementul minim din permutare este 3 şi se află pe poziţia 3. După acest pas, S devine 5+3=8, iar permutarea rămâne: (5 4).
4) Elementul minim din permutare este 4 şi se află pe poziţia 2. După acest pas, S devine 8+2=10, iar permutarea rămâne: (5).
5) Elementul minim din permutare este 5 şi se află pe poziţia 1. După acest pas, S devine 10+1=11, iar permutarea devine vidă.
Valoarea finală a lui S este 11.
In al doilea exemplu:
S = 5 + 1 + 5 + 1 + 2 + 1 + 1
