Fişierul intrare/ieşire:barman.in, barman.outSursăpreONI 2005 Runda 3
AutorAdrian VladuAdăugată de
Timp execuţie pe test0.95 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inbarman.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content