barman

Barman

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

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

Poveste ...

==Include(page="template/raw")==
 
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. Restrictii

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 intrare

h2. Date de Iesire

...

Fisierul $barman.out$ va contine pe prima linie un singur numar reprezentand timpul minim de sortare a bauturilor.

h2. Date de iesire

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

| barman.in | barman.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. barman.in |_. barman.out | explicatii |
| 4
1 5 2 2
| 42
| * 5 2 2
merge in camera 1 si pune paharul de acolo pe tava (10s)
* 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 (a2 ≤ a3 ≤ a4 ≤ a1) |

== include(page="template/taskfooter" task_id="barman") ==
 

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