VIII Olimpiada Informatyczna 2000/2001
|
Zadanie: WYS
|
Autor: Wojciech Guzicki
|
Zawody II stopnia, dzień pierwszy | 7 luty 2001 |
Plik źródłowy: | WYS.??? (np. pas, c, cpp) |
Plik wykonywalny: | WYS.exe |
Plik wejściowy: | WYS.in |
Plik wyjściowy: | WYS.out |
Na wyspie o kształcie wielokąta wypukłego o 2n bokach, znajduje się 2n-2 państw --- trójkątów, których wierzchołki są jednocześnie wierzchołkami wielokąta. Nie ma państw graniczących dokładnie z dwoma innymi państwami (zatem każde państwo graniczy albo tylko z jednym państwem, albo z trzema). Wynika stąd, że istnieje dokładnie n państw graniczących tylko z jednym państwem (są to państwa nadmorskie) oraz n-2 państw graniczących z trzema sąsiadami (są to państwa wewnątrzlądowe). Państwa nadmorskie są ponumerowane liczbami od 1 do n, natomiast państwa wewnątrzlądowe mają numery od n+1 do 2n-2. Gdy podróżujemy z jednego państwa do drugiego, to za przekroczenie każdej granicy musimy zapłacić ustaloną stawkę. Poszczególne stawki mogą być różne, ale przekroczenie granicy w obu kierunkach kosztuje tyle samo.
Dla każdych dwóch państw, spośród n państw nadmorskich, znana jest suma opłat granicznych na drodze prowadzącej (lądem) od jednego państwa do drugiego przez najmniejszą liczbę granic. Zadanie polega na wyznaczeniu wszystkich opłat granicznych na całej wyspie. Dla każdego państwa nadmorskiego należy podać numer państwa, z którym ono graniczy, oraz wysokość odpowiedniej opłaty granicznej. Ponadto, dla każdego z n-2 państw wewnątrzlądowych należy podać numery trzech państw, z którymi ono graniczy, oraz wysokości opłat na granicach z tymi państwami.
7 0 8 10 8 13 11 14 8 0 8 10 11 5 12 10 8 0 12 5 11 6 8 10 12 0 15 13 16 13 11 5 15 0 14 3 11 5 11 13 14 0 15 14 12 6 16 3 15 0poprawną odpowiedzią jest plik wyjściowy WYS.OUT (zobacz też rysunek obok):
12 3 10 1 9 1 12 5 8 1 10 4 8 2 5 1 7 2 9 3 3 1 8 3 11 4 2 1 6 4 11 2 9 4 10 2 12 2 1 3 4 5 11 2 |