Subsecuencia de suma mínima P95982


Statement
 

pdf   zip

thehtml

Dada una secuencia de n números enteros x1xn, 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