Secchi d’Acqua
Se hai soltanto due recipienti di capacità
x e y, il tuo obiettivo è ottenere una quantità totale di acqua in questi due recipienti che sia la più vicina possibile a un determinato valore s.Hai la possibilità di compiere fino a
k operazioni tra le seguenti:- Riempire completamente uno dei due recipienti
- Svuotare uno dei due recipienti
- Versare il contenuto di un recipiente nell’altro, fermandoti non appena il secondo è pieno oppure il primo è vuoto (a seconda di cosa accade prima).
All’inizio, entrambi i recipienti sono vuoti.
Potrebbe non essere sempre possibile ottenere esattamente la somma
s in entrambi i recipienti. Per questo motivo, ti viene richiesto di trovare la differenza minima |s - s’|, dove s’ è il quantitativo complessivo di acqua nei due recipienti.Input
L’unica riga dell’input contiene 4 interi
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) e s (1 ≤ s ≤ 200).Output
Il programma deve stampare la minima differenza assoluta ottenibile eseguendo al massimo
k operazioni.Esempi
Ingresso | Uscita |
14 50 2 32 | 18 |
Spiegazione
È possibile effettuare solo 2 operazioni. Ecco le situazioni raggiungibili dopo 2 operazioni:
- (0, 0) → 0 unità
- (14, 0) → 14 unità
- (0, 50) → 50 unità
- (0, 14) → 14 unità
- (14, 36) → 50 unità
- (14, 50) → 64 unità
La quantità più vicina a 32 è 14, con una differenza di 18.
Da notare che saremmo potuti arrivare a 36 svuotando il primo recipiente partendo da (14, 36), ma ciò avrebbe richiesto 3 operazioni, mentre il limite massimo è 2.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB