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 |