Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | munte4.in, munte4.out | Sursă | Lot 2005 Sibiu |
| Autor | Stefan Gheorghe | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.275 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Munte4
Mari iubitori de munte, Mars si Stefan hotarasc sa mearga intr-o excursie intr-un lant muntos, format din N munti. Acesti munti sunt situati unul dupa altul si sunt dispusi circular (al i-lea munte are ca vecini muntii i-1 si i+1, si al N-lea munte este lipit de primul si de al N-1-lea). Sensul de deplasare este de la muntele 1 spre muntele 2.
Avand deja o mare experienta in domeniu, ei apreciaza foarte exact timpul necesar (exprimat in ore) pentru escaladarea fiecarui munte.
Totusi, cu fiecare munte escaladat, ei obosesc si timpul de escaladare initial estimat va creste. Astfel, dupa escaladarea muntelui de start, timpul de escaladare a muntelui urmator va creste cu o ora. Dupa escaladarea muntelui de start si a urmatorului, timpul de escaladare a celui de al treilea munte va creste cu doua ore. Astfel, dupa escaladarea a i munti, timpul necesar pentru escaladarea urmatorului munte va fi cu i ore mai mare decat timpul estimat initial.
Excursia poate porni de la poalele oricarui munte astfel ca ei isi pun problema de unde sa inceapa excursia astfel incat la final, timpul maxim in care au escaladat un munte sa fie minim.
Date de intrare
Fisierul de intrare munte4.in contine pe prima linie un numar natural N reprezentand numarul de munti. A doua linie va contine un sir de N numere naturale, separate prin cate un spatiu. Al i-lea numar de pe linie reprezinta numarul de ore necesare pentru escaladarea muntelui i din lant, neluand in calcul si oboseala.
Date de iesire
Fisierul de iesire munte4.out va contine pe prima linie doua numere naturale separate printr-un spatiu: muntele de unde cei doi incep excursia si timpul maxim pentru a urca un munte in cadrul excursiei, timp minim avand in vedere celelalte variante de start.
Restrictii
- 1 ≤ n ≤ 1 000 000
Exemplu
| munte4.in | munte4.out |
|---|---|
| 4 5 9 10 3 | 2 11 |
Explicatie
Pornim excursia de la muntele 2. Timpii de escaladare sunt: 9, 10 + 1, 3 + 2, 5 + 3 cu maximul 11. Orice alta alegere a muntelui de start conduce la timpi maximi mai mari.
