Copiado al portapapeles
Descripción
La eficiencia de la última computadora que compró ha estado funcionando muy rara. Usted supone que tiene mucho espacio libre en los disco de su maquina. Sin embargo el espacio libre esta distríbuido en muchos discos. Usted decide que el secreto para mejorar la eficiencia es consolidar todos los datos en la menor cantidad de discos.
Dado un vector que representa el espacio utilizado de disco, un segundo vector que representa la capacidad total de cada disco, debe tratar de empaquetar los datos en la menor cantidad de discos. Imprimir la cantidad de discos que contienen datos después de la consolidación.
La cantidad de discos está entre $1$ y $50$ elementos.
Los valores de los discos están entre $1$ y $1000$.
Por ejemplo si tenemos $3$ discos con capacidad de $350,600,115$ y espacio ocupado $300,525,110$ veamos:
-
Disco 1 $350 MB$ total, $300 MB$ usados, $50 MB$ libres
-
Disco 2 $600 MB$ total, $525 MB$ usados, $75 MB$ libres
-
Disco 3 $115 MB$ total, $110 MB$ usados, $5 MB$ libres
Una forma de empaquetar los datos en el menor número de discos es primero mover $50 MB$ del
disco $3$ al disco $1$, llenando este completamente. La próxima vez mover los $60 MB$ restantes del Disco $3$ al Disco $2$. Como quedan dos disco con datos después del proceso la respuesta es $2$.
Entrada
En la entrada de datos hay varios casos de prueba.
Cada caso de prueba comienza con una línea que contiene un número entero $N$ que indica el número de discos.
Las siguientes líneas contienen $N$ valores representando el espacio ocupado de los discos.
Luego, siguen $N$ valores representando las capacidades de los discos.
La entrada termina cuando no hay más datos.
Salida
Imprima en una línea el menor número de discos en los que se pueden empaquetar los todos datos.
Ejemplo Entrada
3 300 525 110 350 600 115 6 1 200 200 199 200 200 1000 200 200 200 200 200 5 750 800 850 900 950 800 850 900 950 1000
Ejemplo Salida
2 1 5
Ayuda
Debe asegurarse que todos los discos anteriores queden totalmente llenos para pasar a llenar el siguiente disco
Aclaración entrada:
3
300 525 110
350 600 115
6
1 200 200 199 200 200
1000 200 200 200 200 200
5
750 800 850 900 950
800 850 900 950 1000