Capacitats. X94550

Siguin X i Y dos vectors de naturals. El vector X de mida N1 conté les capacitats de N1 caixes. El vector Y de mida N2 conté els pesos dels N2 elements que cal col·locar a X.

Per exemple, si $X = [10, 10, 5]$ això vol dir que hi ha 2 caixes de capacitat $10$ cadascuna seguides d’una de capacitat $5$. Si $Y = [4,3,1,3,4]$, cal col·locar (si podem) aquests $5$ elements a $X$.

El procediment per a col·locar un element és molt simple: per a un element $Y[i]$ i mirem de col·locar-lo a la primera caixa d’X que puguem (a partir de la primera caixa). Pot ser que no puguem col·locar un pes en una caixa per dos motius: (1) perquè la caixa no té prou capacitat per al pes o (2), perquè la caixa té prou capacitat, però té altres pesos a dins, i el pes que volem col·locar ja no hi cap. Si no podem col·locar un pes en cap caixa, acabem i tornem la posició d’aquest pes: i. Si podem col·locar-lo, llavors anem a $Y[i + 1]$. Si ja hem acabat de col·locar tots els elements de Y, llavors tornem N2 + 1, cosa que voldrà dir que hem pogut col·locar tots els elements d’Y.

Per exemple, si $X = [10, 10, 5]$ i $Y = [4,3,1,3,4]$ actuarem així: Col·loquem $4$ a la primera caixa. Col·loquem $3$ a la primera caixa. Col·loquem $1$ a la primera caixa. Col·loquem $3$ a la segona caixa (la caixa anterior està massa plena). Col·loquem $4$ a la segona caixa. Tornem $6$, que vol dir que hem col·locat tots els elements d’Y.

Fes la funció colloca(X,Y) tal que, donat un vector de capacitats X i un de pesos Y, torni fins a quin element d’Y s’ha quedat per col·locar. Si torna length(Y) + 1 voldrà dir que els ha pogut col·locar tots.

Per exemple, si $X = [10,10,10]$ i $Y = [9,9,9,1,1,1]$, llavors la funció torna $7$. Si $X = [10,10,10]$ i $Y = [9,11]$, llavors la funció torna $2$. Si $X = [1,4]$ i $Y = [5,5,5,5,5]$, llavors la funció torna $1$.

Entrada

Un vector de capacitats X i un de pesos Y.

Sortida

Fins a quin element d’Y s’ha quedat per col·locar. Si torna length(Y) + 1 voldrà dir que els ha pogut col·locar tots.