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
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 |
|---|---|
| 4 1 5 2 2 | 42 |
Explicatii
o 5 2 2 merge in camera 1 si pune paharul de acolo pe tava (10s)
o 5 2 2 merge din camera 1 in camera 2 cu un pahar pe tava (1s)
o o 2 2 pune pe tava paharul din camera 2 (10s)
o 1 2 2 asaza pe masa din camera 2 paharul cu bautura de valoare 1 (10s)
o 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)
