Subsecuencia de suma mínima P95982


Statement
 

pdf   zip

thehtml

Dada una secuencia de n números enteros x1 …xn, calculad su subsecuencia consecutiva no vacía cuya suma sea más próxima a cero.

Entrada

La entrada tiene diversos casos. Cada caso empieza con n, seguido de n números enteros con valor absoluto no mayor que 105.

Salida

Para cada caso, escribid el valor absoluto de la suma más próxima a cero, seguido de los índices izquierdo i y derecho d que delimitan la suma óptima xi + … + xd. Si hay más de una solución, escoged la i mínima. Si sigue el empate, escoged la d mínima.

Puntuación

  • test-1:  ‍10 Puntos ‍

    Resolver casos como los del ejemplo 1, con 1 ≤ n ≤ 10, y con una sola subsecuencia de suma óptima.

  • test-2:  ‍ Resolver casos como los del ejemplo 2, con 1 ≤ n ≤ 200.  ‍20 Puntos ‍
  • test-3:  ‍ Resolver casos con 1 ≤ n ≤ 104.  ‍70 Puntos ‍
Public test cases

  • Input

    2   5 -4
1   -10
4   20 -9 3 4
3   1 0 2

    Output

    1 1 2
10 1 1
2 2 4
0 2 2

  • Input

    4   0 0 0 0
6   10 -9 -2 -1 -3 2
3   1000 6 -1000

    Output

    0 1 1
1 1 2
6 1 3
    • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions