Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Olimpiada Informatyczna 1995/96

Zadanie: GON
Autor: Krzysztof Diks
Gońcy

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

rysunek - graf o 5 wierzchołkach

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.




Wersja do druku