Vectors Segmentables X95177

Donats un vector A de nombres naturals i una constant k > 0, una k-segmentació del vector es construeix de la manera següent: Es comença des del primer element i es van sumant elements mentre la suma sigui menor o igual que k. A continuació es comencen a restar elements mentre la suma sigui més gran o igual que 0. A continuació es comencen a sumar elements mentre la suma menor o igual que k i així succesivament. El vector es k-segmentable si amb aquest procés s’arriba al final del vector.

Per exemple, el vector A = {4, 4, 1, 2, 6, 7, 1, 1, 8, 2, 6, 7} és 9-segmentable perquè es pot travessar tot el vector seguint el procediment descrit anteriorment com es veu a continuació (on S és 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 canvi, el vector no és 8-segmentable perquè si agafem k = 8, ens quedem aturats a mig camí, ja que el 6 no el podem ni sumar ni restar sense superar k o ser negatiu:

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

Escriviu un programa que trobi la k més petita tal que A sigui k-segmentable. És fàcil demostrar que sempre existeix un valor de k tal que k ≤ 2·max{A[i]}, 0≤ i < A.size().

Entrada

L’entrada consiteix en un natural n, seguit de n naturals A[0], …, A[n-1].

Sortida

La sortida és el mínim valor de k tal que A és k-segmentable.

Observació

Es recomana fer servir una funció:

 
que determina si el vector és k-segmentable.

Per a dissenyar una solució eficient, convé pensar en tots aquells valors de k que no cal provar.