Polish version    English version  
  Historia OI -> IX OI 2001/2002 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
Statystyki
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Zadanie: zam
Autor: Zbigniew Czech
Zamek

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?

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego zam.in opis zamku, numer komnaty, w której znajduje się księżniczka i kwotę w sakiewce,
  • wyznaczy ciąg komnat, przez które należy kolejno przejść, aby dojść z komnaty wejściowej do komnaty, w której znajduje się księżniczka i wydać dokładnie całą zawartość sakiewki,
  • zapisze znalezioną drogę w pliku tekstowym zam.out.
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.

Wejście

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.

Wyjście

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.

Przykład

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 1
poprawną odpowiedzią jest plik wyjściowy zam.out:
3 2 4

Zamek




Wersja do druku