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.