Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-05-09 17:48:25.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| 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
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici
