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ą.
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.