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