Both my AC submissions answer wrong (locally) on test,
which is generated by following code:

int n = (int)1e5;
printf("%d %d\n", n, n);
printf("1 %d\n", n);
printf("1 2 97\n");
printf("1 3 98\n");

for (int i = 2; i <= n - 2; i++)
   printf("%d %d %d\n", i, i + 2, 99);
printf("%d %d 98\n", n - 1, n);

To be exact, they answer
50001 1.0000000
1 2 ... n-2 n

On the other side, answer is obviously path
1 3 ... n-1 n, because probability to not meet Kraken is (4 / 100^(n/2)) for it
and (3 / 100^(n / 2)) for path 1, 2, ...

By the way, it is far from the worst test. Actually, any test like this
(with two diverging paths of same length), but where difference between products
of (1 - probability of meeting Kraken) on edges of paths is 1 and these products
are big is going to be much, much worse.

P. S. If I am misunderstanding something (for example, 10^(-6) error is allowed for
answer, not only for output (though even if it is true, it is not clear from
Russian problem statement)), then I am very sorry.

P. P. S. In hindsight it looks like statement is a bit unclear, but tests are OK
(it looks like checker does allow any path with probability to meet Kraken not more
than 10^(-6) + lowest probability), but formally, it is said in statement that path
should be optimal, just answer can be written with some error). If it is so, I
apologize for "wrong call", but I still would like to see some tweaks to statement.

Edited by author 30.07.2014 04:29