Vectores Segmentables X95177

Dados un vector A de números naturales y una constante k > 0, una k-segmentación del vector se construye de la siguiente forma: Se comienza desde el primer elemento y se van sumando elementos mientras la suma sea menor o igual que k. A continuación se empiezan a restar elementos mientras la suma sea mayor o igual que 0. A continuación se comienzan a sumar elementos mientras la suma sea menor o igual que k y así sucesivamente. El vector es k-segmentable si con este proceso se llega al final del vector.

Por ejemplo, el vector A = {4, 4, 1, 2, 6, 7, 1, 1, 8, 2, 6, 7} es 9-segmentable porque se puede atravesar todo el vector siguiendo el procedimiento descrito anteriormente como se ve a continuación (donde S es la suma):

A: 4 4 1 2 6 7 1 1 8 2 6 7
S: 4 8 9 7 1 8 9 8 0 2 8 1
   + + + - - + + - - + + -

En cambio, el vector no es 8-segmentable porque si tomamos k = 8, nos quedamos parados a medio camino, ya que el 6 no podemos ni sumarlo ni restarlo sin superar k o ser negativo:

A: 4 4 1 2 6 7 1 1 8 2 6 7
S: 4 8 7 5
   + + - -

Escriba un programa que encuentre la k más pequeña tal que A sea k -segmentable. Se puede demostrar que siempre existe un valor de k tal que k ≤ 2·max{A[i]}, 0≤ y < A.size().

Entrada

La entrada consiste en un natural n, seguido de n naturales A[0], …, A[n-1].

Salida

La salida es el mínimo valor de k tal que A es k-segmentable.

Observación

Se recomienda utilizar una función:

 
que determina si el vector es k-segmentable.

Para diseñar una solución eficiente, conviene pensar en todos aquellos valores de k que no hace falta probar.