Lo scorso martedì si sono svolte le Olimpiadi Italiane d'Informatica, o meglio, le selezioni territoriali.
Competizione aperta a tutti gli studenti delle superiori che frequentano l'anno 1, 2, 3 o 4.
Come ogni anno, i problemi da risolvere erano 3: uno generale, uno risolvibile con la programmazione dinamica e un grafo.
LSWF (d = 1)
Avendo un numero N, tradurlo in una sequenza di 1 e 0 tenendo come base i numeri della successione di Fibonacci. La somma degli 1 della sequenza, corrispondenti quindi al numero della successione di Fibonacci, devono risultare N. Ecco un esempio:
Come si arriva al risultato che 19 è 1000101 (i successivi 0 all'ultimo 1 sono irrilevanti)?
Ci sono svariati metodi: 1 + 2 + 3 + 13 o 1 + 2 + 3 + 5 + 8 o 1 + 5 + 13.
Ma qual è quello corretto? Be', io ho optato per l'ultimo per un motivo abbastanza semplice: andando per greedy, faccio meno confronti se dovessi avere un numero molto grande, esempio:
N = 10947
Tutti numeri della successione < N = 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
Di conseguenza, se partiamo dal presupposto che fib[0], che ha come valore 1, è sempre preso, l'esecuzione si ferma al primo numero in ordine decrescente. Creiamo quindi una funzione che calcoli tutti i numeri sella successione di Fibonacci < N e poi iniziamo la ricerca:
Il codice C++:
INPUT:
19
OUTPUT:
100010
Scommesse (d = 2)
Ho in input un numero N e N-1 numeri nella riga successiva.
N è un numero compreso tra 1 e 10000 ed è dispari. La riga seguente sono delle carte con dei numeri casuali che non si ripetono da 0 a N-1. Ad ogni iterazione la coppia di carte che ha come somma un numero dispari, viene tolta. Vi si deve stampare quante e quali carte restano sul tavolo se si procede con una sequenza di mosse. Poniamo ad esempio N = 11 e la sequenza 1 0 2 6 4 5 3 9 8 10 7: possiamo vedere che a seconda da dove iniziamo ad esaminare le carte, ne escono due: 8 e 2.
Se iniziamo da 1:
Se iniziamo da 9:
Il codice C++:
INPUT:
11
1 0 2 6 4 5 3 9 8 10 7
OUTPUT:
2
8 2
Tecla (d = 2)
Non sono arrivato a risolvere questo problema, ma confrontandomi con gli altri partecipanti, pare essere un grafo di tipo BFS.
Se qualcuno ha partecipato e vuole condividere le proprie soluzioni o miglioramenti ai miei, faccia pure
Competizione aperta a tutti gli studenti delle superiori che frequentano l'anno 1, 2, 3 o 4.
Come ogni anno, i problemi da risolvere erano 3: uno generale, uno risolvibile con la programmazione dinamica e un grafo.
LSWF (d = 1)
Avendo un numero N, tradurlo in una sequenza di 1 e 0 tenendo come base i numeri della successione di Fibonacci. La somma degli 1 della sequenza, corrispondenti quindi al numero della successione di Fibonacci, devono risultare N. Ecco un esempio:
Come si arriva al risultato che 19 è 1000101 (i successivi 0 all'ultimo 1 sono irrilevanti)?
Ci sono svariati metodi: 1 + 2 + 3 + 13 o 1 + 2 + 3 + 5 + 8 o 1 + 5 + 13.
Ma qual è quello corretto? Be', io ho optato per l'ultimo per un motivo abbastanza semplice: andando per greedy, faccio meno confronti se dovessi avere un numero molto grande, esempio:
N = 10947
Tutti numeri della successione < N = 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
Di conseguenza, se partiamo dal presupposto che fib[0], che ha come valore 1, è sempre preso, l'esecuzione si ferma al primo numero in ordine decrescente. Creiamo quindi una funzione che calcoli tutti i numeri sella successione di Fibonacci < N e poi iniziamo la ricerca:
Il codice C++:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
19
OUTPUT:
100010
Scommesse (d = 2)
Ho in input un numero N e N-1 numeri nella riga successiva.
N è un numero compreso tra 1 e 10000 ed è dispari. La riga seguente sono delle carte con dei numeri casuali che non si ripetono da 0 a N-1. Ad ogni iterazione la coppia di carte che ha come somma un numero dispari, viene tolta. Vi si deve stampare quante e quali carte restano sul tavolo se si procede con una sequenza di mosse. Poniamo ad esempio N = 11 e la sequenza 1 0 2 6 4 5 3 9 8 10 7: possiamo vedere che a seconda da dove iniziamo ad esaminare le carte, ne escono due: 8 e 2.
Se iniziamo da 1:
Se iniziamo da 9:
Il codice C++:
Codice:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
11
1 0 2 6 4 5 3 9 8 10 7
OUTPUT:
2
8 2
Tecla (d = 2)
Non sono arrivato a risolvere questo problema, ma confrontandomi con gli altri partecipanti, pare essere un grafo di tipo BFS.
Se qualcuno ha partecipato e vuole condividere le proprie soluzioni o miglioramenti ai miei, faccia pure
E NIENTE, SALUTA ANDONIO!!
Ultima modifica:
. Non è una coincidenza che la maggior parte degli studenti che passano alle nazionali sono del 4° anno.