.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » munte2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
munte2


Timp maxim de execuţie / test:
1s
Memorie totala disponibilă / stivă:
32MB / 1MB

Mari iubitori de munte, Mars şi Ştefan hotărăsc să meargă într-o excursie într-un lanţ muntos, format din N munţi. Aceşti munţi sunt situaţi unul după altul şi sunt dispuşi circular (al i-lea munte are ca vecini munţii i–1 şi i+1, şi al N-lea munte este lipit de primul şi de al N–1 lea). Sensul de deplasare este de la muntele 1 spre muntele 2.
Având deja o mare experienţă în domeniu, ei apreciază foarte exact timpul necesar (exprimat în ore) pentru escaladarea fiecărui munte.
Totuşi, cu fiecare munte escaladat, ei obosesc şi timpul de escaladare iniţial estimat va creşte. Astfel, după escaladarea muntelui de start, timpul de escaladare a a muntelui următor va creşte cu o oră. După escaladarea muntelui de start şi a următorului, timpul de escaladare a celui de al treilea munte va creşte cu două ore. Astfel, după escaladarea a i munţi, timpul necesar pentru escaladarea următorului munte va fi cu i ore mai mare decât timpul estimat iniţial.
Excursia poate porni de la poalele oricărui munte astfel că ei îşi pun problema de unde să înceapă excursia astfel încât la final, timpul maxim în care au escaladat un munte să fie minim.

Cerinţă

Sa se determine muntele de unde cei doi încep excursia şi timpul maxim pentru a urca un munte în cadrul excursiei, timp minim având în vedere celelalte variante de start.

Date de intrare

Fişierul de intrare munte2.in conţine pe prima linie un număr natural N reprezentând numărul de munţi. A doua linie va conţine un şir de N numere naturale, separate prin câte un spaţiu. Al i-lea număr de pe linie reprezintă numărul de ore necesare pentru escaladarea muntelui i din lanţ, neluând în calcul şi oboseala.

Date de ieşire

Fişierul de ieşire munte2.out va conţine pe prima linie două numere naturale separate printr-un spaţiu: muntele de unde cei doi încep excursia şi timpul maxim pentru a urca un munte în cadrul excursiei, timp minim având în vedere celelalte variante de start.

Restricţii

1 <= N <= 1 000 000

Exemple

munte2.inmunte2.outExplicaţii
4 5 9 10 3 2 11 Pornim excursia de la muntele 2. Timpii de escaladare sunt: 9, 10 + 1, 3 + 2, 5 + 3 cu maximul 11. Orice altă alegere a muntelui de start conduce la timpi maximi mai mari.

autor: Ştefan Gheorghe
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Despre heap: Heap-uri
Probleme recomandate
surse trimise | ajutor