Regolamento

INTERNATIONAL OLYMPIAD IN INFORMATICS- IOI 2008

Olimpiadi Italiane di Informatica

Regolamento gara nazionale 2008

Pesaro/Fano, 4 aprile 2008

Tipologia della gara

Obiettivo della gara è verificare le capacità dei partecipanti nel risolvere problemi mediante la scrittura di programmi secondo lo stile delle Olimpiadi Internazionali di Informatica (linguaggi, file input/output ecc.).

I problemi proposti, di difficoltà intermedia fra quella della selezione regionale e quella delle gare olimpiche internazionali, sono della stessa tipologia e sono formulati secondo quanto previsto dalle gare olimpiche.

Descrizione dei problemi

Ogni problema è caratterizzato dalle seguenti informazioni:

1. nome breve, che individua il problema;

2. coefficiente di difficoltà del problema (crescente con la difficoltà);

3. limiti di tempo massimo assegnato per l'esecuzione del programma (tale tempo è ampiamente maggiore di quello effettivamente necessario per la soluzione ottima);

4. descrizione del problema;

5. limiti e/o condizioni dei dati di ingresso;

6. esemplificazione attraverso un caso di prova;

7. eventuali note.

Soluzione dei problemi

I problemi devono essere risolti tramite programmi scritti in C/C++ o Pascal; le soluzioni devono funzionare correttamente con qualsiasi input che rispecchi i limiti assegnati nel testo.

I programmi devono obbligatoriamente leggere i dati in ingresso da un file di input di nome assegnato, e produrre i risultati su un file di output di nome assegnato; in particolare, questi file vanno aperti in C con le istruzioni

fr = fopen( "input.txt", "r" );

fw = fopen( "output.txt", "w" );

e in Pascal con le istruzioni

assign( fr, 'input.txt' ); reset( fr );

assign( fw, 'output.txt' ); rewrite( fw );

Il nome del file che contiene il programma deve essere esattamente il nome breve riportato nel testo del problema.

Il programma consegnato non deve interagire in alcun modo con l'utente, né stampare dati non richiesti, anche se nello sviluppo del programma è ovviamente possibile utilizzare l'input/output da tastiera/video per eseguire testing e debugging.

I partecipanti possono scegliere quali problemi risolvere e in quale ordine.

Modalità di gara

Ciascun partecipante è identificato attraverso un documento di riconoscimento e gli viene assegnata una postazione di lavoro. I partecipanti hanno a disposizione 15 minuti per prendere visione dell'ambiente e per controllarne la corretta funzionalità.

All'inizio della gara saranno distribuiti i testi dei problemi stampati su carta. I programmi dovranno essere consegnati via rete mediante un sistema automatico (detto sistema di sottoposizione) che i partecipanti avranno sperimentato nel corso della prova del giorno precedente.

La durata della gara è di 5 ore. I partecipanti possono rivolgere alla commissione di sorveglianza solo domande di chiarimento scritte alle quali verrà data, sempre per iscritto, una delle seguenti risposte: SI, NO, RISPOSTA CONTENUTA NELLA DESCRIZIONE DEL PROBLEMA (esplicitamente o implicitamente), DOMANDA NON VALIDA, NO COMMENT (non si può rispondere).

Nessun partecipante può lasciare l’aula prima di un’ora e mezzo dall’inizio della prova. I testi dei problemi possono essere portati fuori dall’aula solo dopo il termine della prova.

Durante la gara è vietato portare con sé ed usare qualsiasi strumento di comunicazione interpersonale e di memorizzazione di informazioni, nonché consultare testi, manuali o appunti di qualsiasi genere, pena la squalifica.

Ambiente di programmazione

Ogni partecipante può scegliere fra le seguenti opzioni:

· Linux (distribuzione Ubuntu completa di gcc, g++, gdb, emacs, xemacs, vi, ddd) e FreePascal (fpc);

· Windows XP Professional, con gli ambienti di sviluppo della DevC++ e Dev-Pascal (FreePascal). Gli ambienti sono installati insieme al debugger grafico della Insight. Infine, è disponibile l'editor di testi NoteTab Light.

I compilatori ufficiali della competizione sono il compilatore GNU per il C/C++ e il Free Pascal per il Pascal in ambiente Linux a 32 bit. E’ anche possibile utilizzare l’ambiente Windows: in questo caso il sistema di sottoposizione segnalerà la presenza di eventuali non conformità con l’ambiente Linux e lo studente avrà la possibilità di apportare eventuali modifiche. Si sottolinea questa decisione poiché alcuni compilatori installati sotto Windows prevedono estensioni non-standard.

Si consiglia in ogni caso di:

1. utilizzare solo variabili intere a 32 bit (LongInt e long);

2. evitare l'uso di componenti non-standard, come la crt del Turbo Pascal o i file di intestazione, come conio.h del Turbo C;

3. compilare in ogni caso con il compilatore ufficiale prima della consegna mediante il sistema di sottoposizione.

Modalità di correzione e assegnazione dei punteggi

I partecipanti devono consegnare i sorgenti mediante il sistema di sottoposizione. Viene considerata valida l'ultima sottoposizione effettuata per ciascun problema. Il nome di ogni sorgente deve essere formato dal nome breve assegnato al problema, seguito dall'estensione relativa al linguaggio usato: .c per il C, .cpp per il C++ e .pas per il Pascal.

Per la valutazione il programma sarà compilato ed eseguito su un insieme di casi di prova. Il punteggio finale consiste nella somma, pesata sul coefficiente di difficoltà del problema, dei punteggi ottenuti sui casi di prova. Lo stile di programmazione non ha alcun effetto sulla valutazione, così come il tempo necessario a risolvere ogni caso, purché rientri nei limiti previsti.

La classifica della gara sarà stilata in funzione del punteggio ottenuto dai singoli partecipanti. A parità di punteggio saranno favoriti i più giovani.

Premiazione e Probabili Olimpici 2008

In analogia a quanto accade nella gara internazionale, i primi classificati alle Olimpiadi Italiane di Informatica saranno premiati con:

MEDAGLIA D’ORO: dal primo al quinto classificato,

MEDAGLIA D’ARGENTO: dal sesto al quindicesimo classificato,

MEDAGLIA DI BRONZO: dal sedicesimo al trentacinquesimo classificato.

Il Comitato si riserva di apportare variazioni in caso di ex aequo.

I vincitori delle medaglie d’oro e d’argento saranno dichiarati Probabili Olimpici 2008 (PO2008) e saranno ammessi alle successive fasi di allenamento insieme a eventuali vincitori di medaglie di bronzo che, a insindacabile giudizio del Comitato, presentino particolari meriti.

IL COMITATO OLIMPICO

Programma

ConfCommercio, Strada delle marche, 58 - Pesaro

ISIS "S. Marta", Strada delle marche, 1 - Pesaro

Teatro della Fortuna, Piazza XX settembre - Fano

Atleti ammessi

AMMESSI OLIMPIADI ITALIANE DI INFORMATICA 2008

Come da regolamento sono ammessi alle Olimpiadi Italiane di Informatica:

1. i partecipanti agli stage di formazione della passata edizione che ancora frequentano la scuola ed hanno meno di 20 anni;
2. il primo classificato di ogni Regione con punteggio maggiore al valore medio della classifica nazionale (che è risultata di 11 punti);
3. i migliori della classifica nazionale, esclusi i primi per Regione, fino ad un massimo di 80 partecipanti complessivi.

Risultati

Le Olimpiadi Italiane 2008 si sono tenute nei giorni 3-5 aprile a Pesaro/Fano. Gli studenti vincitori delle medaglie d'oro e d'argento diventano Probabili Olimpici 2008 e risultano ammessi alla fase di allenamento.

Risultano inoltre ammessi alla formazione cinque vincitori di medaglie di bronzo scelti fra i più giovani.

I cinque studenti medagliati con l'oro alle ultime Olimpiadi Italiane di Informatica hanno vinto un premio della Banca d'Italia consistente in una borsa di studio da spendere per uno stage di due settimane che si terrà nel mese di settembre presso il laboratorio IBM di Hursley in Inghilterra.

Prove assegnate

I testi assegnati alle Olimpiadi Italiane di Informatica ed. 2008

Esercizio 1: Troupe televisive (cnn)

Difficoltà D = 2 (tempo limite 2 sec).

Descrizione del problema

Mino ha deciso di intraprendere la carriera giornalistica iniziando il suo tirocinio negli Stati Uniti, presso la prestigiosa sede newyorkese della CNN. Il suo compito è quello di pianificare gli spostamenti giornalieri di due troupe televisive a Manhattan.

Com'è noto, le strade di Manhattan formano concettualmente una griglia di righe (street) e di colonne (avenue). La zona assegnata a Mino corrisponde a una griglia quadrata MxM, le cui righe e colonne sono entrambe numerate da 1 a M.

La CNN dispone di due troupe televisive, ciascuna dotata di una potente telecamera con zoom telescopico:

• la troupe R può muoversi soltanto lungo la prima colonna per riprendere ciò che succede nelle righe (street) della griglia;

• la troupe C può muoversi soltanto lungo la prima riga per riprendere ciò che avviene nelle colonne (avenue) della griglia.

Inizialmente, entrambe le troupe sono posizionate nell'incrocio che corrisponde alla prima riga e alla prima colonna.

Il costo di spostamente di una troupe, dalla posizione I alla posizione J, è misurato come il valore assoluto della differenza di posizione, ossia |I-J| (righe o colonne, a seconda della troupe). In questo modo, una troupe che non si sposta ha correttamente costo pari a zero.

Ogni mattina Mino riceve la lista degli N eventi che andranno ripresi nella giornata, nell'ordine temporale previsto (ossia il primo evento è il primo ad accadere e così via). Ciascun evento è identificato dalle sue coordinate r c a indicare che avverrà in corrispondenza dell'incrocio tra la riga (street) r e la colonna (avenue) c della griglia assegnata a Mino.

Tale evento potrà essere ripreso dalla troupe R, posizionandosi sulla riga r, oppure dalla troupe C, posizionandosi sulla colonna c. Per la troupe scelta da Mino per riprendere quell'evento, verrà pagato un costo pari al suo eventuale spostamento dalla posizione corrente alla posizione di ripresa (come definito sopra). Infatti, non è sempre necessario spostare una troupe per riprendere due eventi successivi.

Mino deve decidere quale delle due troupe va assegnata a ciascun evento da riprendere, in modo da minimizzare il costo totale, ovvero la somma dei costi di ognuna delle due troupe. Aiutate Mino a ottenere il costo totale minimo.

Dati di input

Il file input.txt è composto da N+1 righe, dove N è un intero positivo.

La prima riga contiene due interi positivi N e M che rappresentano rispettivamente il numero N di eventi da riprendere e il lato M della griglia (ossia ci sono M righe e M colonne).

Le successive N righe contengono gli eventi da riprendere nell'ordine temporale in cui si presenteranno. La k-esima di tali righe è composta da due interi r e c separati da uno spazio per indicare che il k-esimo evento (in ordine temporale) avverrà in corrispondenza dell'incrocio tra la riga (street) r e la colonna (avenue) c.

Dati di output

Il file output.txt è composto da N righe. La k-esima di tali righe contiene un solo carattere: la lettera R (maiuscola) oppure la lettera C (maiuscola) per indicare che il k-esimo evento (in ordine temporale) va ripreso, rispettivamente, con la troupe R oppure con la troupe C. La scelta operata in questo modo deve minimizzare il costo degli spostamenti delle due troupe per riprendere tutti gli eventi nel loro ordine dato.

Assunzioni

• 1 ≤ N, M ≤ 1000

• 1 ≤ r, c ≤ M

Esempi di input/output

3 5
4 5 
3 3
2 2

R
R
C

7 6
4 2
5 2
6 2
4 3
4 4
4 5
4 6

C
C
C
R
R
R
R

Nota/e

• Nel primo esempio sopra, il costo ottenuto da RRC è 5 (=3+1+1): in questo caso, tale costo è ottimo perché lo spostamento minimo per riprendere tutti gli eventi è proprio 5. Anche RRR è una risposta corretta in quanto il suo costo è 5. Bisogna specificarne una sola in output.
• Nel secondo esempio sopra, il costo ottenuto da CCCRRRR è ottimo perché è pari a 4 (=1+0+0+3+0+0+0). Notare che la sequenza CCCCCCC produce invece un costo non ottimo, in quanto esso è pari a 5 (=1+0+0+1+1+1+1).
• Se una troupe viene spostata su una riga (o colonna), vi rimane fino all'eventuale spostamento successivo, su indicazione di Mino.
• Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio.

Esercizio 2: Giornalismo d'inchiesta (triade)

Difficoltà D = 2 (tempo limite 2 sec).

Descrizione del problema

Durante la sua attività giornalistica, Mino incappa in uno scoop. Ha infatti scoperto l'esistenza di un'associazione che fu fondata e composta da due membri che si conoscevano direttamente. Tutti gli altri membri furono successivamente reclutati se conoscevano direttamente uno o due garanti facenti già parte dell'associazione.

Mino è riuscito a ricostruire la genesi dell'attuale associazione. Numerati i suoi membri da 1 a N, ha scritto sul suo taccuino una serie di M coppie di interi. In particolare, la coppia composta da due interi (I,J) indica che I ha garantito per J o viceversa. Infatti, Mino non è riuscito a stabilire chi dei due sia entrato per primo nell'associazione: sia (I,J) che (J,I) rappresentano la stessa coppia, anche perché l'ordine di numerazione dei membri non riflette necessariamente quello dell'iscrizione all'associazione (per esempio, non è detto che i membri numero 1 e 2 siano stati i fondatori o che il membro numero N sia l'ultimo arrivato).

Lo scoop di Mino consiste nell'aver trovato le prove di azioni criminali da parte di alcune triadi all'interno dell'associazione. Una triade è composta da tre membri I, J e K dell'associazione, tali che le coppie (I,J), (I,K) e (J,K) sono tutte presenti nel taccuino di Mino (è lecito supporre che i membri di una triade si siano aiutati reciprocamente, in un qualche ordine, per entrare nell'associazione).

Per stimare il numero di controlli che Mino deve effettuare, aiutatelo a contare efficientemente quante triadi in tutto contiene l'associazione, basandovi sulle coppie trascritte nel suo taccuino e sulla modalità di reclutamento di nuovi membri: per entrare nell'associazione occorre avere conoscenza diretta di uno o due garanti che ne siano già membri.

Dati di input

Il file input.txt è composto da M+1 righe.

La prima riga contiene due interi positivi M e N separati da uno spazio: M rappresenta il numero di coppie contenute nel taccuino di Mino e N il numero di membri dell'associazione. Tali membri sono numerati da 1 a N.

Le successive M righe rappresentano le coppie nel taccuino: ciascuna riga è composta da due interi differenti I e J, separati da uno spazio, per indicare la coppia (I,J).

Dati di output

Il file output.txt è composto da una sola riga contenente un intero non negativo che rappresenta il numero totale di triadi in seno all'associazione.

Assunzioni

• 1 ≤ N ≤ 100000.
• N-1 ≤ M ≤ 2N-3.
• 1 ≤ I, J ≤ N.
• Non esistono due righe in input che rappresentano la stessa coppia. Notare che (I,J) = (J,I), per cui non è possibile trovarle entrambe in input.

Esempi di input/output

3 4
4 2
1 3
3 4

0

13 8
4 2
8 3
1 2
8 5 
6 8
4 8
7 2
6 7
2 8
7 4
8 1
5 6
3 2

5

Nota/e

• L'ordine con cui si considerano i membri per definire una triade è irrilevante: per esempio, sia 2, 4, 7 che 4, 7, 2 definiscono la stessa triade e, pertanto, essa deve essere conteggiata una volta soltanto.
• Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio.

Esercizio 3: Parole saturnine (parole)

Difficoltà D = 3 (tempo limite 1 sec).

Descrizione del problema

Come ogni giornalista moderno che si rispetti, Mino deve imparare anche qualche lingua straniera. Mino, che è un tipo bizzarro, opta per il linguaggio saturnino! Su Saturno, ogni abitante ha un proprio vocabolario, che è formato dalle parole che non contengono una certa sequenza S di M caratteri consecutivi.

Per pura curiosità, Mino vuole contare quante parole sopravvivono in un tipico vocabolario saturnino. A tal fine, considera il caso più semplice delle parole su un alfabeto binario, aventi lunghezza prefissata N ≥ M, dove S è composta da M simboli binari.

Per esempio, se S = 01, allora le parole binarie di lunghezza N = 4 che non contengono S sono 0000, 1000, 1100, 1110, 1111. Se invece S = 11, allora esse sono 0000, 1000, 0100, 0010, 1010, 0001, 1001, 0101.

Mino vuole quindi contare le parole binarie di lunghezza N che non contengono S, solo che il loro numero può esplodere al crescere di N. Allora, indicato con K tale numero, Mino vuole calcolare il valore di K modulo 2011 (in effetti, gira voce che i saturnini sappiano solo contare da 0 fino a 2010 perché tale è il loro numero di dita). Aiutate Mino a calcolare tale valore.

Dati di input

Il file input.txt è composto da due righe.

La prima riga contiene due interi positivi M e N separati da uno spazio: M rappresenta la lunghezza della sequenza binaria S da evitare e N la lunghezza delle parole binarie da contare.

La successiva riga contiene M caratteri binari '0' e '1' che rappresentano la sequenza binaria S da evitare.

Dati di output

Il file output.txt è composto da una sola riga contenente un intero, compreso tra 0 e 2010, che rappresenta il valore K modulo 2011, dove K è il numero di parole binarie di lunghezza N che non contengono S.

Assunzioni

• 1 ≤ N, M ≤ 1000.
• Per almeno metà dei casi di prova, su cui saranno valutati i programmi, vale 1 ≤ M ≤ 16.

Esempi di input/output

2 4
01

5

2 4
11

8

2 15
11

1597

2 16
11

573

Nota/e

• Ricordiamo che a modulo b = c se e solo se c è il resto della divisione intera tra a e b. L'operazione di modulo in linguaggio C si effettua con il simbolo di percentuale, in linguaggio Pascal con l'operatore mod.
• E' importante usare sempre il modulo dopo un'operazione aritmetica di conteggio perché i valori intermedi generati possono richiedere più di 32 bit. Poiché il risultato è K modulo 2011, suggeriamo di sfruttare il fatto che (A + B + C) modulo 2011 = ((A + B) modulo 2011) + C) modulo 2011. Stessa cosa per le altre operazioni aritmetiche. In questo modo, i risultati intermedi sono sempre modulo 2011 e possono essere mantenuti in una normale variabile intera a 32 bit.
• Se usate la piattaforma di sviluppo software basata sul compilatore Turbo Pascal e sul sistema operativo Windows, fare attenzione: i vostri programmi potrebbero essere valutati in una piattaforma diversa dalla vostra, e la garanzia di uniformità di comportamenti si ha soltanto se utilizzate sempre il tipo LongInt al posto del tipo Integer (quest'ultimo permette di rappresentare gli interi nell'intervallo [-32768...32767] mentre LongInt ne permette la rappresentazione in [-2147483648...2147483647]).
• Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio.