Fişierul intrare/ieşire:munte4.in, munte4.outSursăLot 2005 Sibiu
AutorStefan GheorgheAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.55 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inmunte4.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content