No.3615 Ge Gusser
タグ : / 解いたユーザー数 30
作問者 :
kazuppa
/ テスター :
Problem Statement
Kazuppa is playing a certain game. The game proceeds as follows.
- The game has $M$ maps implemented, and $1$ of them is chosen as the answer.
- In each game, there are $N$ areas that can be visited. The information of area $i$ is represented by a string $S_i$ of length $M$ consisting of
oandx. If $S_{i,j}=$o, the information of area $i$ tells that "the answer may be map $j$", and if $S_{i,j}=$x, the information of area $i$ tells that "the answer cannot be map $j$". Here, it is guaranteed that the answer is uniquely determined once all $N$ areas have been visited. Also, the player cannot know the information $S_i$ until visiting area $i$. - The player starts from any location, moves by choosing various areas, and can answer which map is the answer exactly once. The player becomes happy if the answer is correct, and unhappy if it is wrong.
Kazuppa has decided to play this game with the following strategy.
- He absolutely does not want to be unhappy, so he does not answer until the answer is uniquely determined. Also, since he is impatient, he answers as soon as the answer is uniquely determined.
- He does not understand the optimal play of this game, so he starts by choosing $1$ random area, and each time he moves, he randomly chooses $1$ area he has not visited yet and moves there.
Define the score of this game as the number of areas visited (including the starting area). Find the expected value of the score when Kazuppa plays with his strategy.
Constraints
- $1\leq N\leq 22$
- $2\leq M\leq 50$
- $S_i$ is a string of length $M$ consisting of
oandx - There exists exactly one $j$ such that "$S_{i,j}=$
ofor every $i$" - $N,M$ are integers
Subtasks
This problem has partial scores set by subtasks.
| Subtask Name | Points | Constraints |
|---|---|---|
| Subtask 1 | 100 points | $N\leq 6$ |
| Subtask 2 | 100 points | $N\leq 18$ |
| Subtask 3 | 50 points | No additional constraints |
Input
$N\ M$ $S_1$ $S_2$ $\vdots$ $S_N$
Output
Print the answer on one line.
Your answer is judged as correct if the absolute or relative error from the true value is at most $10^{-6}$.
Sample
Sample 1
Input
2 2 oo ox
Output
1.5
If he starts from map $1$, the answer is not unique at that point, so he moves to map $2$. Here the answer is uniquely determined, so the score is $2$.
If he starts from map $2$, the answer is uniquely determined at this point, so the score is $1$.
Therefore, the answer is $\frac{1+2}{2}=1.5$.
Sample 2
Input
3 3 xox xox xox
Output
1
Sample 3
Input
5 5 ooxoo xoooo oxooo oooox ooooo
Output
4.8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。