| Historia OI -> III OI 1995/1996 -> Zadania |  |
|
III Olimpiada Informatyczna 1995/96
|
|
Zadanie: GON
|
Autor: Krzysztof Diks
|
| Zawody I stopnia |
| Plik źródłowy: | GON.??? (np. pas, c, cpp) |
| Plik wykonywalny: | GON.exe |
| Plik wejściowy: | GON.in |
| Plik wyjściowy: | GON.out |
Król Informaticus, władca Bajtocji, ma zmartwienie. Tajne służby doniosły mu, że zły król Haker postanowił napaść na jego królestwo. Co więcej, Haker wysłał już tajnych agentów do jednego z miast Bajtocji poza stolicą, by utrudniali królowi Informaticusowi przygotowania do obrony. Informaticus postanowił powiadomić mieszkańców kraju o grożącym niebezpieczeństwie.
Obywatele Bajtocji mieszkają tylko w miastach. Miasta są ponumerowane od 1 do n, gdzie 3 <= n <= 500. Stolica kraju ma numer 1. W kraju istnieje dobrze rozwinięta sieć dróg. Wszystkie drogi są dwukierunkowe. Dowolne dwa miasta mają co najwyżej jedno bezpośrednie połączenie drogowe, ale dla każdych dwóch różnych miast A, B można przejechać z A do B, a następnie wrócić z B do A nie przejeżdżając ponownie przez żadne z miast na trasie z A do B.
Król Informaticus postanowił wysłać niezależnie dwóch gońców, by ostrzegli mieszkańców wszystkich miast o grożącym niebezpieczeństwie. Każdy goniec porusza się po drogach Bajtocji i może wielokrotnie odwiedzać to samo miasto. Jednak kolejność, w jakiej goniec odwiedza poszczególne miasta po raz pierwszy, musi być zgodna z planem, który otrzymał od króla.
Plan jest ciągiem n różnych liczb całkowitych x1, x2, ..., xn z zakresu [1..n], przy czym x1 = 1. Po drodze z miasta o numerze xi do miasta o numerze xi+1 goniec może przejść przez dowolną, skończoną liczbę miast, ale tylko tych, które już wcześniej odwiedził. Niestety, na posłańców czyhają ludzie Hakera i biorą w niewolę każdego gońca, który trafi do opanowanego przez nich miasta. Trzeba przygotować takie plany tras podróży obu gońców, aby do każdego miasta Bajtocji dotarł przynajmniej jeden z nich, zanim obaj zostaną schwytani przez ludzi Hakera, ukrytych w jednym z miast poza stolicą.
Zadanie
Ułóż program, który:- wczytuje z pliku tekstowego GON.IN liczbę n wszystkich miast w Bajtocji, liczbę d wszystkich odcinków dróg łączących bezpośrednio dwa różne miasta, a następnie opisy wszystkich bezpośrednich połączeń drogowych,
- układa plany tras obu gońców zaczynające się w stolicy w taki sposób, aby do każdego miasta w Bajtocji dotarł przynajmniej jeden z nich zanim obaj zostaną schwytani przez ludzi Hakera,
- zapisuje wyznaczone plany w pliku tekstowym GON.OUT.
Wejście
W pierwszym wierszu pliku tekstowego GON.IN jest zapisana jedna liczba naturalna n - jest to liczba wszystkich miast w Bajtocji. W drugim wierszu jest zapisana jedna liczba naturalna d - jest to liczba wszystkich bezpośrednich połączeń drogowych. W każdym z kolejnych d wierszy znajduje się opis jednego bezpośredniego połączenia drogowego. Opis bezpośredniego połączenia to dwie różne liczby naturalne z zakresu [1..n] oddzielone pojedynczym odstępem. Każde połączenie występuje w pliku tylko raz.
Wyjście
W pierwszym wierszu pliku tekstowego GON.OUT należy zapisać plan trasy pierwszego gońca w postaci ciągu n różnych liczb naturalnych z zakresu [1..n] pooddzielanych pojedynczym odstępem. W drugim wierszu należy zapisać w takiej samej postaci plan trasy drugiego gońca.
Przykład
Opisem przedstawionej na rysunku sieci dróg Bajtocji jest następujący plik GON.IN:
5
6
1 2
2 3
3 4
4 1
4 5
5 2
W tym przypadku poprawnym rozwiązaniem jest plik GON.OUT:
1 2 3 5 4
1 4 5 3 2
Pierwszy goniec mógłby wtedy poruszać się po drodze: 1 2 3 2 5 4, a drugi - po drodze: 1 4 5 4 3 2.
Twój program powinien szukać pliku GON.IN w katalogu bieżącym i tworzyć plik GON.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę GON.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku GON.EXE.