Fișierul intrare/ieșire lanterna.in, lanterna.out Sursă Pregătire clasele 9-10
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.2 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in lanterna.out explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii