Water Pails
Dado que solo dispones de dos cubos de tamaños
x y y, tu objetivo es obtener la cantidad total de agua en esos dos cubos lo más cercana posible al valor objetivo s.Tienes permitido realizar como máximo
k operaciones de los siguientes tipos:- Llenar uno de los cubos completamente.
- Vaciar uno de los cubos.
- Verter el contenido de un cubo en el otro, deteniéndote cuando el segundo se llene o cuando el primero se vacíe (lo que suceda primero).
Al inicio, ambos cubos están vacíos.
Es posible que no logres exactamente la suma
s en ambos cubos, así que necesitas determinar la diferencia más pequeña |s - s’|, donde s’ representa la cantidad total de agua que hay en los dos cubos combinados.Input
La única línea de la entrada contiene 4 enteros
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) y s (1 ≤ s ≤ 200).Output
El programa debe mostrar la menor diferencia absoluta posible que puedas obtener ejecutando, como máximo,
k operaciones.Examples
Input | Output |
14 50 2 32 | 18 |
Explanation
Solo se permiten 2 operaciones. A continuación se muestran todos los resultados posibles después de hacer 2 operaciones:
- (0, 0) → 0 unidades
- (14, 0) → 14 unidades
- (0, 50) → 50 unidades
- (0, 14) → 14 unidades
- (14, 36) → 50 unidades
- (14, 50) → 64 unidades
La cantidad más cercana a 32 que podemos obtener es 14, de modo que la diferencia es 18.
Observa que podríamos haber llegado a 36 vaciando el primer cubo a partir de (14, 36), pero eso hubiera requerido 3 pasos, y solo tenemos permitido realizar 2 como máximo.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB