IX Olimpiada Informatyczna 2001/2002
|
Zadanie: zam
|
Autor: Zbigniew Czech
|
Zawody I stopnia |
Plik źródłowy: | zam.??? (np. pas, c, cpp) |
Plik wykonywalny: | zam.exe |
Plik wejściowy: | zam.in |
Plik wyjściowy: | zam.out |
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:
zam.in
opis zamku, numer komnaty,
w której znajduje się księżniczka i kwotę w sakiewce,
zam.out
.
W pierwszym wierszu pliku tekstowego
zam.in
zapisanych jest pięć
dodatnich liczb całkowitych n, m, w, k, s,
1<=n<=100, 1<=m<=4950,
1<=w,k<=n,
1<=s<=1 000, pooddzielanych pojedynczymi odstępami.
Liczba n jest równa liczbie komnat, a m liczbie korytarzy.
Komnaty są
ponumerowane od 1 do n.
Liczba w jest numerem komnaty wejściowej, a
k numerem komnaty, w której znajduje się
księżniczka. Liczba s określa
liczbę bajtków w sakiewce. W drugim wierszu zapisanych jest n
dodatnich liczb całkowitych
o1, o2, .... ,
on, 1<=oi<=1 000,
pooddzielanych
pojedynczymi odstępami.
Liczba oi jest równa opłacie za (każdorazowy)
wstęp do komnaty nr i.
W kolejnych m wierszach zapisane są po dwie
dodatnie liczby całkowite x, y,
x<>y, 1<=x, y<=n,
oddzielone pojedynczym
odstępem. Każda taka para x, y oznacza,
że komnaty o numerach x i y są
połączone korytarzem.
Twój program powinien w pierwszym
(i jedynym) wierszu pliku zam.out
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 pliku wejściowego zam.in
:
5 6 3 4 9 1 2 3 4 5 2 4 5 4 1 5 1 2 2 3 3 1poprawną odpowiedzią jest plik wyjściowy
zam.out
:
3 2 4