In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Bajtek od niedawna uczy się chemii i bardzo go ten przedmiot zafascynował. Postanowił nawet stworzyć własne laboratorium. Już skompletował pewien zestaw związków chemicznych oraz narzędzi do przeprowadzania różnych reakcji. Chciałby teraz pomnożyć swoje zasoby i jest ciekaw, ile różnych związków chemicznych, jakich jeszcze nie posiada, jest w stanie wyprodukować przy użyciu tego, co ma do dyspozycji.
Ponieważ jednak matematyka nie jest jego dobrą stroną, Bajtek poprosił Ciebie o napisanie programu, który wyznaczy liczbę tych związków. Dla uproszczenia zakładamy, że każdy spośród już skompletowanych związków chemicznych Bajtek posiada w nieskończonej ilości.
Napisz program, który:
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , oraz (, , ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio: liczbę znanych Bajtkowi związków chemicznych, liczbę związków chemicznych posiadanych przez Bajtka oraz liczbę reakcji, jakie jest on w stanie przeprowadzić. W drugim wierszu znajduje się liczb całkowitych (), pooddzielanych pojedynczymi odstępami i oznaczających numery związków chemicznych posiadanych przez Bajtka. Numery te są parami różne.
W każdym z następnych wierszy znajduje się opis jednej reakcji, jaką potrafi wykonać Bajtek. Opis każdej reakcji składa się z opisu jej substratów (związków chemicznych potrzebnych jako składniki do jej przeprowadzenia) oraz następującego po nim opisu produktów. Opis substratów składa się z liczby całkowitej () oznaczającej liczbę substratów tej reakcji, po której następuje numerów związków chemicznych, potrzebnych do przeprowadzenia reakcji. Następnie w tym samym wierszu znajduje się opis produktów. Składa się on z liczby całkowitej (), oznaczającej liczbę produktów reakcji, po której następuje numerów związków chemicznych, jakie otrzymuje się po przeprowadzeniu -tej reakcji. Każdy z numerów związków chemicznych uczestniczących w reakcji (zarówno substratów, jak i produktów) jest liczbą całkowitą z zakresu od do włącznie. Numery substratów dowolnej reakcji są parami różne; podobnie numery produktów też są parami różne. Może się jednak zdarzyć, że jakiś związek jest jednocześnie substratem i produktem reakcji (może on wówczas być jej katalizatorem). Wszystkie liczby występujące w opisie jednej reakcji są pooddzielane pojedynczymi odstępami.
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą liczbę związków chemicznych, których Bajtek jeszcze nie posiada, ale potrafi wyprodukować z już posiadanych związków za pomocą odpowiednich reakcji chemicznych.
Dla danych wejściowych:
8 2 4 2 1 2 1 2 2 3 4 2 4 1 1 3 2 2 3 3 2 1 5 2 5 6 3 1 8 2
poprawną odpowiedzią jest:
3
W powyższym przykładzie Bajtek potrafi przeprowadzić następujące reakcje:
Na początku posiada on związki i , przy użyciu pierwszej reakcji może otrzymać związki oraz , a następnie, przeprowadzając trzecią reakcję, może wyprodukować związek . Natomiast związków , ani nie jest on w stanie otrzymać.
Autor zadania: Marian M. Kędzierski.