Fișierul intrare/ieșire | lanterna.in, lanterna.out | Sursă | Pregătire clasele 9-10 |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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). |