Le prove assegnate

Home
Su

Codice (coefficiente di difficolta’ D=3)

Il problema

Giovanni ha deciso che il normale modo di scrivere i numeri naturali (l’insieme dei numeri  naturali comprende 0 e tutti i numeri interi positivi) non è adatto ai computer. In particolare, lo disturba il fatto che per leggere numeri da un file occorra un separatore. Per esempio, se un file contiene

2
1
12

è facile capire quali sono i numeri contenuti, dato che sono separati da un fine riga. Se lo stesso file fosse scritto però come segue  

2112

 non si potrebbe distinguere dal file che contiene il solo numero 2112.

 Per risolvere il problema una volta per tutte, Giovanni decide di inventare un formato di scrittura dei numeri che non necessita di separatori.

Il formato funziona così: se vogliamo scrivere un numero x, per prima cosa calcoliamo il numero n di cifre che occorrono per scrivere x. Per esempio, se x è 41012 allora n è uguale a 5.

La rappresentazione di x, a questo punto, si ottiene come segue: scriviamo tanti zeri quante sono le cifre di n seguiti da un uno, quindi scriviamo n, e per finire scriviamo x. Per esempio, il numero 41012 verrà rappresentato da 01541012, mentre 1234567890 verrà rappresentato da 001101234567890 e zero verrà rappresentato da 0110.

Giovanni si sente molto furbo, perché in questo modo può concatenare liberamente rappresentazioni di numeri e leggerle senza bisogno di separatori: per esempio, leggendo

 015410120011012345678900110

 si vede che ci deve essere un numero la cui lunghezza è specificata da una cifra (c'è uno zero seguito da un uno). Questa lunghezza è cinque: i cinque numeri che seguono sono 41201, e quindi questo è il primo numero. Il numero successivo deve avere una lunghezza espressa da due cifre (perché ci sono due zeri seguiti da un uno). La lunghezza sarà quindi 10, e il numero 1234567890. Infine, l'ultimo numero deve avere una lunghezza espressa da una singola cifra (perché comincia con 01); la lunghezza risulta essere uno, l'unica cifra che compare è 0, e quindi il numero è zero.

Giovanni non ha avuto difficoltà a scrivere un programma che legge una serie di numeri e li scrive senza separatori nella nuova forma. Ha però qualche problema a rileggere i numeri che ha scritto, e voi dovete aiutarlo.

 Dati in input

Il file di input contiene una sequenza di cifre terminate da un asterisco (*).

Dati in output

Il file di output contiene un intero su ogni riga. La prima riga deve contenere, nella normale forma decimale, il primo intero rappresentato nell'input, la seconda riga il secondo e così via.

Assunzioni

I numeri sono rappresentati senza segno

Nessun intero è più grande di 101000.

Esempi di input e output

Esempio 1
File input.txt

0142112*

File output.txt

2112

Esempio 2
File input.txt

01541012001101234567890011000112234234234234*

File output.txt

41012

1234567890

0

234234234234


Giostre (coefficiente di difficolta' D=2)

Il problema

In una fiera di paese sono installate due giostre. La prima giostra (quella di sinistra in figura) è costituita da A≥20 vagoni e gira in senso antiorario, la seconda giostra (quella di destra) è costituita da B≥20 vagoni e gira in senso orario.

Le due giostre sono così vicine fra loro che in ogni istante c'è un vagone della prima giostra che sfiora un vagone della seconda giostra (quelli colorati di nero in figura), tanto che un ragazzo che stia su uno dei due può saltare sull'altro. Le velocità delle giostre sono regolate in modo tale che, all'istante successivo, i due vagoni adiacenti saranno i due successivi sulle due giostre (quelli colorati di grigio in figura).

Quindi, un ragazzo che salga su un vagone della prima giostra può passare su un altro vagone della stessa giostra saltando prima sulla seconda e poi di nuovo sulla prima.

Ora, assumete di conoscere i valori di A e B, e supponete che un ragazzo salga su un vagone della prima giostra:

  1. Dovete determinare quanti diversi vagoni della prima giostra il ragazzo può visitare.
  2. Inoltre, dovete determinare il numero minimo B'≥20 di vagoni che la seconda giostra deve avere affinché il ragazzo possa visitare tutti i vagoni della prima giostra.

File di input

Il file di input, di nome input.txt, è costituito da una singola riga contenente due interi separati da uno spazio: i due interi rappresentano rispettivamente il numero A di vagoni della prima giostra e il numero B di vagoni della seconda giostra.

File di output

Il file di output, di nome output.txt, è costituito da una singola riga, contenente due numeri interi, separati da uno spazio. Il primo è il numero di vagoni della prima giostra che il ragazzo può visitare. Il secondo è il numero minimo B'≥20 di vagoni che la seconda giostra deve avere affinché il ragazzo possa visitare tutti i vagoni della prima giostra.

Assunzioni

Si fanno le seguenti assunzioni:

  • 20 ≤= A,B ≤= 32000;
  • il programma deve terminare la propria esecuzione in meno di 0.1 secondi;
  • nelle due giostre non ci sono altri passeggeri, a parte il ragazzo;
  • l'unica possibilità di movimento concessa è quella di saltare da una giostra all'altra quando due vagoni sono adiacenti; in particolare, il ragazzo non può spostarsi direttamente da un vagone all'altro della stessa giostra;
  • il file di input non contiene altri caratteri oltre a quelli indicati nel testo;
  • il file di output non deve contenere altri caratteri oltre a quelli indicati nel testo; inoltre, il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output;
  • i file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno aperti in C con un'istruzione tipo
·                                       fr = fopen( "input.txt", "r" );
·                                       fw = fopen( "output.txt", "w" );

         

e in Pascal con un'istruzione tipo

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

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

         

Esempio di input/output

File input.txt

24 22

File output.txt

12 23

Selezioni Regionali IOI 2003

Enrica (coefficiente di difficolta' D=3)

Il problema

Enrica la formica si muove seguendo le linee di una griglia. Ogni punto della griglia è identificato da una coppia di interi non negativi (x,y), dove il primo indica la coordinata X e il secondo indica la coordinata Y. Il punto (0,0) è quello in basso a sinistra (vedi figura).

Enrica inizia il suo cammino da un certo punto di coordinate (0,Yin) e normalmente si sposta in orizzontale, da sinistra verso destra. Lungo il suo percorso, però, può trovare degli ostacoli. Gli ostacoli sono costituiti da segmenti verticali che si trovano sparsi sul percorso.

Quando Enrica arriva a un ostacolo, inizia a spostarsi verticalmente lungo l'ostacolo verso l'estremità più vicina dell'ostacolo stesso; se le estremità sono egualmente distanti, si muove sempre verso l'alto. Raggiunta l'estremità dell'ostacolo, Enrica riprende a camminare orizzontalmente verso destra.

Una linea verticale delimita il campo da gioco: quando Enrica arriva alla linea verticale, si ferma. Dovete trovare quanto è lungo il percorso compiuto da Enrica, e a quale altezza (coordinata Y) si trova Enrica alla fine del percorso.

Dati in input

Il file di input, di nome input.txt, è costituito da varie righe:

  • sulla prima riga si trovano due numeri interi (separati da uno spazio) Yin e Xfin: il primo indica da quale coordinata Y parte Enrica, mentre il secondo indica a quale coordinata X si trova la linea verticale che delimita il campo di gioco; in altre parole, Enrica inizierà il suo cammino dal punto (0,Yin) e si fermerà in un qualche punto della forma (Xfin,Yfin) (dove Yfin è uno dei valori da determinare);
  • sulla seconda riga si trova il numero intero N che rappresenta quanti sono gli ostacoli;
  • su ciascuna delle successive N righe si trova la descrizione di un ostacolo; l'i-esimo ostacolo è descritto da tre interi Xi Yi Y'i, separati fra loro da uno spazio; Xi è la coordinata X a cui si trova l'ostacolo, mentre Yi e Y'i sono le due coordinate Y delle sue estremità.

Dati in output

Il file di output, di nome output.txt, è costituito da una singola riga, contenente due numeri interi, separati da uno spazio. Il primo numero intero è la lunghezza L del percorso compiuto da Enrica; il secondo numero intero Yfin è la coordinata Y a cui si trova Enrica alla fine del suo percorso.

Assunzioni

Si fanno le seguenti assunzioni:

  • 0 < Yin;
  • 0 < X1 < X2 < ... < XN < Xfin;
  • per ogni i vale che 0 < Yi < Y'i;
  • 0 ≤ N ≤ 1000;
  • nessuna delle variabili coinvolte in input o output avrà valore maggiore di 32000;
  • il programma deve terminare la propria esecuzione in meno di 0.1 secondi;
  • il file di input non contiene altri caratteri oltre a quelli indicati nel testo;
  • il file di output non deve contenere altri caratteri oltre a quelli indicati nel testo; inoltre, il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output;
  • i file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno 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 );

         

Esempio di input/output

Questo esempio corrisponde a quello mostrato in figura.

File input.txt

7 15

5

3 3 8

5 9 11

6 6 10

9 2 5

11 9 12

     

File output.txt

19 9
   

 

E' disponibile l'archivio contenente le tre prove.