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 |   4/5 |
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. |
|---|
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 a1,a2...a[N] se considera sortat daca exista 1 <= i <= N astfel incat a[i] <= a[i+1] <= ... <= a[N] <= a1 <= ... <= 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)
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-ulea numar reprezinta valoarea bauturii aflate initial in camera i (a[i]).
Date de Iesire
Fisierul barman.out va contine pe prima linie un singur numar reprezentand timpul minim de sortare a bauturilor.
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
Exemplu
| barman.in | barman.out | Explicatii |
| 4 | 42 |
|
| merge in camera 1 si pune paharul de acolo pe tava (10s) | ||
| 1 5 2 2 |
| |
| merge din camera 1 in camera 2 cu un pahar pe tava (1s) | ||
| ||
| pune pe tava paharul din camera 2 (10s) | ||
| ||
| asaza pe masa din camera 2 paharul cu bautura de valoare 1 (10s) | ||
| ||
| 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) | ||
