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.
Bajtazar jest chemikiem. Przeprowadza eksperyment, którego celem jest uzyskanie specyfiku X - mikstury rozwiązującej wszelkie problemy ludzkości.
Bajtazar posiada fiolek ponumerowanych liczbami od do , w których znajdują się różne płynne substancje. Fiolka o numerze zawiera całkowitą liczbę gramów substancji . Aby uzyskać specyfik X, należy wykonać sekwencję kroków. Każdy krok polega na przelaniu całej zawartości pewnej fiolki do innej (możemy przy tym założyć, że fiolki mają odpowiednio dużą pojemność, a także, że przy przelewaniu nie uronimy ani kropli). Fiolka, z której przelano substancję, jest odstawiana na półkę i nie jest wykorzystywana w dalszej części eksperymentu.
O pewnych parach substancji wiadomo, że reagują ze sobą, tworząc związek chemiczny, który wytrąca się w postaci osadu. Dla każdej takiej reakcji, na jeden gram pierwszej substancji przypada jeden gram drugiej, a w jej wyniku powstają dwa gramy osadu. Reakcja trwa, dopóki któryś z jej substratów się nie skończy. Wytrącony osad nie reaguje z żadną substancją i do końca eksperymentu przylega do ścianki fiolki, w której powstał. Pewne reakcje dokonują się szybciej niż inne - jeśli wiele substancji znajdzie się naraz w jednym roztworze, reakcje pomiędzy parami substancji wykonują się w ustalonej, znanej Bajtazarowi kolejności. Po każdym kroku Bajtazar czeka, aż substancje w docelowej fiolce przereagują, i dopiero wtedy wykonuje kolejny krok.
Bajtazar zastanawia się, czy sekwencja kroków prowadząca do uzyskania specyfiku X jest optymalna. Chciałby wiedzieć, jaka część substratów marnuje się w wyniku wykonania wszystkich kroków. Poprosił Cię zatem o pomoc w znalezieniu łącznej liczby gramów wytrąconego osadu.
Pierwszy wiersz wejścia zawiera trzy liczby całkowite , oraz (, ), oznaczające kolejno: liczbę fiolek (a więc także liczbę różnych substancji), długość sekwencji kroków eksperymentu oraz liczbę par substancji, której ze sobą reagują, wytrącając osad.
W drugim wierszu znajduje się ciąg liczb całkowitych (), określających początkową liczbę gramów substancji w fiolce numer .
W kolejnych wierszach znajduje się opis sekwencji kroków prowadzących do uzyskania specyfiku X: -ty z tych wierszy zawiera dwie liczby całkowite (), oznaczające, że -ty krok polega na przelaniu zawartości fiolki numer do fiolki numer . Można założyć, że jeśli w pewnym kroku wylewamy zawartość fiolki, to ta fiolka nie zostanie użyta w żadnym z kolejnych kroków.
W następnych wierszach znajduje się opis par substancji, które reagują ze sobą, tworząc osad: -ty z tych wierszy zawiera dwie liczby całkowite , () oznaczające, że jeśli substancje i znajdą się jednocześnie w jednej fiolce, to zajdzie między nimi reakcja i wytrąci się osad. Pary substancji podane są w kolejności zgodnej z priorytetem wykonywania reakcji, tzn. w przypadku, gdy w fiolce znajdą się się co najmniej dwie pary reagujących ze sobą substancji, w pierwszej kolejności rozpocznie się (i całkowicie zakończy) reakcja pary substancji podanej na wejściu najwcześniej. Żadna nieuporządkowana para liczb nie powtórzy się wśród tych wierszy.
W jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita, oznaczająca łączną liczbę gramów wytrąconego osadu po wykonaniu całej sekwencji kroków eksperymentu.
Dla danych wejściowych:
3 2 1 2 3 4 1 2 3 2 2 3
poprawną odpowiedzią jest:
6
Autor zadania: Jakub Radoszewski.