Programozás‎ > ‎Feladatok‎ > ‎

Nyaklánc

Egy körbefűzött nyakláncon N darab (N páros), különböző értékű gyöngy van. A nyakláncot az i-edik gyöngy után elvághatjuk. Az egyes gyöngyök értéke a vágás helyétől vett kisebb távolsággal megszorzódik (a két közvetlen szomszéd éréke egyszeres, az eggyel távolabbiak kétszeres, a még eggyel távolabbiak háromszoros értékűek lesznek, ... és így tovább). 

Feladat

Írjunk programot, ami megadja, hogy hol vágjuk el a nyakláncot, hogy az összérték a lehető legnagyobb legyen!

Bemenet

A bemenet első sorában a gyöngyök száma (3 <= N <= 1000000) van. A következő N sor mindegyike egy egész számot tartalmaz, közülük az i-edik az i-edik gyöngy értékét (1 <= értéki <= 100).

Kimenet

Egyetlen sorába annak a gyöngynek a sorszámát kell írni, amely után elvágva a nyakláncot, a gyöngyök összértéke a lehető legnagyobb lesz! Több megoldás esetén bármelyik megadható.

Példa

Bemenet  Kimenet
4
30
30
10
20
3


Tesztadatok

Címkék

A feladat forrása: NTOITV 3. forduló, 11-13. évfolyam
Algoritmusok: 

megoldás