{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:27.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/5850ded3563caaf974035b3f431aad07?v\u003d1715635052\" alt\u003d\"/problems/optimistan/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eOptimistan is a strange country. It is situated on an island\n with a huge desert in the middle, so most people live in port\n towns along the coast. As the name suggests, people of\n Optimistan (also called Optimists) like to optimise everything,\n so they only built roads necessary to connect all port towns\n together and not a single extra road. That means that there is\n only one way to get from one port town to another without\n visiting the same place twice.\u003c/p\u003e\n\n \u003cp\u003eThe government installed multi-directional distance signs in\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e-kilometre intervals on\n one side of the road, to provide important information to\n drivers. Thus whenever you go from one port town to another,\n you pass the first sign at the port town and then one each\n kilometre. Every distance sign contains the shortest distances\n to all port towns, each written on a separate small sign\n directed towards the goal town.\u003c/p\u003e\n\n \u003cp\u003eThe signs also serve another important function: to guide\n drivers on intersections. This means that distance of each\n intersection from every port town is an integer number of\n kilometres.\u003c/p\u003e\n\n \u003cp\u003eYou bought a tourist guide of Optimistan which does not have\n a map of the country, but it contains a huge table with the\n shortest distances between all pairs of port towns. You quickly\n calculated the average shortest distance between all pairs of\n port towns, but then you started wondering: if the signs also\n contained shortest distances to all other signs, what would be\n the average number written on a sign? Could this be calculated\n just from the distance table in the tourist guide?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\le n \\le 500$\u003c/span\u003e), the number of\n ports;\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e lines, the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth of which\n contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n-i$\u003c/span\u003e\n integers. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003eth\n integer on the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth\n line denotes the distance between port \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and port \u003cspan class\u003d\"tex2jax_process\"\u003e$i+j$\u003c/span\u003e in kilometres. Each distance\n is between \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10^6$\u003c/span\u003e\n (inclusive).\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eYou can assume that the distances correspond to a road\n network in which there is exactly one path between two port\n towns that does not visit the same place twice. All roads can\n be used in both directions.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput one line with the average distances in kilometres\n between all pairs of distance signs in Optimistan. Your answer\n should have an absolute or relative error of at most\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-9}$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eIf it is impossible to determine the exact average of\n distances between all pairs of distance signs in Optimistan,\n output ā\u003ctt class\u003d\"tt\"\u003eimpossible\u003c/tt\u003eā.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4 4\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.13333333333333\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n2 2 2\n2 2\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}