Divisió Equilibrada. X69856

Sigui v una llista de mida $n > 2$ que conté enters (tant positius com negatius). Una divisió de v és una posició $i$ de la llista (on $0 \leq i < len(v)$), tal que que divideix la llista v en dues parts: de les posicions que van del $0$ a $i-1$, i l’altra que va de $i$ fins a l’última posició: $len(v) - 1$.

La divisió equilibrada de v és una posició i ($0 \leq i < len(v)$) que minimitza aquesta diferència (on $abs$ és el valor absolut):

$$abs (\sum^{i-1}_{j=0} v[j] - \sum^{len(v)-1}_{j=i} v[j])$$

Dit altrament, la divisió equilibrada és una posició $i$ de la llista tal que diferència entre la suma dels elements que hi ha des de la posició $0$ fins a la posició $i-1$ i la suma dels elements entre les posicions $i$ i $len(v)-1$ és mínima. Fixeu-vos també que aquesta posició $i$ pot ser $0$. Això voldrà dir que la part esquerra de la llista serà buida (i per tant, la seva suma valdrà $0$) i la part dreta anirà de la posició $0$ fins a la $len(v)-1$, és a dir, serà tot el vector.

Fes la funció divisio_equilibrada(v) tal que, donat una llista v, en torni la divisió equilibrada. Si n’hi haguessin més d’una, torneu la de més a l’esquerra. Com ja hem explicat, el valor $0$ per a una divisió equilibrada és possible, ja que vol dir que una la divisió de l’esquerra és buida. Recordeu, que per definició, la suma d’una llista (o un tros de llista) buit és zero.

Per exemple, si la funció rep la llista $v = [4 , 1 , 2 , 3]$, torna $2$, ja que $(4 + 1) - (2 + 3) = 0$, mentre que si rep la llista $v = [2 , 1 , -3 , 4]$, torna un $1$, que és la partició equilibrada, ja que $(2) - (1 - 3 + 4) = 0$ és la diferència mínima entre la divisió esquerra i la dreta.

Tingueu en compte que, si calculeu la suma total de la llista al principi de la funció, podreu resoldre aquest problema amb una sola passada sobre la llista v.

Entrada

Una llista v d’enters, amb, almenys, dos elements.

Sortida

La divisió equilibrada de la llista v. Si n’hi haguessin més d’una, torneu la de més a l’esquerra.