Problemi tradotti e risolti

In questa pagina potete trovare una parte dei problemi olimpici degli ultimi dieci anni, tradotti, risolti e commentati in italiano, e i problemi delle selezioni nazionali italiane. A volte le soluzioni sono in C, a volte in Pascal. In ogni caso sono commentate in dettaglio. In alcuni casi è presente solo la traduzione.

Se siete curiosi di sapere chi risolve i problemi, c'è una pagina degli autori che ve lo spiega.

Il livello di difficoltà dei problemi è salito rapidamente di anno in anno. Se volete allenarvi, o anche solo verificare il vostro livello di comprensione dei problemi, vi consigliamo di partire con problemi dei primi anni (per esempio, del 1994) e poi continuare con gli anni successivi.

Alcune note sui programmi

  1. Alcune delle soluzioni proposte leggono da standard input e scrivono su standard output. Altre leggono da/scrivono su file con nomi diversi da quelli indicati nel testo del problema.
  2. I file Gen... (quando presenti) servono per la generazione automatica o semiautomatica degli input.
  3. I file Spiega... (quando presenti) ripetono il testo del problema ma contengono alla fine una sintetica spiegazione delle tecniche risolutive adottate.
  4. Potete liberamente scaricare, leggere o modificare i programmi secondo i diritti dati dalla GNU General Public License (per i meno avvezzi all'inglese, c'è anche una traduzione non ufficiale).

Il driver di correzione

Per semplificare la correzione dei problemi, abbiamo realizzato un driver che corregge automaticamente (su un sistema che implementa POSIX.2, per esempio Linux) un programma provandolo su diversi input. Potete scaricarlo e provare a utilizzarlo (le istruzioni sono contenute all'inizio del sorgente).

Attenzione: a seconda dell'ambiente in cui sono stati generati, i file di input e output possono utilizzare solo un LF (ASCII 10) o un CR (ASCII 13) e un LF come fine riga (Unix e MS-DOS, rispettivamente). Ricordatevi di convertire i terminatori di linea a quelli utilizzati dal vostro sistema operativo.

Arbitro per giochi

Alcuni problemi in olimpiadi recenti chiedono di scrivere un programma che gareggi in un gioco combinatoriale. Questi programmi leggono da standard input la configurazione del gioco, e quindi, a turno, scrivono le loro mosse su standard output o leggono le mosse dell'avversario da standard input. Eseguire questi programmi a mano è oneroso se non impossibile: abbiamo quindi sviluppato referee (arbitro), una utility che connette due programmi e li fa giocare senza intervento umano. Come il driver di correzione, referee funziona su qualunque sistema che implementa POSIX.2.