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:
|
1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> 7<br /> 8<br /> 9<br />10<br />11<br />12<br />13<br />14<br />15<br />16<br />17<br />18<br />19<br />20<br />21<br />22<br />23<br />24<br />25<br />26<br />27 |
|
|
<span style="color: #009999;">#include <iostream></span><br /><span style="color: #009999;">#include <cstdlib></span><br /><span style="color: #009999;">#include <fstream></span><br /><br /><span style="color: #006699; font-weight: bold;">using</span> <span style="color: #006699; font-weight: bold;">namespace</span> std;<br /><br /><span style="color: #007788; font-weight: bold;">int</span> <span style="color: #cc00ff;">main</span>(){<br /> ifstream in (<span style="color: #cc3300;">"input.txt"</span>);<br /> ofstream out (<span style="color: #cc3300;">"output.txt"</span>);<br /> <br /> <span style="color: #007788; font-weight: bold;">int</span> k,d5,d3,s3;<br /> in<span style="color: #555555;">>></span>k;<br /><br />d5<span style="color: #555555;">=</span> k<span style="color: #555555;">/</span><span style="color: #ff6600;">5</span>;<br />d3<span style="color: #555555;">=</span> k<span style="color: #555555;">-</span>d5<span style="color: #555555;">*</span><span style="color: #ff6600;">5</span>;<br />s3<span style="color: #555555;">=</span>d3<span style="color: #555555;">/</span><span style="color: #ff6600;">3</span>;<br /><br /><span style="color: #006699; font-weight: bold;">while</span> (d3<span style="color: #555555;">%</span><span style="color: #ff6600;">3</span> <span style="color: #555555;">!=</span> <span style="color: #ff6600;">0</span> <span style="color: #555555;">&&</span> d5<span style="color: #555555;">-</span><span style="color: #ff6600;">1</span> <span style="color: #555555;">>-</span><span style="color: #ff6600;">1</span>){<br />d3<span style="color: #555555;">=</span> k<span style="color: #555555;">-</span>(<span style="color: #555555;">--</span>d5)<span style="color: #555555;">*</span><span style="color: #ff6600;">5</span>;<br />s3<span style="color: #555555;">=</span>d3<span style="color: #555555;">/</span><span style="color: #ff6600;">3</span>;}<br /><br /> <br /><span style="color: #006699; font-weight: bold;">if</span> (d3<span style="color: #555555;">%</span><span style="color: #ff6600;">3</span> <span style="color: #555555;">==</span><span style="color: #ff6600;">0</span> )<br />out<span style="color: #555555;"><<</span> d5<span style="color: #555555;">+</span>s3;<br /><span style="color: #006699; font-weight: bold;">else</span><br /> out<span style="color: #555555;"><<</span> <span style="color: #555555;">-</span><span style="color: #ff6600;">1</span>;<br /> <span style="color: #006699; font-weight: bold;">return</span> <span style="color: #ff6600;">0</span>;}<br /> |
|