W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Na pewną bajtocką wyspę co roku trafia duży transport surowców. Dostarczane są one do portu, skąd dalej rozwożone są pociągiem do wszystkich miast na całej wyspie. Miasta znajdują się tylko przy brzegu i są ponumerowane kolejno od do . Trasa pociągu prowadzi wokół całej wyspy przez wszystkie miasta.
Pociąg składa się z lokomotywy ciągnącej pewną liczbę wagonów. W każdym wagonie przewożony jest inny rodzaj surowca. Ponadto, do każdego miasta dostarczany jest inny surowiec. Wagonów jest dokładnie tyle co miast. Dotychczas wagony były zawsze tak ustawiane, że pociąg w każdym mieście odczepiał ostatni wagon i ruszał do następnego miasta. W ten sposób wykonywał tylko jedno okrążenie. Niestety tym razem surowce zostały źle oznaczone i pomylono kolejność ustawienia wagonów.
Maszynista zastanawia się, ile minimalnie okrążeń będzie musiał wykonać, aby rozwieźć wszystkie surowce do odpowiednich miast, wiedząc, że może zawsze odczepiać tylko ostatni wagon oraz nie może doczepiać już odczepionych. Stacją początkową i końcową jest miasto numer 1, w którym również znajduje się port. Nowe okrążenie liczone jest wtedy, gdy pociąg wyruszy do miasta numer 2.
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę miast położonych na wyspie. W kolejnym wierszu znajduje się liczb całkowitych (, dla ), przy czym oznacza rodzaj surowca znajdującego się w -tym wagonie od lokomotywy. W kolejnym wierszu znajduje się parami różnych liczb całkowitych , oznaczających surowce zamawiane przez miasta o numerach . Liczby w drugim i trzecim wierszu są pooddzielane pojedynczymi odstępami. Można założyć, że zbiory liczb oraz są takie same, tzn. .
W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita oznaczająca minimalną liczbę okrążeń, które pozwolą rozwieźć wszystkie surowce do odpowiednich miast.
Dla danych wejściowych:
5 1 2 3 4 5 1 3 4 2 5
poprawną odpowiedzią jest:
3
Wyjaśnienie do przykładu: W pierwszym okrążeniu odczepiony zostaje tylko wagon przewożący surowiec numer 5, w drugim - wagon przewożący surowiec numer 4, wreszcie w trzecim, ostatnim okrążeniu odczepione zostają kolejno wagony przewożące surowce o numerach 3, 2, 1.
Autor zadania: Jacek Tomasiewicz.