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.
Umowy międzynarodowe podpisane przez Wielce Rozległe Państwo nakładają na nie obowiązek tranzytowy - musi ono umożliwić przewiezienie koleją odpadów nuklearnych z elektrowni u wschodniego sąsiada do punktów utylizacji za zachodnią granicą. Względy ekologiczne nakazują taką organizację ruchu, by pociągi z odpadami jak najszybciej opuściły terytorium kraju.
Sieć kolejowa w tym państwie ma bardzo szczególną strukturę. Składa się ona z miast-węzłów kolejowych oraz dwukierunkowych odcinków torów, łączących miasta-węzły. Między każdymi dwoma miastami istnieje możliwość przejazdu. Ponadto istnieje taki odcinek sieci, którego końce nie są miastami granicznymi, oraz każdy przejazd z miasta na granicy wschodniej do miasta na granicy zachodniej prowadzi przez ten odcinek.
Wszystkie pociągi z odpadami przyjeżdżają na granicę wschodnią tego samego dnia przed świtem, przy czym każdy z nich do innego miasta. Ze względu na niebezpieczeństwo wypadku pociągi jeżdżą tylko w dzień i po żadnym odcinku nie może jednocześnie jechać więcej niż jeden pociąg z odpadami, natomiast dowolnie wiele takich pociągów może oczekiwać w mieście-węźle. Dodatkowo przejechanie jednego odcinka zajmuje pociągowi jeden dzień. Ruch musi być tak zorganizowany, by każdy pociąg z odpadami dojechał do innego przejścia na granicy zachodniej.
Ile co najmniej dni pociągi z odpadami muszą spędzić na terytorium Wielce Rozległego Państwa?
Zadanie polega na napisaniu programu, który:
Pierwsza linia wejścia zawiera trzy pooddzielane pojedyńczymi odstępami liczby naturalne , . Liczba oznacza liczbę miast-węzłów (są one ponumerowane od 1 do ), zaś i oznaczają liczby przejść granicznych odpowiednio na granicy wschodniej i zachodniej. Przejścia na granicy wschodniej oznaczone są liczbami , zaś na zachodniej liczbami .
W kolejnych liniach znajduje się opis odcinków sieci kolejowej. Każda linia opisu zawiera dwie różne liczby naturalne oddzielone pojedynczym odstępem, . Są to numery miast-węzłów połączonych odcinkiem torów.
W -ej linii znajduje się jedna liczba naturalna , , oznaczająca liczbę pociągów z odpadami. W następnej (i ostatniej) linii wejścia znajduje się pooddzielanych pojedyńczymi odstępami różnych liczb naturalnych, z których każda jest nie większa niż . Są to numery przejść granicznych na granicy wschodniej, do których przyjechały pociągi z odpadami.
Pierwsza i jedyna linia wyjścia powinna zawierać dokładnie jedną liczbę całkowitą, równą minimalnej liczbie dni, jakie odpady muszą spędzić na terytorium państwa.
Dla danych wejściowych:
9 2 3 1 3 2 3 4 3 4 5 4 6 7 4 5 8 9 6 2 1 2
poprawną odpowiedzią jest:
4
Strzałki przedstawiają ruch pociągów w kolejnych dniach
dla jedej z optymalnych organizacji ruchu kolejowego - pętla
oznacza, że danego dnia pociąg stał w mieście-węźle.
Autor zadania: Karol Cwalina.