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
VIII Olimpiada Informatyczna 2000/2001

Zadanie: ZWI
Autor: Krzysztof Onak
Zwiedzanie miasta

Zawody III stopnia, dzień pierwszy 27 marzec 2001
Plik źródłowy: ZWI.??? (np. pas, c, cpp)
Plik wykonywalny: ZWI.exe
Plik wejściowy: ZWI.in
Plik wyjściowy: ZWI.out

Bajtocka Agencja Turystyczna (w skrócie BAT) chce wejść na rynek oferując zwiedzanie Bajtogrodu autobusem-kabrioletem. Należy zbudować siedzibę firmy, w której będzie się zaczynało i kończyło zwiedzanie. Trasa zwiedzania musi przechodzić wszystkimi ulicami miasta, w przeciwnym przypadku turyści mogliby podejrzewać, że nie zobaczyli czegoś bardzo interesującego. Ulice nie muszą być proste i mogą przebiegać tunelami lub wiaduktami. Wszystkie ulice są dwukierunkowe. Każda ulica łączy dwa skrzyżowania. Z każdego skrzyżowania w czterech kierunkach wychodzą ulice. Może się zdarzyć, że dwa skrzyżowania są połączone więcej niż jedną ulicą. Na ulicach nie wolno zawracać, ale można to robić na skrzyżowaniach. Ponadto wiadomo, że z każdego skrzyżowania da się dojechać do każdego innego. Przy każdej ulicy, dokładnie w połowie drogi pomiędzy skrzyżowaniami, które łączy ulica, znajduje się szczególnie godna podziwu atrakcja turystyczna (np. piękny widok, pomnik lub inny zabytek), wywierająca na zwiedzających "wrażenie" określone nieujemną liczbą całkowitą. Siedziba BATu powinna znajdować się przy jednej z takich atrakcji. Przy doborze trasy zwiedzania należy brać pod uwagę zainteresowanie turystów, które może się zmieniać w trakcie zwiedzania. Przejechanie autobusem jednej bajtomili powoduje spadek zainteresowania o jeden. Przejechanie po raz pierwszy obok danej atrakcji turystycznej zwiększa zainteresowanie turystów, o liczbę określająca wrażenie, jakie robi atrakcja. Początkowo poziom zainteresowania turystów jest równy wrażeniu, jakie robi atrakcja, przy której znajduje się siedziba BATu. Zainteresowanie turystów nie może w trakcie wycieczki nigdy spaść poniżej zera.

Zadanie

Napisz program, który:
  • wczyta opis miasta z pliku tekstowego zwi.in,
  • znajdzie trasę spełniającą podane wymagania, lub stwierdzi, że taka trasa nie istnieje,
  • zapisze wynik do pliku tekstowego zwi.out.

Wejście

W pierwszym wierszu pliku tekstowego zwi.in znajduje się jedna liczba całkowita n określająca liczbę skrzyżowań, 1<n<=10 000. Skrzyżowania są ponumerowane od 1 do n, a ulice są ponumerowane od 1 do 2n. Kolejnych 2n wierszy opisuje ulice -- (i+1)-szy wiersz w pliku opisuje ulicę o numerze i. W każdym wierszu znajdują się cztery liczby całkowite a, b, l, s oddzielone pojedynczymi odstępami. Liczby a i b to numery skrzyżowań, które łączy dana ulica, 1<=a,b<=n, a<>b. Liczba l jest parzystą liczbą całkowitą będącą długością ulicy w bajtomilach, 2<=l<=1 000. Atrakcja turystyczna położona przy danej ulicy robi wrażenie określone liczbą s, 0<=s<=1 000.

Wyjście

Pierwszy wiersz pliku tekstowego zwi.out powinien zawierać jedno słowo TAK, jeżeli istnieje taka trasa, lub NIE, w przeciwnym przypadku. Jeśli odpowiedź jest pozytywna to kolejne wiersze powinny opisywać przykładową trasę. Drugi wiersz powinien zawierać dokładnie jedną liczbę całkowitą k równą liczbie skrzyżowań występujących na trasie zwiedzania. (Pamiętaj, że ulica, przy której ma znajdować się siedziba BATu łączy pierwsze i ostatnie skrzyżowanie). Oznaczmy przez si (dla i=1,2,...,k) numer ulicy, którą podczas zwiedzania dojeżdża się do i-tego (w kolejności zwiedzania) skrzyżowania. Kolejny wiersz powinien zawierać dwie liczby całkowite s1 i d równe odpowiednio numerowi ulicy, przy której należy zbudować siedzibę BATu oraz numerowi pierwszego skrzyżowania, przez które prowadzi trasa zwiedzania. Kolejne k-1 wierszy powinno zawierać po jednej liczbie całkowitej, odpowiednio s2, s3, ..., sk.

Przykład

Dla pliku wejściowego zwi.in:
4
1 2 4 6
2 4 2 4
3 2 4 2
4 3 10 8
2 1 8 7
4 3 2 1
1 4 2 6
3 1 4 5
poprawną odpowiedzią jest plik wyjściowy zwi.out
TAK
8
5 2
2
6
3
1
8
4
7



Wersja do druku