Polish version    English version  
  History of OI -> VIII OI 2000/2001

 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
Stage III - results
Stage II - results
Stage I - results
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
VIII Olimpiada Informatyczna 2000/2001

Task: WYS
Author: Wojciech Guzicki

II stage contest, the first day  

On an island of the shape of a convex polygon with 2n sides, there are situated 2n-2 countries. Each country has a territory in the shape of triangle, which vertices are placed at the vertices of the polygon. There are no countries which border exactly with two different countries (therefore, each country borders with only one or three countries). It implies, that there are exactly n countries bordering with one country only (these are seaside countries) and n-2 countries bordering with three neighbours (these are inland countries). Seaside countries are numbered from 1 to n, inland countries have numbers from n+1 to 2n-2. When we travel from one country to another, we are obliged to pay a charge on the border. Charges may be different on different borders, but crossing a border costs the same amount of money in both directions. 

For each two countries i,j from n seaside countries, it is known how much one has to pay traveling from i to j, assuming that the land route from one country to the other through the least number of borders was chosen. The task is to find all the charges on the island. For each seaside country there should be given the number of neighbouring country and the charge on the border. Moreover, for each n-2 inland countries there should be given numbers of three neighbouring countries and the charges on borders. 


Write a program which:

  • reads from the text file WYS.IN the sums of border charges on routes between seaside countries,
  • finds for each country its neighbours,
  • computes border charges on the island,
  • writes the results in the text file WYS.OUT. 


In the first line of the text file WYS.IN there is one positive integer n, 4<=n<=100. This is the number of seaside countries. In each of the following n lines there are n non-negative integers separated by single spaces. The number di,j, on the j-th position in the i-th line, is equal to the sum of border charges on the route (through the least number of borders) from the i-th country to the j-th country. We assume that the charge on each border is an integer from the interval [1..100]. Of course, di,j=dj,i and di,i=0. 


In each of the first n lines of the text file WYS.OUT there should be written two integers separated by a single space. The first number in the i-th line should be the number of the country, which borders with the country number i. The second number is the charge on the border between these two countries. In each of the following n-2 lines there should be written six integers separated by single spaces. In the line number i, n+1<=i<=2n-1,  the first - number of the first country bordering with the i-th country, the second - the charge on their border, the third - number of the second country bordering with the i-th country, the forth - the charge on the second border, the fifth - the number of the third country bordering with the i-th country, the sixth - the charge on the third border. Inland countries are numbered from n+1 to 2n-2. 


For the input file WYS.IN: 

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

the correct answer is the output file WYS.OUT (see the picture below):

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
[ rysunek do przykładu ]

Print friendly version