Полное решение будет оценено в 3 балла.
В игре «Подземелья и радуги» используются кубики разной формы и с разным количеством граней. Игровой процесс заключается в перемещении по нескольким подземельям и выполнении различных действий. Суммарно в игре $$$n$$$ состояний: различные положения, имеющиеся предметы и т. д. Для каждого из состояний правила игры определяют, какой игровой кубик нужно бросить, чтобы узнать, в какое состояние перейдет игра (или останется в том же состоянии). Игровой кубик может иметь более $$$n$$$ граней, поэтому дополнительно правила определяют, сколько граней этого кубика соответствует переходам в каждое состояние.
Например, в игре с тремя состояниями в одном из них может быть доступен кубик с пятью гранями. Для перехода в состояние 1 будут использоваться две его грани, в состояние 2 — одна грань, а в состояние 3 — две грани.
Игроки начинают в состоянии 1 и игра длится $$$k$$$ раундов. Для того, чтобы игра закончилась изумительным финалом, игроки должны в последнем раунде попасть в состояние $$$s$$$. Попадания в это состояние в промежуточных раундах не имеют значения.
Опытный ведущий знает вероятности выпадения каждой грани каждого кубика. В каждом раунде он может выбирать, какие грани кубика будут соответствовать каким исходам, то есть ведущий назначает для каждой грани кубика переход в состояние на следующий раунд. Если игроки попали в одно и то же состояние несколько раз, он может сделать разный выбор в каждом случае.
Ведущий хочет, чтобы игра закончилась изумительным финалом с максимальной вероятностью. Вычислите эту вероятность при оптимальных действиях ведущего.
В первой строке дано число состояний $$$n$$$ ($$$2 \le n \le 1000$$$), число раундов игры $$$k$$$ ($$$1 \le k \le 100$$$) и номер состояния с изумительным финалом $$$s$$$ ($$$1 \le s \le n$$$).
В следующих $$$n$$$ строках даны описания кубиков и правила переходов из каждого состояния. Первые $$$n$$$ чисел строки $$$i$$$ задают количество граней кубика $$$F_{ij}$$$ ($$$0 \le F_{ij} \le 1000$$$), которые соответствуют переходам из состояния $$$i$$$ в каждое из $$$n$$$ состояний. Далее в этой же строке дан знаменатель $$$Q_i$$$ ($$$\sum_j F_{ij} \le Q_i\le 10^6$$$) вероятностей выпадений граней кубика. А за ним $$$\sum_j F_{ij}$$$ числителей $$$P_{ij}$$$ ($$$1 \le P_{ij} \le Q_i$$$) вероятностей выпадения каждой грани кубика.
Общее число граней каждого кубика удовлетворяет ограничениям $$$2 \le \sum_j F_{ij}\le 1000$$$, а сумма вероятностей выпадения всех граней равна $$$1$$$.
Выведите максимальную вероятность получения изумительного финала при оптимальных действиях ведущего с абсолютной погрешностью, не превосходящей $$$10^{-9}$$$.
2 1 2 1 1 3 1 2 1 1 3 2 1
0.666666666667
3 3 3 1 1 0 3 2 1 0 1 1 3 2 1 1 0 1 3 2 1
0.592592592593
2 2 2 2 1 4 1 2 1 2 1 4 1 1 2
0.5
| 2021-2022 ICPC, Moscow Subregional |
|---|
| Закончено |
