Fişierul intrare/ieşire:lanterna.in, lanterna.outSursăPregătire clasele 9-10
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Lanterna

Într-o noapte întunecoasă, un grup de N călători ajunge la un pod. Podul este şubred şi poate ţine doar doi oameni simultan. Grupul are o singură lanternă, care este necesară la fiecare traversare. Fiecare călător i are nevoie de ti minute pentru a traversa podul. Când doi oameni traversează podul împreună, ei merg cu viteza celui mai lent dintre ei. De câte minute are nevoie tot grupul pentru a traversa podul?

Date de intrare

Fişierul de intrare lanterna.in conţine pe prima linie numărul de călători N, iar pe a doua linie timpii t1, t2, ..., tN, despărţiţi prin spaţii.

Date de ieşire

În fişierul de ieşire lanterna.out se va scrie un singur număr, reprezentând timpul minim în care grupul poate traversa podul.

Restricţii

  • 3 ≤ N ≤ 100.000
  • 1 ≤ ti ≤ 1.000.000

Exemple

lanterna.inlanterna.outexplicaţie
4
8 1 5 2
15
Persoanele 2 şi 4 trec podul (timp 2).
Persoana 2 se întoarce (timp 1).
Persoanele 1 şi 3 trec podul (timp 8).
Persoana 4 se întoarce (timp 2).
Persoanele 2 şi 4 trec podul (timp 2).
4
8 1 5 4
19
Persoanele 1 şi 2 trec podul (timp 8).
Persoana 2 se întoarce (timp 1).
Persoanele 2 şi 3 trec podul (timp 5).
Persoana 2 se întoarce (timp 1).
Persoanele 2 şi 4 trec podul (timp 4).
6
1 20 30 40 50 60
193
Persoanele 1 şi 2 trec podul (timp 20).
Persoana 1 se întoarce (timp 1).
Persoanele 5 şi 6 trec podul (timp 60).
Persoana 2 se întoarce (timp 20).
Persoanele 1 şi 4 trec podul (timp 40).
Persoana 1 se întoarce (timp 1).
Persoanele 1 şi 3 trec podul (timp 30).
Persoana 1 se întoarce (timp 1).
Persoanele 1 şi 2 trec podul (timp 20).
Trebuie sa te autentifici pentru a trimite solutii. Click aici