Problem D
Driving in Optimistan

Multi-directional distance sign. Picture licensed CC0 Public Domain.

Optimistan is a strange country. It is situated on an island with a huge desert in the middle, so most people live in port towns along the coast. As the name suggests, people of Optimistan (also called Optimists) like to optimise everything, so they only built roads necessary to connect all port towns together and not a single extra road. That means that there is only one way to get from one port town to another without visiting the same place twice.

The government installed multi-directional distance signs in $1$-kilometre intervals on one side of the road, to provide important information to drivers. Thus whenever you go from one port town to another, you pass the first sign at the port town and then one each kilometre. Every distance sign contains the shortest distances to all port towns, each written on a separate small sign directed towards the goal town.

The signs also serve another important function: to guide drivers on intersections. This means that distance of each intersection from every port town is an integer number of kilometres.

You bought a tourist guide of Optimistan which does not have a map of the country, but it contains a huge table with the shortest distances between all pairs of port towns. You quickly calculated the average shortest distance between all pairs of port towns, but then you started wondering: if the signs also contained shortest distances to all other signs, what would be the average number written on a sign? Could this be calculated just from the distance table in the tourist guide?


The input consists of:

  • one line with an integer $n$ ($2 \le n \le 500$), the number of ports;

  • $n-1$ lines, the $i$th of which contains $n-i$ integers. The $j$th integer on the $i$th line denotes the distance between port $i$ and port $i+j$ in kilometres. Each distance is between $1$ and $10^6$ (inclusive).

You can assume that the distances correspond to a road network in which there is exactly one path between two port towns that does not visit the same place twice. All roads can be used in both directions.


Output one line with the average distances in kilometres between all pairs of distance signs in Optimistan. Your answer should have an absolute or relative error of at most $10^{-9}$.

If it is impossible to determine the exact average of distances between all pairs of distance signs in Optimistan, output “impossible”.

Sample Input 1 Sample Output 1
4 4
Sample Input 2 Sample Output 2
2 2 2
2 2

Please log in to submit a solution to this problem

Log in