Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | barman.in, barman.out | Sursă | preONI 2005 Runda 3 |
Autor | Adrian Vladu | Adăugată de | |
Timp execuţie pe test | 0.475 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Barman
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
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 ai, sirul valorilor a1,a2...aN se considera sortat daca exista 1 ≤ i ≤ N astfel incat ai ≤ ai+1 ≤ ... ≤ aN ≤ a1 ≤ ... ≤ ai-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)
Cerinta
Ajutati-l pe Paftenie sa sorteze paharele intr-un timp minim!
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 (ai).
Date de Iesire
Fisierul barman.out va contine pe prima linie un singur numar reprezentand timpul minim de sortare a bauturilor.
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
Exemplu
barman.in | barman.out | explicatii |
---|---|---|
4 1 5 2 2 | 42 |
|