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 \le 2\cdot\max\{A[i]\}, 0\le 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ó:

bool es_segmentable(const vector<int>& A, int k)

 
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.