Water Pails
Dado que só dispõe de dois baldes com capacidades de tamanhos
x e y, pretende obter uma quantidade total de água nestes dois baldes que seja o mais próxima possível de uma soma-alvo s.É permitido realizar até
k operações das seguintes formas:- Encher completamente um dos baldes
- Esvaziar um dos baldes
- Despejar o conteúdo de um balde no outro, parando quando o segundo estiver cheio ou o primeiro estiver vazio (o que ocorrer primeiro).
No início, ambos os baldes estão vazios.
Pode não ser possível alcançar exatamente a soma
s utilizando os dois baldes. Por isso, é solicitado encontrar a menor diferença |s - s’|, onde s’ corresponde à quantidade total de água nos dois baldes.Entrada
A única linha de entrada contém 4 inteiros
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) e s (1 ≤ s ≤ 200).Saída
O programa deve imprimir a diferença absoluta mínima possível de obter realizando, no máximo,
k operações.Exemplos
Entrada | Saída |
14 50 2 32 | 18 |
Explicação
Podem ser realizadas apenas 2 operações. Seguem as possibilidades após 2 operações:
- (0, 0) → 0 unidades
- (14, 0) → 14 unidades
- (0, 50) → 50 unidades
- (0, 14) → 14 unidades
- (14, 36) → 50 unidades
- (14, 50) → 64 unidades
Logo, o valor que fica mais próximo de 32 é 14, resultando numa diferença de 18.
Repare que poderíamos ter obtido 36 esvaziando o primeiro balde a partir de (14, 36), mas isso exigiria 3 passos, e só nos são permitidos no máximo 2.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB