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.
Megachip IV Wspaniały, król Bajtocji, zamierza wydać za mąż swą urodziwą córkę, księżniczkę Adę. Zapytał ją jakiego męża chciałaby mieć. Księżniczka odpowiedziała, że jej przyszły małżonek powinien być mądry, a także ani skąpy, ani rozrzutny. Zamyślił się król nad tym, jakim to próbom powinni być poddani kandydaci na męża, aby mógł wybrać dla swej córki najlepszego z nich. Po długich dumaniach stwierdził, że najlepiej posłuży do tego zamek, który kazał był wybudować ku uciesze mieszkańców Bajtocji. Zamek składa się z dużej liczby komnat, w których zgromadzono bogactwa królestwa. Komnaty te, połączone korytarzami, mogą być zwiedzane przez poddanych w celu podziwiania wystawionych w nich wspaniałości. Za zwiedzenie komnaty trzeba uiścić pewną liczbę bajtków (bajtek jest jednostką pieniężną Bajtocji). Zwiedzanie zamku rozpoczyna się od komnaty wejściowej.
Król wręczył sakiewkę każdemu kandydatowi na męża księżniczki. W każdej sakiewce była taka sama liczba bajtków. Poprosił każdego kandydata, aby ten wybrał taką drogę, która pozwoli, poczynając od komnaty wejściowej, odwiedzić pewną liczbę komnat zamku oraz zakończyć zwiedzanie w komnacie, w której przebywa księżniczka, i wydać przy tym dokładnie kwotę, jaka była w sakiewce. Rozrzutni kandydaci, którzy wydawali po drodze zbyt dużo, nie docierali do komnaty księżniczki, skąpi natomiast zjawiali się z niepustą sakiewką i księżniczka wyprawiała ich w dalszą drogę celem opróżnienia sakiewki.
Niestety, do dziś żadnemu z kandydatów nie udało się sprostać zadaniu króla, a księżniczka Ada wciąż z utęsknieniem czeka na swój ideał. Może Ty staniesz w szranki pisząc program, który pomoże biednej księżniczce?
Napisz program, który:
Możesz założyć, że dla danych testowych taka droga zawsze istnieje. Jeśli istnieje wiele takich dróg, Twój program powinien wyznaczyć dowolną z nich.
W pierwszym wierszu standardowego wejścia zapisanych jest pięć dodatnich liczb całkowitych , , , , , , , , , pooddzielanych pojedynczymi odstępami. Liczba jest równa liczbie komnat, a liczbie korytarzy. Komnaty są ponumerowane od do . Liczba jest numerem komnaty wejściowej, a numerem komnaty, w której znajduje się księżniczka. Liczba określa liczbę bajtków w sakiewce. W drugim wierszu zapisanych jest dodatnich liczb całkowitych , , pooddzielanych pojedynczymi odstępami. Liczba jest równa opłacie za (każdorazowy) wstęp do komnaty nr . W kolejnych wierszach zapisane są po dwie dodatnie liczby całkowite , , , , oddzielone pojedynczym odstępem. Każda taka para oznacza, że komnaty o numerach i są połączone korytarzem.
Twój program powinien w pierwszym (i jedynym) wierszu standardowego wyjścia zapisać ciąg dodatnich liczb całkowitych, pooddzielanych pojedynczymi odstępami, określający numery kolejnych komnat, przez które należy przejść, aby z komnaty wejściowej dostać się do komnaty, w której znajduje się księżniczka i wydać dokładnie całą zawartość sakiewki.
Dla danych wejściowych:
5 6 3 4 9 1 2 3 4 5 2 4 5 4 1 5 1 2 2 3 3 1
poprawną odpowiedzią jest:
3 2 4
Autor zadania: Zbigniew Czech.