[C++] Sacchi

Mario lavora in una fabbrica di zucchero come uomo delle consegne. Ha appena ricevuto un ordine:
deve consegnare esattamente N kilogrammi di zucchero a un negozio di caramelle sulla costa
dell’Adriatico. Mario può usare due tipi di pacchi: quelli che contengono 3 kg, e quelli che
contengono 5 kg di zucchero (non ci sono pacchi con misure intermedie, può usare solo pacchi
pieni da 3k o 5kg).
Mario vorrebbe usare il numero minore di pacchi possibile. Se per esempio deve consegnare 18kg
di zucchero, potrebbe usare 6 pacchi da 3kg. Ma sarebbe meglio utillizare tre pacchi da 5kg e 1
pacco da 3kg, per un totale di 4 pacchi.
Aiutate Mario a trovare il numero minore di pacchi necessari per trasportare esattamente N
kilogrammi di zucchero

INPUT (input.txt)
La prima e unica riga dell’input contiene un intero N (3 <= N <= 5000).

OUTPUT (output.txt)
L’output deve consistere di un unico numero, il numero minore di pacchi che Mario deve usare. Se è
impossibile trasportare esattamente N kilogrammi, stampare in output -1.

input.txt input.txt input.txt
4             9            18
output.txt output.txt output.txt
-1             3               4

Sfruttiamo al massimo i pacchi da 5, poi, se non bastano, usiamo quelli da tre:

Related Posts Plugin for WordPress, Blogger...