VK Cup 2016 - Раунд 2 |
---|
Закончено |
Маленький Артёмка решил изучить теорию вероятностей. Он нашёл отличный задачник и прорешал его почти полностью. Однако есть задача, с которой он никак не может справиться, поэтому просит вас помочь ему.
Имеются два игральных кубика, на которых при броске выпадают целочисленные значения от 1 до n. Для каждого кубика каждое значение выпадает с некоторой фиксированной вероятностью (разумеется, сумма этих вероятностей равна 1), при этом для разных кубиков эти вероятности могут отличаться.
Оба кубика бросаются одновременно, после чего вычисляются значения max(a, b) и min(a, b), где a равно значению, выпавшему на первом кубике, а b равно значению, выпавшему на втором кубике. Вам неизвестны вероятности выпадения конкретных значений на кубиках, но вы знаете для каждого x, с какой вероятностью max(a, b) будет равно x и с какой вероятностью min(a, b) будет равно x. Восстановите любое корректное распределение вероятностей для величин a и b. Гарантируется, что хотя бы одно подходящее распределение существует.
Первая строка входных данных содержит единственное целое число n (1 ≤ n ≤ 100 000) — количество возможных значений на обоих кубиках.
Во второй строке записан массив из n вещественных чисел с не более чем восемью цифрами после десятичной точки — распределение вероятности для величины max(a, b), то есть i-е из этих числе равно вероятности того, что max(ab) = i. Гарантируется, что сумма чисел в массиве равна 1. В третей строке записано распределение вероятности для min(a, b) в аналогичном формате.
Выведите два описания распределений вероятности для величины a (первый кубик) на первой строке и для величины b (второй кубик) на второй строке.
Ваш ответ будет считаться правильным, если вероятность каждого значения max(a, b) и min(a, b), вычисленная по предоставленным вами распределениям, будет отличаться от указанных во входных данных не более чем на 10 - 6 по абсолютному значению. Вероятности должны быть неотрицательными вещественными числами, сумма вероятностей внутри одного распределения должна отличаться от 1 не более чем на 10 - 6.
2
0.25 0.75
0.75 0.25
0.5 0.5
0.5 0.5
3
0.125 0.25 0.625
0.625 0.25 0.125
0.25 0.25 0.5
0.5 0.25 0.25
Название |
---|