Wyspa

Limit pamięci: 32 MB

Na wyspie o kształcie wielokąta wypukłego o bokach, znajduje się 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 państw graniczących tylko z jednym państwem (są to państwa nadmorskie) oraz państw graniczących z trzema sąsiadami (są to państwa wewnątrzlądowe). Państwa nadmorskie są ponumerowane liczbami od do , natomiast państwa wewnątrzlądowe mają numery od do .

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 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 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 ze standardowego wejścia 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,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita , . Jest to liczba państw nadmorskich. W każdym z następnych wierszy znajduje się nieujemnych liczb całkowitych oddzielonych pojedynczymi odstępami. Liczba , stojąca na -tym miejscu w -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 do państwa o numerze . Zakładamy przy tym, że na każdej granicy opłata graniczna jest liczbą całkowitą z przedziału . Oczywiście, oraz .

Wyjście

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

Przykład

Dla danych wejściowych:

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:

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

Autor zadania: Wojciech Guzicki.