Le nostre soluzioni alle Olimpiadi di Informatica 2017 – Parte 3

Aleandro Prudenzano/ dicembre 19, 2017/ +/ 0 comments

Eccoci arrivati, finalmente, alla terza parte delle nostre soluzioni per le selezioni scolastiche delle olimpiadi di informatica 2017-2018.

Dopo aver parlato di logica, matematica e di programmazione, in questa ultima parte daremo un’occhiata agli esercizi a carattere algoritmico. Come al solito vi auguro una buona lettura!

Esercizi a carattere algoritmico

Nonostante il nome altisonante, non si tratta altro che di esercizi in cui la logica viene mischiata alla programmazione.
Per risolverli basta mettersi a pensare ai dati che si hanno e tracciare una procedura che ci porti alla fine.

Esercizio 13

Parliamo di come si esce da un ciclo che analizza un vettore con solo l’ausilio delle espressioni condizionali, delle variabili (e costanti) e degli array.
I cicli iterativi nella maggior parte dei linguaggi hanno la così detta “uscita per falso” ovvero: quando la condizione in testa (o in coda) diventa falsa il ciclo termina.

Ragioniamo sulle affermazioni a noi proposte: la prima non è indispensabile in quanto se si visita il vettore partendo da n-1 e finendo a 0 l’ultima cella è la prima visitata, quindi la scartiamo.

La seconda condizione in poche parole ci dice che il valore della condizione del ciclo assume entrambi i valori possibili, se assume entrambi i valori vuol dire che per un po’ abbiamo navigato, ma poi ne siamo usciti, questa condizione è importante.

La terza affermazione non ha senso in quanto un ciclo iterativo di per se non ha nulla a che fare con variabili globali o parametri alle funzioni!

Risposta: b


Esercizio 14

Esercizio abbastanza facile da risolvere se ci si approccia graficamente al problema.
Ci basterà rappresentare i 4 plichi di fogli e raggruppare i fogli seguendo la regola del “mai più di un foglio dallo stesso fascicolo” per ottenere 4 gruppi da 3 fogli (e siamo a 12 fogli) e due gruppi da soli 2 fogli (e sono i 4 rimanenti).

Qui una rappresentazione grafica:

Risposta: S=6


Esercizio 15

Come nel precedente anche qui conviene un approccio grafico al problema quindi iniziamo col disegnarci la matrice riportandoci i valori, le bandiere, il punto di partenza e quello di arrivo.

Ora con un colore diverso per ognuno tracciamoci i vari percorsi fattibili, (consiglio di iniziare a fare quello più a sinistra e man mano proseguire verso destra) e riportiamoci accanto ad essi il valore in monete.
Una volta tracciati tutti i percorsi fattibili, li contiamo ed otteniamo N, il numero di monete minore sarà MIN, quello massimo sarà MAX.

In questi esercizi l’errore più presente è quello di ingarbugliarsi con i vari tratti e finire per non considerare un tracciato o considerarne uno più di una volta, quindi è importante avere un criterio con il quale passare da un percorso all’altro!

Risposta: N=22, MIN=6, MAX=24


Esercizio 16

Per risolvere questo esercizio la tattica che ho usato io è stata quella di creare un piccolo albero in cui al vertice c’è il risultato, ed i rami sono gli elementi necessari.
A questi elementi poi si attaccano gli altri elementi e così via fino ad arrivare alla combinazione di base per ottenere tutto.
Così facendo non ci basta che trovare la giusta combinazione per minimizzare il numero di operazioni necessarie.

Piccolo diagramma esplicativo del mio ragionamento:

Risposta: 4


Esercizio 17

Se rappresentassimo il salto di Hulk con un 1 e l’attesa del prossimo minuto con uno 0 otterremo la rappresentazione binaria del numero dato.
Una volta ottenuto ciò abbiamo che il numero di salti è il numero di 1 presenti nel numero, il numero di attese è il numero di 0, ma il tempo totale per arrivare al traguardo è dato dal totale delle cifre – 1 poiché tra ogni cifra e l’altra è come se passasse un minuto, quindi abbiamo tanti spazi quante le cifre – 1.

Risposta: 6


Esercizio 18

Procediamo a simulare una partita: iniziano i bambini quindi compiamo le loro mosse e noi andremo a fare la mossa contraria a loro (altrimenti non prenderemmo nessun lingotto), quindi abbiamo questa situazione:

Proseguiamo nella maniera che ci permette di non capitare sulle caselle da cui sono già passati gli avversari:

Ancora una volta:


Un’ultima volta:

Le partite sono finite, giocando con Simone si ha il termine della partita grazie al nostro avversario con una differenza di 300 punti a nostro favore, nella partita contro Daniele invece saremo noi a causare il termine con ben 700 punti in meno.

Risposta: G=S, P=300


Esercizio 19

In questo caso abbiamo dello pseudo-codice da seguire per verificare che l’output sia quello segnalato sopra, basterà solamente seguire il codice riga per riga per arrivare alla soluzione.

Risposta: V=A, Disegno=Sì


Esercizio 20

La risposta in questo caso è la b in quanto facendo i vari calcoli dei percorsi proposti si ottiene che nel primo caso abbiamo un tempo di 9,5 ms per il primo movimento ed uno di 17 per il secondo, quindi diciamo 17 ms necessari.
Per la c necessitiamo di 23 ms per il primo e 4 per il secondo: quindi 23 ms, per la d rispettivamente 4 ms e 17 ms, quindi 18 ms poiché non possiamo avere più di un segnale sullo stesso ramo; ed infine per la b ci troviamo a compiere un movimento in soli 16 ms, per il secondo movimento si potrà anche scegliere tra gli altri proposti in modo da avere sempre meno di 16 ms necessari.

Risposta: b

About Aleandro Prudenzano

17 anni passati tra scienza, computer, elettronica e serie tv. Ora provo a raccontare a voi un po' delle cose che ho imparato negli anni nell'attesa di impararne altre. Enjoy the culture!

Facci sapere cosa ne pensi con un commento!