/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
あなたは 4 \times 4 のグリッドを使って的あてゲームをしています。
グリッドの上から i 行目、左から j 列目のマスには、S_{i,j} が . のとき的はなく、# のとき的があります。全ての的に 1 度以上ボールを当てるとゲームクリアです。
あなたがあるマスを狙ってボールを投げると、狙ったマスか 1 マス分上下左右にズレた場所(グリッド外も含む)にそれぞれ \dfrac{1}{5} の確率で飛んでいき、そこに的があれば当たります。
ゲームの進行に伴い狙うマスを適切に選択するとき、ゲームをクリアするまでにボールを投げる回数の期待値は最小でいくらになりますか？
制約
- S_{i,j} は
.または# - S_{i,j} のうち少なくとも 1 個は
#である
入力
入力は以下の形式で標準入力から与えられる。
S_{1,1}S_{1,2}S_{1,3}S_{1,4}
S_{2,1}S_{2,2}S_{2,3}S_{2,4}
S_{3,1}S_{3,2}S_{3,3}S_{3,4}
S_{4,1}S_{4,2}S_{4,3}S_{4,4}
出力
ボールを投げる回数の期待値の最小値を出力せよ。
正しい値との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とみなされる。
入力例 1
#... .... .... ....
出力例 1
5.0000000000
的にボールが当たるまでの回数の期待値は 5 です。グリッドの外へボールが飛んでいくこともあります。
入力例 2
#... #... .... ....
出力例 2
7.5000000000
2 つある的のどちらかにボールが当たるまでは、上の的を狙います。一方の的に当たったあとは、残りの的を狙います。
入力例 3
.#.. #.#. .#.. ....
出力例 3
10.4166666667
最初のうちは 4 つの的の中央にある、的のないマスを狙うのが最適です。
入力例 4
###. #### #### ####
出力例 4
32.5674089515
Score : 6 points
Warning
Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
You are playing the game "Hit the Targets" with a 4 \times 4 grid.
The square at the i-th row from the top and j-th column from the left contains a target if S_{i, j} is #, and it does not if S_{i, j} is .. You win the game when you hit every target with a ball once or more.
When you throw a ball aiming at some square x, the ball flies to one of the following five squares, each with probability \dfrac{1}{5}: x itself and the four squares vertically or horizontally adjacent to x. (Assume that there are empty squares outside the grid.) If that square contains a target, the ball hits it.
What is the expected value of the number of throws before winning the game, assuming that you always make the optimal choice to minimize this value during the game?
Constraints
- S_{i,j} is
.or#. - At least one of the characters S_{i,j} is
#.
Input
Input is given from Standard Input in the following format:
S_{1,1}S_{1,2}S_{1,3}S_{1,4}
S_{2,1}S_{2,2}S_{2,3}S_{2,4}
S_{3,1}S_{3,2}S_{3,3}S_{3,4}
S_{4,1}S_{4,2}S_{4,3}S_{4,4}
Output
Print the minimized expected value of the number of throws.
Your output will be accepted if its absolute or relative error from the correct answer is at most 10^{-6}.
Sample Input 1
#... .... .... ....
Sample Output 1
5.0000000000
The expected number of throws before hitting the target is 5. Note that balls can miss the grid.
Sample Input 2
#... #... .... ....
Sample Output 2
7.5000000000
Until a ball hits one of the two targets, we will aim at the upper target, and then we will aim at the remaining target.
Sample Input 3
.#.. #.#. .#.. ....
Sample Output 3
10.4166666667
In the beginning, it is optimal to aim at the empty square at the center of the four targets.
Sample Input 4
###. #### #### ####
Sample Output 4
32.5674089515