Fişierul intrare/ieşire:permsort.in, permsort.outSursăLot Botosani 2012 - Baraj 2 Seniori
AutorVlad IonescuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inpermsort.out
5
5 4 1 3 2
11
permsort.inpermsort.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?