|
|
Poprawka Program II - ZamekDo poprawki z uwagi na karygodnie niski poziom grupy dwójkowiczów tym razem należy załączyć poprawiony program z kolokwium.Adresat zadania: Zadanie powinny wykonać wszystkie zespoły, które nie zaliczyły Programu II. Dla pozostałych zadanie nie jest obowiązkowe. Tym razem zadanie jest zapożyczone, ale myślę, że nie mniej ciekawe:). Zmierzenie się z tego typu 'prawdziwym' problem na pewno wyjdzie Wam na zdrowie. Wymaga kilku godzin pracy proponuję więc zarezerwować sobie całe popołudnie - większość czasu poświęcając na przemyślenie algorytmu a nie samo pisanie. Wprowadzenie: Megachip IV Wspaniały, król Bajtocji, zamierza wydać za maż 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? Szczegóły: Plik wejściowy zam.in Plik wyjściowy zam.out 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 9poprawną odpowiedzią jest plik wyjściowy zam.out: 3 2 4  Czas: Termin zgłaszania programu do oceny 2002-05-15 23:59:59 :) Ocena: Do zaliczenia wymagane jest poprawienie Programu II z kolokwium czyli doprowadzenie do stanu używalności oraz stworzenie działającego programu wg podanych powyżej założeń. Kod programu musi być podzielony na funkcje, a funkcje zaopatrzone w niezbędne komentarze. 4 otrzymują studenci, którzy napiszą program bez większych wpadek, znajdujacy drogę choćby metodą czołgową. 5 należy się osobom, które opracują algorytm nie wykorzystujący metody czołgowej Forma: Program należy przesłać na mail r.papis@done.pl lub przekazać na dyskietce w czasie zajęć lub konsultacji. Źródło: IX Olimpiada Informatyczna 2001/2002 |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
wszelkie pytania proszę kierować pod adres r.papis@done.pl |
|
