Olimpiadi di Informatica 2006

Premessa

1. La prova consiste di 12 esercizi a carattere logico matematico e 8 esercizi di programmazione, in modo tale che il tempo a disposizione sia appena sufficiente per risolverli tutti. Gli esercizi sono di due tipologie: la prima, a risposta chiusa, contiene domande ciascuna accompagnata da quattro risposte indicate con le lettere a, b, c, d: una sola di queste risposte è corretta; la seconda tipologia, a risposta aperta, prevede che la risposta, consistente di uno o più valori numerici, sia scritta direttamente dal candidato.
2. Gli esercizi hanno un punteggio differente a seconda della difficoltà. Il punteggio è indicato all’inizio dell’esercizio stesso e nella tabella sottostante: per ogni risposta esatta ottieni i punti indicati; per ogni risposta sbagliata ottieni un punto negativo; per ogni esercizio lasciato senza risposta ottieni zero punti. Il punteggio totale degli esercizi a carattere logico-matematico è 16; quello delle domande di programmazione è 19. Quindi il massimo punteggio ottenibile è 35.
3. La risposta va riportata nell’apposito spazio della tabella sottostante segnando il quadratino che corrisponde a quella ritenuta esatta, oppure scrivendola, nel caso la domanda sia a risposta aperta. Non sono ammesse cancellature o correzioni sulla tabella delle risposte.
4. Non è consentito l'uso di alcun tipo di PC o calcolatrice. Non è possibile consultare libri, appunti, manuali, pena l’esclusione dalla selezione. È consentito utilizzare fogli bianchi per appunti e calcoli.
5. Il tempo assegnato per svolgere la prova è di 60 minuti.
6. Indicare chiaramente nome, cognome, data di nascita, classe, indirizzo e-mail ed il linguaggio di programmazione scelto.

Esercizi a carattere logico-matematico

1) La risposta esatta vale 1 punto.
Se un uomo dipinge una stanza in 4 ore e un suo amico ne impiega 2, quanto tempo impiegherebbero dipingendola insieme? (Si assume che quando lavorano insieme ciascuno opera alla stessa velocità di quando lavora da solo).

1. 75 minuti
2. 80 minuti
3. 90 minuti
4. 180 minuti

2) La risposta esatta vale 1 punto.
Se una gallina e mezza fa in media un uovo e mezzo in un giorno e mezzo, quante uova fanno in media 9 galline in 9 giorni?

3) La risposta esatta vale 1 punto.
Quanti modelli di macchine di Formula 1 ha Mario se sono tutte Ferrari meno tre, sono tutte McLaren meno due ed ha anche una Williams?

1. 3
2. 4
3. 5
4. 6

4) La risposta esatta vale 1 punto.
Una maestra ha una scatola di 1300 penne, e vuole distribuirle in modo equo ai suoi alunni. Inizialmente distribuisce ad ogni alunno un numero di penne pari al numero di alunni stessi. Dopo di che, visto che ne rimangono ancora molte, decide di darne altre due ciascuno. Alla fine nella scatola ne rimangono solo cinque, che ella tiene per sé. Quanti sono gli alunni?

5) La risposta esatta vale 1 punto.
Al ritorno dalla guerra durata parecchi anni, un giovane torna a casa. Ad attenderlo trova la cognata del marito dell'unica sorella di sua madre. Dato che il marito non ha fratelli, chi e’ la donna che lo ha accolto?

1. madre
2. sorella
3. zia
4. nonna

6) La risposta esatta vale 1 punto.
Fondendo una statua di bronzo alta 50 cm e piena internamente, realizzo con il bronzo fuso ottenuto tante statuette simili (cioè con le stesse proporzioni della statua originale), anch'esse internamente piene, ma dell'altezza di 10 cm. Quante statuette riesco a realizzare?

1. 5
2. 25
3. 50
4. 125

7) La risposta esatta vale 1 punto.
A Policrate che gli domandava quanti erano i suoi allievi, così rispose Pitagora:
"I miei allievi possono essere suddivisi in insiemi disgiunti; in particolare

• la metà coltiva la matematica
• la quarta parte si dedica allo studio della natura
• la settima parte ascolta con religioso silenzio le mie parole
• inoltre ci sono tre allievi che non fanno nessuna delle cose precedenti"

Quanti erano gli allievi di Pitagora?

8) La risposta esatta vale 1 punto.
Data una torre, costruita inserendo N = 23 mattoncini LEGO uno sopra l'altro, indicare il numero minimo di porzioni in cui suddividere la torre per essere sicuri che sia possibile prendere un qualsiasi numero (compreso fra 1 e 22, estremi inclusi) di mattoncini senza smontare le porzioni e selezionando un opportuno insieme di porzioni.
Ad esempio se N = 6 allora la risposta è 3. Infatti la divisione dei mattoncini in tre porzioni di dimensioni 1, 2 e 3 soddisfa i requisiti. Inoltre, non esiste una soluzione che divide i mattoncini in due sole porzioni; infatti, se si dividono 6 mattoncini in porzioni da 1 e 5 mattoncini non si riesce a formare un insieme di 2 (oppure di 3 o di 4) mattoncini; un analogo problema sorge se si dividono 6 mattoncini in due porzioni da 2 e 4 oppure in due porzioni da 3.
Se N = 23 qual’è il numero minimo di porzioni?

1. 4
2. 5
3. 6
4. 7

9) La risposta esatta vale 2 punti.
Il direttore di un ristorante con capienza massima 150 posti non ricorda quante erano le persone da lui servite in occasione dello scorso cenone di fine anno.
Ricorda però che volendo sistemare tutte le persone servite in tavoli da 3 ne restava fuori esattamente una; inoltre, la stessa cosa succedeva sistemando tutte le persone in tavoli da 5 o tutte in tavoli da 7.
Quante erano le persone servite in occasione dello scorso cenone di fine anno?

10) La risposta esatta vale 2 punti.
Siano A e B due variabili booleane. Quali delle seguenti espressioni è equivalente a not (A or B) and (A or (A and B))

1. (not A and not B and A) or B
2. not A or (not B and A) or (A and B)
3. not A and not B and A and B
4. Nessuna delle risposte precedenti

11) La risposta esatta vale 2 punti.
Un compito in classe inizia quando le lancette dell'orologio sono sovrapposte fra le 8 e le 9 e termina quando sono sovrapposte fra le 10 e le 11. Quanti minuti dura il compito?

1. esattamente 120
2. fra 120 e 124
3. fra 124 e 128
4. nessuna delle precedenti

12) La risposta esatta vale 2 punti.
In un allevamento di bovini bisogna selezionare il più leggero fra 4 capi, avendo a disposizione un unico tipo di bilancia che, date due coppie di bovini, indica la coppia più leggera (si assuma che non esistano due coppie di bovini dello stesso identico peso).
Nota bene: la bilancia non permette di confrontare il peso di due bovini fra loro e non fornisce il peso di una coppia di bovini.
Dire quale delle seguenti affermazioni è vera:

1. 2 pesate sono sempre sufficienti
2. 2 pesate non sono sempre sufficienti e 3 pesate sono sempre sufficienti
3. ci sono casi in cui questo tipo di bilancia non permette di trovare il bovino più leggero
4. nessuna delle precedenti

Esercizi di programmazione

1) La risposta esatta vale 1 punto.
Dopo l'esecuzione della seguente porzione di codice:

#include 

void funzione(int *a,int b) {
   int temp=*a;
   *a=b;
   b=temp;
};

main(){
   int a=2;
   int b=5;
   funzione(&a,b);
}

Quanto valgono a e b?

2) La risposta esatta vale 1 punto.
Si consideri la seguente funzione.

int funzione ( ){
   int contatore = 0;
   int sum = 0;
   while (contatore <= 4){
      contatore = contatore + 1;
      sum = sum + contatore;
   }
   return sum;
}

Quale valore restituisce la funzione?
Risposte:

1. 10
2. 15
3. 16
4. Nessuna delle risposte precedenti

3) La risposta esatta vale 2 punti.
Si consideri la seguente funzione:

void calcola(int* vett, int n) {
  int x,y;
  int i, j;
  for ( i=0; i

Assumendo che vett contenga il vettore [10,9,8,7,6,5,4,3,2,1], quali sono gli elementi di vett dopo l'esecuzione di calcola (usando 10 come secondo parametro)?

Risposte:

1. [1,2,3,4,5,6,7,8,9,10]
2. [10,9,8,7,6,5,4,3,2,1]
3. [1,3,5,7,9,2,4,6,8,10]
4. nessuna delle precedenti

4) La risposta esatta vale 3 punti.
Cosa stampa il seguente programma?

#include 

int funzione(int arr[], int dim) {
   int i = 0;
   int t=0;
   if(dim % 2==1) {
      while(i

Risposte:

1. a=10,b=1
2. a=1,b=1
3. a=10,b=11
4. a=1,b=11

5) La risposta esatta vale 3 punti.
Cosa stampa il seguente programma?

#include 
int funzione1(int arr[]) {
   int i = 1;
   while(arr[i] != -1)
       i = i * 2;
   return i;
};

int funzione2(int arr[], int f, int k) {
   int i = 0;
   int m;
   while(i <= f) {
       m = (i + f) / 2;
       if(arr[m] == k) 
          return m;
       if((arr[m] == -1) || (arr[m] > k)) 
          f = m - 1;
       else 
          i = m + 1;
   };
   return -1;
};

main() {
   int arr[10]={1,2,4,8,-1,-1,-1,-1,-1,-1};
   int f=funzione1(arr);
   int a=funzione2(arr,f,4);
   int b=funzione2(arr,f,7);
   printf ("a=%d,b=%d\\n",a,b);      
}

Risposte:

1. a=2,b=4
2. a=2,b=-1
3. a=-1,b=4
4. a=-1,b=-1

6) La risposta esatta vale 3 punti.
Data la seguente funzione che inizializza i valori di un array bi-dimensionale "matrice":

#define N 5
void inizializza( ){
  int matrice[N][N];
  int riga, colonna;
  for ( riga = 0; riga < N; riga++ ) {
    for ( colonna =  0; colonna < N; colonna++ ) {
      if ( riga == colonna ) 
          matrice[riga][colonna] = 1;
      else if ( riga + colonna == N - 1 ) 
          matrice[riga][colonna] = 1;
      else if ( riga < colonna )
          matrice[riga][colonna] = 0;
      else
          matrice[riga][colonna] = matrice[colonna][riga];
    }
  }
  for ( riga = 0; riga < N; riga++ ) {
    for ( colonna =  0; colonna < N; colonna++ ) 
      printf( "%d ", matrice[riga][colonna] );
    printf( "\\n" );
  }
}

Indicare quale tra le seguenti configurazioni vengono stampate dalla procedura "inizializza".
Risposte:

a.
1 1 1 1 1
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
1 1 1 1 1

b.
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1

c.
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0

d.
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

7) La risposta esatta vale 3 punti.
Sia data la seguente funzione ricorsiva:

int mistero(int m, int n) {
  if ( m == 0 )
    return n;
  else if ( n==0 )
    return mistero( m-1, 1 );
  else
    return mistero( mistero( m-1, n-1 ), n-1 );
}

Calcolare quale tra le seguenti risposte corrisponde ai valori restituiti invocando:

printf( "%d %d %d %dn", mistero(0,3), mistero(1,3), mistero(2,3), mistero(3,3) );

Risposte:

1. 3 1 2 0
2. 3 2 1 0
3. 0 1 2 3
4. Nessuna delle risposte precedenti

8) La risposta esatta vale 3 punti.
Si consideri la seguente funzione A.

int B(int n);

int A(int n){
  if (n > 1)
    return n*B(n+1);
  else
    return 1;
}

int B(int n){
  if (n > 1)
    return (n-1)*A(n-2);
  else
    return 1;
}

Indicare quali sono i valori restituiti dalle invocazioni
A(1), A(2), A(3), A(4), A(5).

Risposte:
a) 1, 4, 24, 192, 1920
b) 1, 4, 36, 576, 14400
c) 1, 4, 16, 256, 65536
d) nessuna delle precedenti

Risposte e riflessioni

Esercizi a carattere logico-matematico

1) Si tratta di una variante dei rubinetti che riempono una vasca [un rubinetto impiega mezz'ora, un altro un'ora, un terzo 20 minuti, quanto impiegano tutti assieme?]. La soluzione immediata la si ottiene mettendo in parallelo gli imbianchini:

     T1 * T2     4h * 2h     8h
t = --------- = --------- = ---- = 1h 20' = 80'
     T1 + T2     4h + 2h     6h

2) Mezza gallina difficilmente fa mezzo uovo, al più è buona per esser mangiata. Detto questo trattandosi di valori medi concludiamo che una gallina impiega un giorno e mezzo per fare un uovo, o - più semplicemente - in un giorno fa 2/3 di uovo.
A questo punto 9 * 9 * 2/3 = 81 * 2/3 = 54 uova tonde tonde.

3) Mario ha 4 macchine.
Infatti tutte Ferrari meno tre indica che McLaren + Williams = 3, tutte McLaren meno due indica invece che Ferrari + Williams = 2.
In conclusione 1 Ferrari, 1 Williams e 2 McLaren fanno 4 macchine.

4) Gli alunni sono 35.
Le penne vengono cosi' distribuite:

1. ad ogni alunno un numero di penne pari al numero di alunni    x2 +
2. altre due ciascuno [alunno]                                   2x +
3. ne rimangono solo cinque [penne].                              5 =
4. totale penne                                                1300

A questo punto è sufficiente risolvere l'equazione x² + 2x - 1295 = 0 la quale ha come radici x₁ = 35 e x₂ = -37. Non avendo esperienza con numeri di alunni diversi dagli interi positivi [si veda a tal proposito l'esercizio 1] utilizziamo la radice numero 1.

5) Ad attenderlo trova la madre.
La soluzione diventa piuttosto semplice se si affronta il problema con l'ordine inverso con cui viene posto, ottenendo il seguente schema logico:

                  (zia)
    madre ------ sorella ------ marito
     | |                           |
     | +----------<-<--------------+
     |          cognata
   figlio

6) Si realizzano 125 statuette
Per semplicità supponiamo che la statua raffiguri un cubo avente lato 50cm [dunque volume pari a 50 cm³]. Dividendo i tre lati per 5 si ottengono 5³ figure, ovvero 125.

7) Pitagora aveva 28 alunni.
Sommando le tre frazioni si ottiene infatti:

1   1   1    14 + 7 + 4     25
- + - + - = ------------ = ----
2   4   7        28         28

a cui vanno aggiunti i 3 alunni per ottenere l'unità.

8) E' possibile ottenere tutti i numeri compresi tra 1 e 22 con 5 elementi.
La tentazione immediata sarebbe quella di utilizzare una codifica binaria, ovvero torri di 1, 2, 4, 8 e 16 elementi [se non per il fatto che la sommatoria restituisce 31 e i pezzi a disposizione sono solo 23].
Detto questo è possibile - il luogo dell'elemento da 16 pezzi - utilizzarne un secondo da 8 [8 + 8 = 16, l'elemento mancante], con il quale ottenere tutte le possibili combinazioni comprese tra 1 e 22 [23 se si rimonta la struttura].

9) Allo scorso cenone di fine anno parteciparono 106 persone.
E' sufficiente osservare che 3, 5 e 7 sono primi tra loro [e primi anche da soli], quindi se avanza sempre un posto il numero di invitati era pari al minimo comune multiplo più 1, in questo caso mcm + 1 = 3 * 5 * 7 + 1 = 106.
Nota: anche 1 verifica le tre condizioni di dare resto 1 dividendo per 3, per 5 e per 7; purtroppo nel testo è esplicito che nel ristorante erano presenti più di una persona.

10) L'espressione fornita è sempre falsa.
Detto questo va ricercata una funzione che fornisce il medesimo risultato [FALSE indipendentemente dai valori A e B].
not A and not B and A and B = (not A and A) and (not B and B) soddisfa i requisiti richiesti.

10) Le lancette si sovrappongono ad intervalli regolari 11 volte ogni 12 ore, quindi ogni 12/11 di ora.
Pertanto il compito dura 2 * 12/11 = 2,181818... ore. Si noti che 128 minuti corrispondono a 2.1333... ore.

11)Occorrono tre pesate per stabilire la coppia più leggera di bovini.
Possono esserci casi in cui è possibile selezionare il bovino più leggero con tre pesate. Ci sono, però, casi in cui l'intersezione è vuota e non è possibile selezionare il più leggero. Si pensi al seguente caso che da gli stessi risultati nelle pesate: bovino A=7, bovino B=8, bovino C=10, bovino D=20.

Esercizi di programmazione

1) Al termine della procedura le variabili valgono a=5, b=5.
L'esercizio affronta i puntatori ed il loro utilizzo; ad un puntatore è assegnato l'indirizzo di una variabile esistente, restituito dall'operatore &, ad esempio:

int a;
int* p;
p = &a;

in questo modo p punta alla variabile a.
Analizzando la funzione funzione(int *a,int b) si intuisce facilmente che

void funzione(int *a,int b) {
   int temp=*a;                /* esegue un'operazione di estrazione,
                                  assegna a temp il valore della variabile puntata da a    */
   *a=b;                       /* esegue un'operazione di inserimento (b = 5), 
                                  assegna il valore di b alla variabile puntata da a        */
   b=temp;                     /* a questo punto temp = 5, questa istruzione e' supreflua   */
};

2) La funzione restituisce 15.
Infatti il ciclo

   while (contatore <= 4){
      contatore = contatore + 1;
      sum = sum + contatore;
   }

viene eseguito 5 volte, partendo da 1 (prima si inizializza contatore, poi si istanzia sum), dunque viene eseguita l'operazione sum = 1 + 2 + 3 + 4 + 5 = 15.

3) Dopo l'esecuzione gli elementi di vett sono [10,9,8,7,6,5,4,3,2,1]
Quando, nella chiamata di una funzione, si passa come argomento un indirizzo (sia che si tratti di una variabile puntatore oppure del risultato di un'operazione di indirizzo), per esempio (essendo p un puntatore e a una qualsiasi variabile): funz(.... p ....) oppure funz(.... &a ....)
nella definizione (e ovviamente anche nella dichiarazione) della funzione il corrispondente argomento va dichiarato come puntatore; dunque se è di tipo int si scriverà: void funz(.... int* p ....)
L'argomento è, come sempre, passato by value. In C++ è anche possibile, passarlo by reference, nel qual caso bisogna indicare entrambi gli operatori di dichiarazione * e &: void funz(.... int*& p ....)
Se il puntatore è passato by value (come nel nostro caso), nella funzione viene creata una copia del puntatore e, qualsiasi modifica venga fatta al suo valore, il corrispondente valore nel programma chiamante rimane inalterato.
Detto questo la funzione mostrata non andava nemmeno esaminata: il suo unico scopo è riempire l'intero vettore col primo elemento e far perdere tempo al candidato distratto.

4) Il programma stampa a=10,b=1.
Infatti il codice di elaborazione può essere suddiviso in due parti:

int funzione(int arr[], int dim) {
   int i=0;
   int t=0;
   if(dim % 2==1) {               /* Controllo di parita'                   */
      while(i

Premesso questo si intuisce che i vettori con numero pari di elementi vengono invertiti, mentre quelli con numero dispari vengono invertiti due volte, dunque lasciati inalterati.

5) Viene stampato a=2,b=-1.
Infatti se si analizza il codice della funzione1 si nota che restituisce un parametro fisso:

int funzione1(int arr[]) {
   int i = 1;           /* Conta a partire dal secondo dato */
   while(arr[i] != -1)  /* Termina quando trova -1 */
       i = i * 2;       /* i e' l'*indice* non il valore dell'array */
   return i;
};

Detto questo il calcolo che viene eseguito e' i = (((1 * 2) * 2) * 2) = 8.
Resta da stabilire cosa viene restituito dalle istanze:

   int a=funzione2({1,2,4,8,-1,-1,-1,-1,-1,-1},8,4);
   int b=funzione2({1,2,4,8,-1,-1,-1,-1,-1,-1},8,7);

Da notare che funzione2 restituisce un numero diverso da -1 solo se k è pari a 1, 2, 4 oppure 8. Detto questo sappiamo che b=-1 ed i calcoli vanno eseguiti solo per a.
Ricostruiamo il ciclo di calcolo:

mentre (i <= f)  /* 0 <= 8 */
  m = (i + f) / 2;  /* m = (0 + 8) / 2 = 4 */
  se (arr[m] == k)  /* 4 == -1, falso */
  se ((arr[m] == -1) || (arr[m] > k))  /* vera la prima istanza, la seconda non occorre verificarla */
    f = m - 1;      /* f = 4 - 1 = 3 */

  /* procediamo col secondo ciclo, n.b. i = 0 */

mentre (i <= f)  /* 0 <= 3 */
  m = (i + f) / 2;  /* m = (0 + 3) / 2 = 2 [integer] */
  se (arr[m] == k)  /* 4 == 4, vero */
    return m;       /* la funzione restituisce 2 */

6) Viene stampata la sequenza:

1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1

Il costrutto if che esegue il test serve per tracciare una croce di 1 in una matrice quadrata di 0:

      if ( riga == colonna )               /* diagonale dall'alto a sx verso il basso a dx  */
          matrice[riga][colonna] = 1;
      else if ( riga + colonna == N - 1 )  /* diagonale dall'alto a dx verso il basso a sx  */
          matrice[riga][colonna] = 1;
      else if ( riga < colonna )           /* restanti cella sottostanti la prima diagonale */
          matrice[riga][colonna] = 0;
      else                                 /* elementi sovrastanti                          */
          matrice[riga][colonna] = matrice[colonna][riga];

7) Viene stampata la sequenza 3 2 1 2 [nessuna delle precedenti].
La funzione ricorsiva si chiude quando m == 0, restituendo n

.

mistero(0,3) = 3 /* non viene eseguita la ricorsione */
mistero(1,3) = mistero(mistero(0,0),2) = mistero(0,2) = 2
mistero(2,3) = mistero(mistero(1,2),2) = mistero(mistero(0,1),2) = mistero(1,2) = 1
mistero(3,3) = mistero(mistero(2,2),2) = mistero(mistero(1,1),2) = mistero(0,2) = 2

8) Viene stampata la sequenza 1 4 24 384 9600.
Infatti:

1. A(1) = 1
2. A(2) = 2*B(3)=2*(2*A(1))=2*(2*1)=4
3. A(3) = 3*B(4)=3*(3*A(2))=3*(3*4)=24
4. A(4) = 4*B(5)=4*(4*A(3))=4*(4*24)=384
5. A(5) = 5*B(4)=5*(5*A(4))=5(5*384)=9600

Si tratta di una funzione ricorsiva spezzata in due parti.