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:
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.
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.
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.
| File input.txt | File output.txt |
2 4 2 3 4 1 2 5 2 2 3 7 2 2 4 1 3 3 7 4 | 3 |
| File input.txt | File output.txt |
4 2 6 2 8 3 5 2 2 6 1 2 3 6 | 1 |
| File input.txt | File output.txt |
2 3 1 3 4 1 2 5 1 3 6 2 2 4 | 0 |
| File input.txt | File output.txt |
3 4 2 4 8 5 2 2 4 7 2 4 3 6 2 5 7 1 3 5 2 6 | -1 |