Fișierul intrare/ieșire	neo.in, neo.out	Sursă	ONI 2004 clasa a 7-a
Autor	autor necunoscut	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Neo (clasa a 7-a)

Notă: această problemă a fost modificată față de original. Limitele au fost mărite pentru a o aduce la zi cu cunoștințele din anul 2014.

Neo, eroul din filmul Matrix, pentru a-și învinge adversarii are nevoie de energie. El a descoperit în matrice o zonă care cuprinde locații consecutive numerotate de la 1 la N, fiecare dintre ele generând o anumită cantitate de energie, pozitivă sau negativă, cunoscută.

Neo are posibilitatea să pătrundă în această zonă printr-o singură locație și poate părăsi zona o singură dată. El, odată intrat în zona energetică, trebuie să străbată locațiile în ordinea crescătoare a numărului lor, iar energia acumulată într-o locație multiplică de atâtea ori energia deja acumulată de Neo. De asemenea, dacă într-o locație se află energie negativă, iar Neo a acumulat până în acea locație energie pozitivă, toată energia lui se transformă în energie negativă, dar dacă în drumul său Neo întâlnește o altă locație cu energie negativă, iar energia deținută de el este tot negativă, toată energia lui devine pozitivă. Energia inițială a lui Neo are valoarea 1.

Cerință

Ajutați-l pe Neo să descopere locația în care trebuie să intre și locația în care trebuie să părăsească zona energetică pentru a acumula cea mai mare cantitate de energie pozitivă posibilă.

Date de intrare

Din fișierul de intrare neo.in se citesc:

• de pe linia 1 numărul locațiilor energetice
• de pe linia 2 un șir de numere întregi reprezentând cantitatea de energie a fiecărei locații, valori separate două câte două printr-un spațiu

Date de ieșire

În fișierul de ieșire neo.out se scriu:

• pe linia 1 cantitatea de energie acumulată de Neo
• pe linia 2 două valori separate printr-un spațiu: numărul de ordine al locației în care Neo pătrunde în zona energetică și numărul de ordine al locației în care Neo iese din zona energetică. Dacă nu se poate obține energie pozitivă, cantitatea de energie acumulată și numărul de ordine al locațiilor vor fi 0.

Restricții

• 1 ≤ N ≤ 10000
• -3 ≤ valoarea energiei dintr-o locație ≤ 3
• -2⁶³ ≤ produsul energiilor din orice grup de locații adiacente < 2⁶³
• Dacă există mai multe soluții pentru datele de intrare, se va afișa una singură.
• Pentru 50% din teste N ≤ 100
• Pentru 70% din teste N ≤ 1000

Exemple