Alibaba
Limit pamięci: 32 MB
Aby otworzyć Sezam, trzeba mieć komplet co najmniej żetonów złotych, — srebrnych i — miedzianych.
Alibaba ma początkowo pewną liczbą żetonów każdego rodzaju i może je wymieniać u strażnika Sezamu według ściśle określonych reguł.
Każda reguła jest postaci:
()
gdzie: oznaczają odpowiednio liczby żetonów złotych, srebrnych i miedzianych, jakie Alibaba musi dać strażnikowi,
zaś — liczby żetonów złotych, srebrnych i miedzianych, które otrzyma w wyniku transakcji wymiany.
Żetony otrzymane w wyniku transakcji można wymieniać w kolejnych transakcjach.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia zestawy danych, z których każdy zawiera:
- liczby żetonów złotych, srebrnych i miedzianych znajdujących się początkowo w posiadaniu Alibaby,
- opis kompletu żetonów otwierającego Sezam, oraz reguły transakcji;
- dla każdego zestawu danych stwierdza, czy istnieje skończony ciąg transakcji,
który pozwoli Alibabie zgromadzić komplet żetonów otwierający Sezam i jeśli tak,
znajduje i wypisuje na standardowe wyjście minimalną długość takiego ciągu,
a w przeciwnym przypadku wypisuje odpowiedź NIE.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia ().
Jest to liczba zestawów danych.
Dalej są zapisane kolejno zestawy danych.
Każdy zestaw danych składa się z wielu wierszy.
W pierwszym wierszu są zapisane trzy liczby całkowite nieujemne .
Są to liczby żetonów złotych, srebrnych i miedzianych, jakie na początku ma Alibaba.
W drugim wierszu są kolejne trzy liczby całkowite .
Są to liczby żetonów złotych, srebrnych i miedzianych, jakie trzeba mieć, aby otworzyć Sezam.
W trzecim wierszu jest zapisana liczba reguł , gdzie .
W każdym z kolejnych wierszy jest zapisany ciąg sześciu liczb
należących do zbioru .
Każda taka szóstka liczb jest zapisem jednej reguły transakcji: .
Liczby w każdym wierszu są pooddzielane pojedynczymi odstępami.
Wyjście
W -tym wierszu standardowego wyjścia należy wypisać wynik dla -tego zestawu danych:
- jedną liczbę całkowitą nieujemną, tj. minimalną liczbę transakcji wymiany,
jakich Alibaba musi dokonać, aby zgromadzić komplet żetonów otwierający Sezam,
- albo jedno słowo NIE.
Przykład
Dla danych wejściowych:
2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2
poprawną odpowiedzią jest:
NIE
9
Autor zadania: Piotr Chrząstowski-Wachtel.