VIII Olimpiada Informatyczna 2000/2001
|
Zadanie: ZWI
|
Autor: Krzysztof Onak
|
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.
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 5poprawną odpowiedzią jest plik wyjściowy zwi.out
TAK 8 5 2 2 6 3 1 8 4 7