Fişierul intrare/ieşire:neo.in, neo.outSursăONI 2004 clasa a 7-a
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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
  • -263 ≤ produsul energiilor din orice grup de locaţii adiacente < 263
  • 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

neo.inneo.out
4
-3 -2 2 -3
12
2 4
1
-2
0
0 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici