Category Archives: OIS

Olimpiadi Italiane a Squadre

Numeri di Figonacci

Dopo l’ultimo seminario di teoria dei numeri, Giorgio è rimasto affascinato dallo studio della sequenza dei numeri di Fibonacci.
Pertanto, per non essere da meno, introduce una nuova sequenza di numeri secondo lui ancora più interessante: i numeri di Figonacci.
Come per i loro quasi-omonimi, l’(n+1)-esimo numero di Figonacci Gn+1 si calcola a partire dai precedenti (eccezion fatta per i primi due numeri di Figonacci, che sono valori fissati a G0=−1 e G1=0).

La regola che stabilisce il valore di GN+1, tuttavia, è diversa da quella dei numeri di Fibonacci: GN+1 è pari alla somma di tutte le possibili differenze tra il numero di Figonacci immediatamente precedente e quelli ancora prima.

In formule:

figonacci

I primi numeri che si ottengono da questa sequenza sono quindi −1, 0, 1, 3, 9, . . . ed è facile vedere che crescono molto rapidamente.
Ma questo non è un problema per Giorgio, che è interessato ad usarli per problemi di teoria dei numeri, e a cui quindi interessa soltanto il valore modulo M di questi numeri.

Aiuta la sua ricerca calcolando il valore dell’N-esimo numero di Figonacci GN modulo M.

Dati di input

Il file input.txt è composto da un’unica riga contenente i due numeri interi N ed M.

Dati di output

Il file output.txt è composto da un’unica riga contenente un unico intero, la risposta a questo problema.

Assunzioni

  • 2 ≤ N ≤ 1000000
  • 2 ≤ M ≤ 40 000.

Esempi di input/output

input.txt output.txt
3 10 3
4 3 0
5 9 6

Spiegazione

  • Nel primo caso di esempio, G3=3 che modulo 10 resta 3.
  • Nel secondo caso di esempio, G4=9 che modulo 3 fa 0.
  • Nel terzo caso di esempio, G5=33 che modulo 9 fa 6.

Note

L’operazione di modulo si calcola con l’operatore % in C/C++.
Notare che può dare risultati non corretti se l’argomento è negativo (il che può succedere per diversi motivi).
Un modo per risolvere questo problema è usare il seguente codice:

(GN % M + M) % M

L’operazione di modulo, inoltre, ha le seguenti proprietà (molto utili per evitare integer overflow quando si vogliono calcolare numeri molto grandi):

  • (A+B) mod M = (A mod M + B mod M) mod M
  • (A·B) mod M = (A mod M · B mod M) mod M

Espressione di parentesi

Olimpiadi Italiane a Squadre

Giorgio ha scritto un programma contenente una serie di espressioni molto elaborate, formate ciascuna da un gran numero di parentesi di tutti i tipi, e cioè:

  • angolate: ’<’ e ’>
  • tonde: ’(’ e ’)
  • quadrate: ’[’ e ’]
  • graffe: ’{’ e ’}

Purtroppo, quando ha provato ad eseguirlo, il compilatore gli ha detto che c’è un errore senza nemmeno dirgli in quale espressione si trova!
Aiutalo controllando quali espressioni sono ben formate e quali no.

Dati di input

Il file input.txt è composto da due righe.

  • La prima riga contiene l’unico intero N.
  • La seconda riga contiene la stringa E.

Dati di output

Il file output.txt è composto da un’unica riga contenente un unica parola, la risposta a questo problema.

Assunzioni

  • 1 ≤ N ≤ 10000
  • Ei è uno tra i caratteri ’{[(<>)]}’.

Esempi di input/output

input.txt output.txt
4
([)]
malformata
5
<({})
malformata
12
()([]{(<>)})
corretta
20
{(<><>){{()[<>]<>}}}
corretta

Utilizzo una seconda stringa


Utilizzo una pila (stack)

cAPS lOCK

Gabriele ha scritto un messaggio per Giorgio, ma arrivato alla fine si è accorto con orrore che tutto il testo ha le minuscole e le maiuscole invertite per colpa del caps lock attivo.
Piuttosto che riscrivere tutto daccapo, Gabriele decide di chiederti di creare un programma che, preso il testo del messaggio, converta le maiuscole in minuscole e viceversa.
Aiuta Gabriele ad aggiustare il messaggio!

Dati di input

Il file input.txt è composto da due righe.

  1. La prima riga contiene l’unico intero N, il numero di caratteri del testo.
  2. La seconda riga contiene il testo del messaggio.

Dati di output

Il file output.txt è composto da un’unica riga contenente il testo corretto.

Esempi di input/output

input.txt output.txt
41
eHI, TUTTO BENE? tI VA UNA PIZZA STASERA?
Ehi, tutto bene? Ti va una pizza stasera?
23
nA nA nA nA nA bATmAN!!
Na Na Na Na Na BatMan!!

Calcolatrice d’epoca

Olimpiadi Italiane a Squadre

La calcolatrice che Giorgio conserva gelosamente da quando faceva le elementari si è rotta, e ora il suo schermo LCD vecchio stile penzola appeso ai tasti dal solo filo di alimentazione.
Nonostante questo, funziona ancora perfettamente come un tempo e quindi Giorgio non ha intenzione di smettere di utilizzarla.
Con la sua affezionata calcolatrice, Giorgio ha appena fatto dei lunghi e complessi calcoli i cui risultati potrebbero portare alla soluzione di numerose congetture in innumerevoli campi della matematica, e ne ha trascritto i risultati su un foglio.
Tuttavia solo dopo si è accorto che, per via del danno descritto sopra, non è in grado di capire l’orientamento giusto dello schermo e quindi in alcuni casi potrebbe aver trascritto il risultato sbagliato (e cioè come si leggerebbe ruotando lo schermo della calcolatrice di 180°).
Da un’approssimazione a stima che si è fatto, gli sembra che i risultati dovrebbero essere numeri abbastanza piccoli.
Pertanto, dato un numero N, vuole scrivere un programma che calcoli il corrispondente numero M ruotato di 180°, e se questo è effettivamente un numero sensato scelga il minore tra i due.

Dati di input

Il file input.txt è composto da un’unica riga contenente l’unico intero N.

Dati di output

Il file output.txt è composto da un’unica riga contenente un unico intero, la risposta a questo problema.

Esempi di input/output

input.txt output.txt
14 14
12650 12650
806129 621908

Nel primo caso di esempio, il numero 14 ruotato non genera un numero sensato, per via della presenza della cifra 4.

Nel secondo caso di esempio, il numero 12650 ruotato genera il numero 05921 che non è da considerarsi sensato, per via della presenza della cifra 0 come prima cifra.

Nel terzo caso di esempio, il numero 806129 ruotato genera il numero 621908 che è sensato e minore del precedente.


Congettura di Lollatz

Olimpiadi Italiane a Squadre

Da qualche tempo, Giorgio si è interessato alla congettura di Lollatz.
Questa congettura afferma che, dato un quadrato perfetto N, ripetendo i seguenti due passaggi:

  • moltiplichi il numero per la sua cifra delle unità−1
  • dividi per due, arrotondando per difetto

prima o poi si arriva a un multiplo di 10.

Giorgio, tuttavia, non riesce ad interpretare i passaggi della dimostrazione del dottor Lollatz, che sembra essere composta unicamente da abbreviazioni poco leggibili, e quindi si fida poco di questo risultato.
Aiutalo a dirimere i suoi dubbi scrivendo un programma che verifichi questa congettura!

Dati in input

Il file input.txt è composto da un’unica riga contenente l’unico intero N.

Dati in output

Il file output.txt è composto da un’unica riga contenente un unico intero, la risposta a questo problema.

Assunzioni

  • 1 ≤ N ≤ 1000000.

Esempi di input/output

input.txt output.txt
4 30
100 100

Se N è un quadrato perfetto l’ultimo cifra è 0, 1, 4, 5, 6 oppure 9 e quindi…