Category Archives: Fase territoriale

Missioni segrete

Il Commissario Basettoni ha presentato a Topolino le missioni che egli dovrà svolgere segretamente nel corso dell’anno.

Per ogni missione, oltre al luogo da raggiungere, Basettoni ne indica la durata in giorni e la data massima entro cui deve essere completata.
In altri termini, la missione può iniziare in qualunque giorno dell’anno ma deve durare esattamente il numero di giorni indicato e terminare non oltre la data di scadenza.

Topolino, presa la lista delle missioni ricevuta da Basettoni, ordina tali missioni in base alla loro data di scadenza.
Quindi, numera i giorni dell’anno da 1 a 365 (non esistono anni bisestili a Topolinia) e trasforma le date di scadenza in numeri secondo tale numerazione.

Per esempio, se una missione dura 15 giorni e deve essere svolta entro il 18 febbraio, Topolino la vede semplicemente come una coppia di interi 15 49 (in quanto il 18 febbraio è il quarantanovesimo giorno dell’anno).

Poiché può effettuare una sola missione alla volta, Topolino non sarà in grado di svolgerle tutte, pur iniziando una missione il giorno immediatamente successivo a quello in cui termina la precedente.
Vuole perciò sapere il numero massimo di missioni che è in grado di eseguire rispettando i vincoli sulla loro durata e scadenza.
Supponendo che Topolino già fornisca le coppie di interi ordinate per scadenza (il secondo membro delle coppie), aiutatelo a calcolare il massimo numero di missioni che può svolgere.

Per esempio, se ci sono quattro missioni, una di tre giorni da terminare entro il 5 gennaio, una di quattro giorni entro l’8 gennaio, una di tre giorni entro il 9 gennaio e una di 6 giorni entro il 12 gennaio, Topolino vi fornisce la lista di quattro coppie 3 5, 4 8, 3 9 e 6 12.
Il numero massimo di missioni che può svolgere è pari a tre, ossia le missioni corrispondenti alle coppie 3 5, 3 9 e 6 12:

  • la prima missione inizia il primo di gennaio e termina il 3 gennaio;
  • la seconda inizia il 4 gennaio e termina il 6 gennaio;
  • la terza inizia il 7 gennaio e termina il 12 gennaio.

Notare che, scegliendo la missione corrispondente alla coppia 4 8, Topolino può svolgere al più due missioni.

Dati di input

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

  • La prima riga contiene un intero positivo che rappresenta il numero N di missioni presentate da Basettoni a Topolino.
  • Le successive N righe rappresentano durata e scadenza delle missioni: ciascuna riga è composta da due interi d e s separati da uno spazio, a rappresentare che la corrispondente missione dura d giorni e deve essere completata entro l’s-esimo giorno dell’anno.

 

Dati di output

Il file output.txt è composto da una sola riga contenente un intero che rappresenta il massimo numero di missioni che Topolino può svolgere rispettando i vincoli su durata e scadenza.

Assunzioni

  • 1 ≤ N ≤ 100
  • 1 ≤ d, s ≤ 365
  • d ≤ s.

 

Esempio

input.txt output.txt
4
3 5
4 8
3 9
6 12
3

Le pesate di Bilancino

Bilancino è un bambino con una passione maniacale, quella di mettere gli oggetti in ordine crescente di peso.
I suoi genitori posseggono un’antica e rara bilancia con due bracci uguali: posti due oggetti, uno per braccio, la bilancia permette di stabilire quale dei due oggetti è più pesante, ma non permette di trovarne il peso assoluto.

Oggi Bilancino vuole mettere in ordine crescente di peso N oggetti e, a tale scopo, ha già effettuato una serie di M pesate, trascrivendone i risultati.
Infatti, numerati tali oggetti da 1 a N, egli ha pesato M coppie di oggetti distinti x e y, dove 1 <= x, y <= N, scrivendo i due interi x e yin quest’ordine su una riga per indicare che x è più leggero di y e, invece, scrivendo y e x in quest’ordine per indicare che y è più leggero di x.
Da notare che non esistono due oggetti con lo stesso peso (siano essi stati pesati o meno da Bilancino) e che la stessa coppia di oggetti non può essere pesata più di una volta.

Esaminate le M pesate finora eseguite da Bilancino e aiutatelo a decidere quale, tra le seguenti alternative, consente di stabilire l’ordine crescente di peso tra gli N oggetti:

  • le M pesate sono sufficienti;
  • è necessaria un’ulteriore pesata;
  • sono necessarie due o più pesate.

 

Dati di input

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

  • La prima riga contiene due interi positivi separati da uno spazio: il primo intero rappresenta il numero N di oggetti da ordinare in base al peso mentre il secondo intero rappresenta il numero M di pesate effettuate da Bilancino.
  • Le successive M righe contengono coppie di interi positivi: la j-esima di tali righe è composta da due interi distinti a e b separati da uno spazio, a rappresentare la j-esima pesata effettuata da Bilancino, in cui egli scopre che l’oggetto a è più leggero dell’oggetto b (dove 1 <= j <= M e 1 <= a, b <= N).
  • Da notare che la stessa pesata non può apparire in più di una riga.

 

Dati di output

Il file output.txt è composto da una riga contenente un solo intero come dalla seguente tabella.

  • 0: nessuna ulteriore pesata è necessaria per stabilire l’ordine crescente di tutti gli oggetti.
  • 1: serve e basta un’ulteriore pesata per stabilire l’ordine crescente di tutti gli oggetti.
  • 2: due o più pesate sono ulteriormente necessarie per stabilire l’ordine crescente di tutti gli oggetti.

 

Assunzioni

  • 1 < N < 100
  • 1 <= M <= N(N-1)/2
  • I dati in input.txt garantiscono sempre che esiste almeno un ordinamento degli oggetti compatibile con tutte le pesate trascritte da Bilancino.

 

Esempi

input.txt output.txt
1 3 2
1 2
3 1
0
2 4 4
2 3
1 4
1 3
2 1
1
3 4 3
2 3
1 4
2 1
2

La poltrona di Korrot

Il robot Korrot deve trovare una poltrona su cui sedersi.
Korrot vive in una scacchiera NxM, con le righe numerate da 1 a N (dal basso verso l’alto) e le colonne numerate da 1 a M (da sinistra a destra).
Parte dalla riga più in basso (la riga 1) e deve raggiungere la poltrona sulla riga più in alto (la riga N).
Korrot può spostarsi in tutte le direzioni tranne che in diagonale.
La figura sottostante illustra una possibile disposizione iniziale di Korrot (K) e della poltrona (P) in una scacchiera con N=5 e M=6.ter_2005_korrot1

Figura 1.
Percorso: AAAAS (poltrona)

Korrot ha un modo particolare di raggiungere l’ambita poltrona.
Parte da una delle caselle sulla riga 1 e procede verso l’alto fino alla riga N, poi prosegue il suo percorso verso destra o verso sinistra in direzione della poltrona.
Nell’esempio mostrato, il percorso scelto da Korrot prevede 4 passi verso l’alto e uno verso sinistra ed è rappresentato dalle lettereAAAAS.

Purtroppo, Korrott ha una nemica di nome Maggie che dissemina la scacchiera di scomodi ostacoli.
Se Korrot si trova di fronte a un ostacolo, deve aggirarlo.
Nell’affrontare gli ostacoli bisogna ricordare che, per come è programmato, Korrot prova sempre ad andare verso l’alto per raggiungere l’ultima riga e poi, muovendosi su questa (a destra o sinistra), prova a raggiungere la poltrona.
Ecco quindi come si comporta Korrot:

  • Se incontra un ostacolo mentre cerca di andare verso l’alto, Korrot devia a destra.
  • Se però si trova nella colonna più a destra (la colonna M) devia a sinistra per non cadere dalla scacchiera.
  • In entrambi i casi tenta di risalire non appena può.
  • Se Korrot è già arrivato alla riga più in alto, evita gli ostacoli con una mossa verso il basso (spostandosi quindi temporaneamente sulla riga N-1) e rientra sulla riga N appena possibile (eventualmente per sedersi sull’ambita poltrona).
  • Se Korrot trova un ostacolo nella casella dove vorrebbe deviare, va in uno stato di confusione totale e rinuncia per sempre all’amata poltrona.
  • Inoltre Korrot rinuncia alla poltrona anche se è costretto a ritornare sui suoi passi.

Ecco alcuni esempi del comportamento di Korrot (gli ostacoli sono rappresentati dal simbolo O, la casella finale presenta il simbolo sottolineato).

ter_2005_korrot2

Figura 2.
Percorso: ADAADDAADA (poltrona)

ter_2005_korrot3
Figura 3.
Percorso: DAA (confusione: è programmato per andare a destra ma a destra trova un ostacolo)

ter_2005_korrot4

Figura 4.
Percorso: SAAD (confusione: costretto a tornare sui propri passi)

ter_2005_korrot5

Figura 5.
Percorso: AAAASBSSSAS (poltrona)

ter_2005_korrot6

Figura 6.
Percorso: AAAASBSS (confusione: non è sull’ultima riga e quindi non può andare in basso)

Scrivere un programma che riproduca il comportamento di Korrot stampandone il corrispondente percorso.

Dati di input

Il file input.txt contiene sulla prima riga in ingresso i due interi positivi N (il numero delle righe nella scacchiera) e M (il numero delle colonne nella scacchiera), separati da uno spazio.
La seconda riga del file contiene le posizioni iniziali, rispettivamente di Korrot e della poltrona, rappresentate ognuna da un solo intero positivo (soltanto l’indice di colonna nella scacchiera: sappiamo che la riga nella scacchiera è 1 per Korrott e N per la poltrona).
Ciascuna delle righe seguenti nel file è riferita ad un ostacolo.
Su ciascuna riga del file si trovano due interi positivi (indice di riga e indice di colonna nella scacchiera, separati da uno spazio) che rappresentano la posizione dell’ostacolo considerato.

Dati di output

Il programma, dopo aver letto l’input, deve scrivere in output due righe.
Sulla prima riga le mosse fatte da Korrot, usando le abbreviazioni

A Alto
B Basso
D Destra
S Sinistra

Sulla riga successiva, il programma deve scrivere il risultato finale:

P Poltrona
C Confusione

 

Assunzioni

  • 1 < M, N < 210

 

Esempi di input/output

input.txt output.txt
1 5 6
3 2
0 0
AAAAS
P
2 7 8
2 6
3 2
5 3
5 4
7 4
7 5
0 0
ADAADDAADA
P
3 5 10
7 7
2 7
3 9
4 8
4 7
0 0
DAA
C
4 5 8
8 2
2 8
4 7
4 8
0 0
SAAD
C
5 5 7
6 1
5 3
5 4
0 0
AAAASBSSSAS
P

 

Note

  • I cinque esempi corrispondono alle Figure 1..5.
  • Korrot è un personaggio completamente inventato: non esiste alcuna creatura che strisci alla ricerca di una poltrona ed eviti gli ostacoli svoltando sempre a destra.

Giardinaggio

Pippo ha deciso di spendere il proprio tempo libero facendo giardinaggio.
Poiché il numero di fiori piantati nelle sue aiuole gli pare eccessivo, decide di ridurne il numero eliminando quelli tra loro più vicini.
A tale scopo, essendo appassionato di informatica, decide di scrivere un programma che gli permetta di risolvere il problema.

Di ogni fiore viene identificata la posizione e questa viene memorizzata in un file indicando le coordinate, in centimetri, rispetto l’angolo in basso a sinistra dell’aiuola; ogni posizione è contenuta in una riga diversa del file e codificata con due numeri interi separati da uno spazio.
Oltre alle righe che contengono le posizioni dei fiori, il file contiene anche, nella prima riga, il numero di fiori che deve essere eliminato.

In sostanza il programma deve cercare la coppia di fiori con distanza minima ed eliminare, dei due, il fiore più in alto (cioè quello la cui ordinata è maggiore); ripetere, quindi, l’operazione tante volte quanti sono i fiori da eliminare.
Nel caso in cui l’ordinata dei due fiori fosse uguale, il fiore da eliminare è quello con ascissa maggiore.

Dati di input

I dati di ingresso sono contenuti nel file input.txt che contiene:

  • nella prima riga, un numero intero che rappresenta il numero di fiori da eliminare;
  • dalla seconda riga al termine, coppie di numeri interi separati da uno o più spazi bianchi, il primo rappresenta l’ascissa ed il secondo l’ordinata della piantina

 

Dati di output

Il risultato deve essere scritto nel file di testo output.txt indicando le coordinate dei punti eliminati nello stesso formato del file in ingresso (esclusa la prima riga).
I punti devono essere ordinati, in modo crescente, rispetto all’ascissa, e nel caso in cui avessero la stessa ascissa, rispetto l’ordinata.

Assunzioni

  1. Non ci sono due o più fiori esattamente nello stesso punto;
  2. la distanza è calcolata usando la formula euclidea;
  3. il numero di piante da eliminare, indicato nel file di ingresso, è sempre minore o uguale al numero di piante contenute nello stesso file;
  4. il file di ingresso contiene almeno due piante;
  5. l’aiuola ha dimensioni 1000×1000 cm.

 

Esempio di input e output

input.txt output.txt
2
30 20
50 80
10 60
40 60
10 100
40 60
50 80

Foto stellare

Il dottor Hubb è un appassionato di astronomia.
Possiede una carta astronomica planare, composta dai due assi del piano cartesiano aventi l’origine in posizione (0,0).

ter_2004_fotoLa carta è suddivisa in quattro quadranti delimitati dagli assi cartesiani, dove a ciascun quadrante viene assegnata una lettera distinta come mostrato in figura:

Le stelle nella carta planare sono rappresentate mediante coordinate intere e un valore di intensità.
Precisamente, ciascuna stella è rappresentata da una tripla x, y, k, per individuare le coordinate (x, y) del centro della stella e la sua intensità espressa mediante un intero k Î {1,2,3}.

Al dottor Hubb piace molto scattare delle foto digitali al cielo stellato.
Ciascuna foto digitale è composta da zeri e da uni.
Lo sfondo del cielo è rappresentato dagli zeri, mentre una stella x, y, k è rappresentata dagli uni in accordo al valore di k:

In tal caso, la coordinata (x, y) si riferisce all’uno in posizione centrale.

Le stelle possono parzialmente sovrapporsi nelle foto ma le loro coordinate sono sicuramente distinte come coppie di valori.

Purtroppo il dottor Hubb è un pasticcione.
La sua carta astronomica contiene N stelle, e lui ha scattato una foto digitale di taglia MxM, ma non ricorda in quali quadranti.
Per l’elevata tecnologia adottata, non ci sono distorsioni ottiche: basta sovrapporre la foto digitale alla carta planare in una posizione opportuna, per farle combaciare e poter così ricostruire il quadrante (o i quadranti) di appartenenza.
Le risposte ammissibili sono A, B, C, D, AD, AB, BC, CD, ABCD, mentre AC, BD, ABC, ecc., non sono considerate valide.

Suggerimento

Quadrettare a griglia il piano cartesiano con le coordinate intere, assegnando le coordinate (x, y) al quadratino avente (x, y) come coordinata dello spigolo inferiore sinistro.

Dati di input

Il file di input contiene una sequenza di righe.
La prima riga contiene il valore di N e M.
Le N righe successive rappresentano le N stelle nella carta astronomica, ciascuna riga contenente una tripla x, y, k, interpretata in accordo a quanto descritto sopra.
Le M righe finali rappresentano la foto digitale, ogni riga contenente una sequenza di M valori scelti tra zeri e uni.

Dati di output

Il file di output contiene una sola delle risposte ammissibili, A, B, C, D, AD, AB, BC, CD, ABCD, in base alla posizione della foto digitale rispetto ai quadranti della carta astronomica.

Assunzioni

I numeri sono rappresentati con il segno.
Le coordinate (x, y) sono coppie di numeri, dove -1000 < x, y < 1000.
Per la conformazione della carta stessa e della foto c’è esattamente una risposta da fornire (non è possibile che la foto appaia due o più volte in posizioni distinte).
La foto non taglia le stelle: una stella è interamente catturata dalla foto oppure non è catturata affatto.
Infine, se una stella ha centro nel quadrante A ma la sua intensità è tale che induca un uno nel quadrante B, per esempio, allora la stella viene considerata a cavallo dei due quadranti A e B (non conta solo il centro, ma anche l’intensità).

Esempio di input e output

input.txt output.txt
9 7
3 7 1
2 6 1
1 2 2
2 1 1
1 7 1
1 3 3
2 3 2
2 -1 1
3 -1 1
1000100
0100000
0000100
0001110
0011111
0111110
0110100
AB

Motivazione per la risposta: la foto è stata scattata a cavallo dei quadranti A e B, e contiene le prime 7 stelle elencate nel file input.txt.

Enrica

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).
ter_2003_enrica
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.

File di 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à.

 

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 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;

Esempio

Questo esempio corrisponde a quello mostrato in figura

input.txt output.txt
7 15
5
3 3 8
5 9 11
6 6 10
9 2 5
11 9 12
19 9

Codice

Fase territoriale

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.

File di input

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

File di 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

input.txt output.txt
0142112* 2112
01541012001101234567890011000112234234234234* 41012
1234567890
0
234234234234

Depurazione dell’acqua

Fase Territoriale 2009

Bisogna realizzare un procedimento chimico per la depurazione dell’acqua, avendo a disposizione un certo numero di sostanze, numerate da 1 in avanti.
Per un’efficace depurazione, è necessario inserire nell’acqua la sostanza chimica purificante numero 1, tenendo presente che nell’acqua sono già presenti K sostanze chimiche.

Per quanto riguarda il procedimento adottato, valgono R precise regole per poter inserire le sostanze chimiche nell’acqua.
Tali regole prevedono che una certa sostanza A possa essere inserita solo se nell’acqua sono già presenti un dato insieme di sostanze, ad esempio, A1, A2,..., An (dove Ai ≠ A per 1 ≤ i ≤ n).
In tal caso, scriviamo tale regola di inserimento nel seguente modo A :-- A1, A2,..., An e diciamo che A compare nella parte sinistra della regola.

Al fine di un corretto inserimento delle sostanze, valgono le seguenti osservazioni:

  • l’eventuale presenza di ulteriori sostanze non inibisce l’applicabilità della regola suddetta;
  • se A compare nella parte sinistra di una regola, allora non può comparire nella parte sinistra di altre regole e non può essere una delle K sostanze già presenti nell’acqua;
  • qualora una sostanza sia priva di regole (ossia non compaia mai nella parte sinistra di una qualche regola) e non sia già presente nell’acqua, tale sostanza non può essere inserita;
  • non è necessario usare tutte le regole e/o tutte le sostanze a disposizione.

Per esempio, ipotizzando che le sostanze 2 e 3 siano già presenti nell’acqua (K=2) e che valgano le seguenti regole (R=4):

4 :– 2
5 :– 2, 3
7 :– 2, 4
1 :– 3, 7, 4

possiamo inserire la sostanza 4 perché la sostanza 2 è già presente (prima regola); in seguito, possiamo inserire anche la sostanza 7 perché le sostanze 2 e 4 sono presenti nell’acqua (terza regola); a questo punto, possiamo aggiungere la sostanza 1 perché le sostanze 3, 7 e 4 sono presenti (ultima regola).
Quindi abbiamo inserito un totale di S=3 sostanze, ossia 4, 7 e 1 (oltre alle K=2 già presenti), per purificare l’acqua.

Scrivere un programma che calcoli il numero minimo S di sostanze da inserire per purificare l’acqua, conoscendo le K sostanze già presenti nell’acqua e le R regole di inserimento.
Tale numero sarà S = 0 se la sostanza 1 è già presente nell’acqua; sarà S = 1 se la sostanza 1 può essere inserita direttamente e non è già presente; in generale, sarà S = m se è necessario inserire m-1 sostanze prima di poter inserire la sostanza 1.
Nel caso in cui non sia possibile purificare l’acqua, bisogna restituire il valore S = -1.

Dati di input

Il file input.txt è composto da K+R+1 righe.
La prima riga contiene due interi positivi separati da uno spazio, rispettivamente il numero K delle sostanze chimiche già presenti nell’acqua e il numero R di regole di inserimento.
La successive K righe contengono le K sostanze già presenti nell’acqua, dove ogni riga è composta da un solo intero positivo che rappresenta una di tali sostanze.
Le ultime R righe rappresentano le R regole, al massimo una regola per ciascuna sostanza non presente nell’acqua. Ciascuna riga è composta da n+2 interi positivi A, n, A1, A2,..., An separati da uno spazio (dove Ai ≠ A per 1 ≤ i ≤ n), i quali rappresentano la regola A :-- A1, A2,..., An.

Dati di output

Il file output.txt è composto da una sola riga contenente un intero S, il minimo numero di sostanze inserite (oltre alle K già presenti) per purificare l’acqua secondo le regole descritte sopra.

Assunzioni

  • 1 ≤ K, R ≤ 1000
  • Il numero di sostanze chimiche a disposizione è al massimo 2000.
  • I casi di prova non contengono mai situazioni cicliche: in tal modo, non accade mai che una sostanza A possa essere inserita solo se A stessa è già presente nell’acqua.

Esempi

input.txt output.txt
1 2 4
2
3
4 1 2
5 2 2 3
7 2 2 4
1 3 3 7 4
3
2 4 2
6
2
8
3
1

Nota

  • Il numero di sostanze chimiche a disposizione può essere semplicemente dedotto guardando il massimo intero contenuto nel file input.txt.
  • Il numero R di regole di inserimento può essere inferiore al numero di sostanze a disposizione e non presenti nell’acqua.
  • Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio in aggiunta a quello ottenuto per la sua compilazione.

Sbarramento tattico

Fase Territoriale 2010

L’esercito di Orchi dell’Oscuro Signore degli Anelli marcia a ranghi serrati verso il Fosso di Helm.
Per contrastarne la marcia, Re Theoden decide di richiamare tutte le sue N armate per creare uno sbarramento unico, con le seguenti regole

  • Campo di battaglia: è rappresentato da una tabella di dimensione N x N, le cui righe e colonne sono numerate da 1 a N.
  • Posizione: ognuna delle N armate occupa una posizione distinta [i,j] nella tabella, all’incrocio tra la riga i e la colonna j.
  • Movimento: permette di passare dalla posizione corrente [i,j] a una vicina con un giorno di marcia:
    nord [i-1,j] (se i > 1),
    sud [i+1,j] (se i < N),
    est [i,j+1] (se j < N) e
    ovest [i,j-1] (se j > 1).

    Una sola armata alla volta si sposta con un movimento.

  • Sbarramento: si crea ponendo tutte le armate su un’unica riga R della tabella, attraverso una serie di movimenti.

Theoden vuole calcolare il numero minimo di movimenti necessari per spostare tutte le armate in un unico sbarramento sulla riga R.
Aiutate Theoden a calcolare tale numero minimo.

Dati di input

Il file input.txt è composto da N+1 righe.
La prima riga contiene due interi positivi N e R, separati da uno spazio: il numero N di righe e di colonne nella tabella (nonché il numero di armate) e l’indice R della riga su cui far convergere lo sbarramento delle armate.
Ciascuna delle successive N righe contiene una coppia di interi i e j, separati da uno spazio, a indicare che un’armata è presente nella posizione [i,j] della tabella.

Dati di output

Il file output.txt è composto da una sola riga contenente un intero non negativo, il minimo numero di movimenti per posizionare tutte le armate sulla riga R della tabella, in posizioni distinte all’interno di tale riga.

Assunzioni

  • 2 <= N <= 500.
  • Durante un movimento, due o più armate non possono mai occupare la stessa posizione intermedia.

Esempi

input.txt output.txt
1 8 3
5 5
1 6
2 2
6 5
3 2
7 1
1 2
8 1
31
2 8 5
5 7
5 2
5 3
5 6
5 1
5 8
5 5
5 4
0

Il tesoro del Pirata Barbablù

Fase Territoriale 2012

John Steam della compagnia Oriental Steam Navigation decide di organizzare una spedizione di recupero del tesoro del Pirata Barbablù, custodito nel relitto del galeone del pirata, affondato al largo di Gobal, che si trova adagiato su un fianco a 30 metri di profondità.
L’unico punto di accesso al relitto è uno squarcio sulla fiancata, in corrispondenza della cabina numero 1.
Nel galeone sono presenti cabine e corridoi che le collegano.
Tutti i corridoi sono totalmente sommersi dall’acqua a causa della rottura degli oblo mentre in alcune delle cabine sono rimaste delle sacche d’aria.
A causa degli spazi angusti non è possibile, per i sommozzatori, esplorare la nave con le bombole d’aria; sono quindi
costretti a nuotare in apnea, sfruttando le sacche d’aria presenti nel tragitto per respirare.
Prima di procedere con le operazioni di recupero ti viene commissionata la realizzazione di un programma in grado di individuare il percorso più breve all’interno del galeone che permetta ai sommozzatori di raggiungere la cabina con il tesoro a partire dall’apertura.
In alcune cabine sono presenti sacche d’aria che possono essere usate per respirare.
Un sommozzatore riesce a nuotare senza aria per 20 metri al massimo prima di dover riprendere fiato.

In Figura sono mostrati due possibili scenari.
ter_2012_barbablu
La cabina di ingresso è come detto la numero 1, mentre la cabina del tesoro (rappresentato da una T) è la numero 2 per l’esempio di sinistra, e la numero 4 per l’esempio di destra.
Le cabine con la sacca d’aria sono quadrate, mentre quelle senza sacca sono tonde.
A fianco di ogni corridoio è segnata la sua lunghezza in metri.
L’esempio di sinistra ammette una sola soluzione, di lunghezza 29 metri, mentre quello di destra non ha soluzioni.

Dati di input

Il file input.txt è composto da M+2 righe.
La prima riga contiene quattro interi positivi separati da uno spazio, che rappresentano il numero N delle cabine, il numero M dei corridoi, il numero C che rappresenta la cabina del tesoro e il numero K che rappresenta quante cabine hanno sacche d’aria al loro interno.
La seconda riga contiene K numeri separati da uno spazio che rappresentano i numeri (distinti) delle cabine che contengono aria.
Ciascuna delle rimanenti M righe contiene tre interi I, J, L separati da uno spazio che indicano la presenza di un corridoio che collega le cabine I e J di lunghezza L (in metri).

Dati di output

Il file output.txt è composto da una sola riga contenente la lunghezza in metri del percorso più breve che permetta, a partire dall’apertura, di raggiungere la cabina del tesoro in apnea.
Riportare -1 se non esiste nessun percorso che soddisfa i vincoli.

Assunzioni

  • 2 <= N <= 30
  • 2 <= M <= 100
  • 1 <= C <= N
  • 0 <= K <= N

Esempio

input.txt output.txt
1 3 3 2 2
2 3
1 2 22
1 3 15
2 3 14
29
2 4 5 4 2
3 4
1 2 11
1 3 7
1 4 23
2 4 14
3 4 21
-1

Nota

  • Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio.