Una gara di canoe sta per iniziare. Sfortunatamente dei forti venti hanno danneggiato alcune canoe e
la gara sta per iniziare!
Per fortuna alcune squadre hanno portato una canoa di riserva. Siccome le canoe sono pesanti e
difficili da trasportare, le squadre sono disposte a prestare la loro canoa di riserva (se ce l’hanno) a
una squadra avversaria se e solo se sono disposti immediatamenti vicini a loro (alla partenza, cioè
se hanno numeri di partenza immediatamente vicini). Per esempio, la squadra con il numero di
partenza 4, sarà disposta a prestare la sua canoa di riserva solo alle squadre con numero di partenza
3 e 5. Ovviamente se una squadra che ha portato la canoa di riserva ha la sua canoa danneggiata,
utilizzerà la canoa di riserva per sè.
Tu, come organizzatore della gara, vuoi sapere qual è il minimo numero di squadre che non possono
iniziare la gara, neanche con canoe imprestate.
INPUT (input.txt)
La prima riga dell’input contiene tre interi: N, (2 <= N <= 10), il numero totale di squadre, S (2 <=
S <= N), il numero delle squadre con canoe danneggiate e R ( 2 <= R <= N), il numero di squadre
con canoe di riserva.
La seconda riga dell’input contiene esattamente S numeri, i numeri delle posizioni alla partenza
delle squadre con canoe danneggiate. Questa riga non contiene duplicati.
La terza riga dell’input contiene esattamente R numeri, i numeri delle posizioni alla partenza delle
squadre con canoe di riserva. Questa riga non contiene duplicati.
OUTPUT (output.txt)
L’output contiene un singolo numero, il numero minimo di squadre che non possono iniziare la
gara.
|
1 |
input.txt input.txt<br /><span style="color: #0000dd; font-weight: bold;">5</span> <span style="color: #0000dd; font-weight: bold;">2</span> <span style="color: #0000dd; font-weight: bold;">3</span> <span style="color: #0000dd; font-weight: bold;">5</span> <span style="color: #0000dd; font-weight: bold;">2</span> <span style="color: #0000dd; font-weight: bold;">1</span><br /><span style="color: #0000dd; font-weight: bold;">2</span> <span style="color: #0000dd; font-weight: bold;">4</span> <span style="color: #0000dd; font-weight: bold;">2</span> <span style="color: #0000dd; font-weight: bold;">4</span><br /><span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #0000dd; font-weight: bold;">3</span> <span style="color: #0000dd; font-weight: bold;">5</span> <span style="color: #0000dd; font-weight: bold;">3</span><br /><br />output.txt output.txt<br /><span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #0000dd; font-weight: bold;">1</span><br /> |
SOLUZIONE:
Procediamo con ordine: se una squadra ha una canoa:
* gli serve? se la tiene
* serve a sinistra? la da alla squadra di sisnistra
*la da alla squadra di destra
|
1 |
<span style="color: #557799;">#include <iostream></span><br /><span style="color: #557799;">#include <cstdlib></span><br /><span style="color: #557799;">#include <fstream></span><br /><br /><span style="color: #008800; font-weight: bold;">using</span> <span style="color: #008800; font-weight: bold;">namespace</span> std;<br /><br /><span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">main</span>(){<br /> ifstream in (<span style="background-color: #fff0f0;">"input.txt"</span>);<br /> ofstream out (<span style="background-color: #fff0f0;">"output.txt"</span>);<br /><br /><span style="color: #333399; font-weight: bold;">int</span> n,s,r,d<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;<br /><br />in <span style="color: #333333;">>></span>n<span style="color: #333333;">>></span>s<span style="color: #333333;">>></span>r;<br /><span style="color: #333399; font-weight: bold;">int</span> dann[s],ris[r];<br /><span style="color: #333399; font-weight: bold;">bool</span> pos[n][<span style="color: #0000dd; font-weight: bold;">2</span>];<br /><br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span>s;i<span style="color: #333333;">++</span>)<br />in<span style="color: #333333;">>></span> dann[i];<br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span>r;i<span style="color: #333333;">++</span>)<br />in<span style="color: #333333;">>></span> ris[i];<br /><br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span> n;i<span style="color: #333333;">++</span>)<br /> pos[i][<span style="color: #0000dd; font-weight: bold;">0</span>]<span style="color: #333333;">=</span>pos[i][<span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;<br /> <br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span> s;i<span style="color: #333333;">++</span>)<br /> pos[dann[i]][<span style="color: #0000dd; font-weight: bold;">0</span>]<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>;<br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span> r;i<span style="color: #333333;">++</span>)<br /> pos[ris[i]][<span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>;<br /> <br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span> n;i<span style="color: #333333;">++</span>)<br /><span style="color: #008800; font-weight: bold;">if</span> (pos[i][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">&&</span> pos [i][<span style="color: #0000dd; font-weight: bold;">1</span>])<br /> pos[i][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> pos [i][<span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;<br /><br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span> n;i<span style="color: #333333;">++</span>)<br /><span style="color: #008800; font-weight: bold;">if</span> ( i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">>=</span> <span style="color: #0000dd; font-weight: bold;">0</span> <span style="color: #333333;">&&</span> pos[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">&&</span> pos [i][<span style="color: #0000dd; font-weight: bold;">1</span>])<br />pos[i<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> pos [i][<span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;<br /><span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span> (i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span><span style="color: #333333;"><</span>n <span style="color: #333333;">&&</span> pos[i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">&&</span> pos [i][<span style="color: #0000dd; font-weight: bold;">1</span>])<br />pos[i<span style="color: #333333;">+</span><span style="color: #0000dd; font-weight: bold;">1</span>][<span style="color: #0000dd; font-weight: bold;">0</span>] <span style="color: #333333;">=</span> pos [i][<span style="color: #0000dd; font-weight: bold;">1</span>]<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;<br /><br /><span style="color: #008800; font-weight: bold;">for</span> (<span style="color: #333399; font-weight: bold;">int</span> i<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">0</span>;i<span style="color: #333333;"><</span> n;i<span style="color: #333333;">++</span>)<br /><span style="color: #008800; font-weight: bold;">if</span> (pos[i][<span style="color: #0000dd; font-weight: bold;">0</span>]) d<span style="color: #333333;">++</span>;<br /><br />out<span style="color: #333333;"><<</span>d;<br /><br /><br /> <span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;}<br /> |
