Olimpiada Informatyczna

Historia OI -> VIII OI 2000/2001 -> Zadania

SIO

MAIN

VIII Olimpiada Informatyczna 2000/2001

Zadanie: WYS

Autor: Wojciech Guzicki

Wyspa

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.

Zadanie

Napisz program, który:

wczyta z pliku tekstowego WYS.IN sumy opłat granicznych na drogach pomiędzy poszczególnymi państwami nadmorskimi,
obliczy opłaty graniczne na całej wyspie i wyznaczy, które państwa sąsiadują z którymi,
zapisze wyniki w pliku tekstowym WYS.OUT.

Wejście

W pierwszym wierszu pliku tekstowego WYS.IN znajduje się jedna dodatnia liczba całkowita n, 4<=n<=100. Jest to liczba państw nadmorskich. W każdym z następnych n wierszy znajduje się n nieujemnych liczb całkowitych oddzielonych pojedynczymi odstępami. Liczba d_i,j, stojąca na j-tym miejscu w i-tym z tych wierszy, jest równa sumie opłat granicznych na drodze prowadzącej (lądem, przez najmniejszą liczbę granic) z państwa o numerze i do państwa o numerze j. Zakładamy przy tym, że na każdej granicy opłata graniczna jest liczbą całkowitą z przedziału [1..100]. Oczywiście, d_i,j=d_j,i oraz d_i,i=0.

Wyjście

W pierwszych n wierszach pliku tekstowego WYS.OUT należy zapisać po dwie liczby całkowite oddzielone pojedynczym ostępem. Pierwszą liczbą w i-tym wierszu powinien być numer państwa graniczącego z państwem o numerze i, a drugą wysokość opłaty granicznej na granicy między tymi dwoma państwami. W każdym z następnych n-2 wierszy należy zapisać po sześć liczb oddzielonych pojedynczymi odstępami. W wierszu o numerze i (licząc od początku pliku, a więc i>n) pierwszą liczbą ma być numer pierwszego państwa graniczącego z państwem o numerze i, drugą ma być wysokość opłaty granicznej na tej granicy, trzecią ma być numer drugiego państwa graniczącego z państwem o numerze i, czwartą wysokość opłaty granicznej na drugiej granicy, piątą ma być numer trzeciego państwa graniczącego z państwem o numerze i, szóstą ma być wysokość opłaty granicznej na trzeciej granicy. Państwa wewnątrzlądowe mogą być ponumerowane dowolnie liczbami od n+1 do 2n-2.

Przykład

Dla pliku przykładowego WYS.IN:

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 0

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

Wersja do druku