==Include(page="template/taskheader" task_id="barman")==

==Include(page="template/taskheader" task_id="barman")==
 
Paftenie a decis sa se faca barman. Inainte de asta trebuie sa dovedeasca abilitate in manevrarea bauturilor. Barul lui Paftenie este alcatuit din $N$ camere aliniate in cerc. In fiecare camera se afla un pahar cu bautura, fiecare bautura avand o anumita valoare (cuprinsa intre $1$ si $2.000.000.000$). El trebuie sa mute bauturile dintr-o camera in alta astfel incat la sfarsit, bauturile sa fie sortate dupa camere. Daca la sfarsit in camera $i$ se afla o bautura cu valoarea $a{~i~}$, sirul valorilor $a{~1~},a{~2~}...a{~N~}$ se considera sortat daca exista $1 ≤ i ≤ N$ astfel incat $a{~i~} ≤ a{~i+1~} ≤ ... ≤ a{~N~} ≤ a{~1~} ≤ ... ≤ a{~i-1~}$ (sirul este circular). In orice moment, Paftenie poate tine pe tava cel mult doua pahare. Pentru deplasarea bauturilor, poate efectua urmatoarele mutari:
 
* poate lua un pahar din camera in care se afla si sa il aseze pe tava (il costa $10$ secunde)
* poate lasa un pahar intr-o camera in care nu se afla nici o bautura (il costa $10$ secunde)
* se poate deplasa din camera $i$ in camera $j$ avand pe tava $c$ pahare ({$0 ≤ c ≤ 2$}) (il costa $c*|i-j|$ secunde)
 
h2. Cerinta
 
Ajutati-l pe Paftenie sa sorteze paharele intr-un timp minim!
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare $barman.in$ este dat numarul $N$ al bauturilor. Pe urmatoarea linie se afla $N$ intregi reprezentand valorile bauturilor - al $i$-lea numar reprezinta valoarea bauturii aflate initial in camera $i$ ({$a{~i~}$}).
 
h2. Date de Iesire
 
Fisierul $barman.out$ va contine pe prima linie un singur numar reprezentand timpul minim de sortare a bauturilor.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 600$
* In orice moment, in afara de paharele care le are Paftenie pe tava, intr-o camera poate exista maxim un pahar
 
h2. Exemplu
 
table(example). |_. barman.in |_. barman.out |
| 4
1 5 2 2
| 42 |
 
h3. Explicatii
 
$o 5 2 2$ merge in camera $1$ si pune paharul de acolo pe tava ({$10$}s)
$o 5 2 2$ merge din camera $1$ in camera $2$ cu un pahar pe tava ({$1$}s)
$o o 2 2$ pune pe tava paharul din camera $2$ ({$10$}s)
$o 1 2 2$ asaza pe masa din camera $2$ paharul cu bautura de valoare $1$ ({$10$}s)
$o 1 2 2$ se intoarce in camera $1$ cu un pahar pe tava ({$1$}s)
$5 1 2 2$ asaza pe masa din camera $1$ paharul cu bautura de valoare $5$ ({$10$}s)
→ $42$ de secunde
sirul este sortat deoarece {$1 ≤ 2 ≤ 2 ≤ 5 (a2 ≤ a3 ≤ a4 ≤ a1)$}
 
==Include(page="template/taskfooter" task_id="barman")==
 
 

==Include(page="template/raw")==
 
barman
 
 
 
Paftenie a decis sa se faca barman. Inainte de asta trebuie sa dovedeasca abilitate in manevrarea bauturilor. Barul lui Paftenie este alcatuit din N camere aliniate in cerc. In fiecare camera se afla un pahar cu bautura, fiecare bautura avand o anumita valoare (cuprinsa intre 1 si 2.000.000.000). El trebuie sa mute bauturile dintr-o camera in alta astfel incat la sfarsit, bauturile sa fie sortate dupa camere. Daca la sfarsit in camera i se afla o bautura cu valoarea a[i], sirul valorilor a[1],a[2]...a[N] se considera sortat daca exista 1 <= i <= N astfel incat a[i] <= a[i+1] <= ... <= a[N] <= a[1] <= ... <= a[i-1] (sirul este circular). In orice moment, Paftenie poate tine pe tava cel mult doua pahare. Pentru deplasarea bauturilor, poate efectua urmatoarele mutari:
 
S poate lua un pahar din camera in care se afla si sa il aseze pe tava (il costa 10 secunde)
 
S poate lasa un pahar intr-o camera in care nu se afla nici o bautura (il costa 10 secunde)
 
S se poate deplasa din camera i in camera j avand pe tava c pahare (0 <= c <= 2) (il costa c*|i-j| secunde)
 
h2. Cerinta
 
Ajutati-l pe Paftenie sa sorteze paharele intr-un timp minim !
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare barman.in este dat numarul N al bauturilor. Pe urmatoarea linie se afla N intregi reprezentand valorile bauturilor - al i-ulea numar reprezinta valoarea bauturii aflate initial in camera i (a[i]).
 
h2. Date de Iesire
 
Fisierul barman.out va contine pe prima linie un singur numar reprezentand timpul minim de sortare a bauturilor.
 
h2. Restrictii si precizari
 
S 1 <= N <= 600
 
S In orice moment, in afara de paharele care le are paftenie pe tava, intr-o camera poate exista maxim un pahar
 
h2. Exemplu
 
 
|barman.in |barman.out |Explicatii |
 
|4 |42 |* 5 2 2 |
| | |merge in camera 1 si pune paharul de acolo pe tava (10s) |
|1 5 2 2 | |* 5 2 2 |
| | |merge din camera 1 in camera 2 cu un pahar pe tava (1s) |
| | |* * 2 2 |
| | |pune pe tava paharul din camera 2 (10s) |
| | |* 1 2 2 |
| | |asaza pe masa din camera 2 paharul cu bautura de valoare 1 (10s) |
| | |* 1 2 2 |
| | |se intoarce in camera 1 cu un pahar pe tava (1s) |
| | |5 1 2 2 |
| | |asaza pe masa din camera 1 paharul cu bautura de valoare 5(10s) |
| | |-> 42 de secunde |
| | |sirul este sortat deoarece 1 <= 2 <= 2 <= 5 (a[2] <= a[3] <= a[4] <= |
| | |a[1]) |
 
 
 
==Include(page="template/taskfooter" task_id="barman")==

303