General of Taiko

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem C: General of Taiko

Problem

とあるゲームセンターには、曲に合わせて流れてくる譜面通りに和太鼓を叩くゲームがあります。 譜面は長さ L のセルからなり、各セルには何もない、またはノートと呼ばれるプレイヤーがとるべき行動を表した記号があります。 ノートは2種類ありそれぞれ、和太鼓の面を叩く「トン」、和太鼓の縁を叩く「コツ」があります。 これらのノートに合わせて和太鼓を叩くと得点を得ることができます。 この得点の合計が10000点以上であればクリアとなります。

このとき、プレイヤーが曲をクリアできる確率を求めなさい。ただし、プレイヤーは常に最適な行動をとることにします。

プレイヤーが譜面通りに和太鼓を叩く精度は11段階あり、それぞれ、 0%, 10%, 20%, ..., 90%, 100%の確率で譜面通りに和太鼓を叩くことができます。

上記の二種類の動作は右腕と左腕どちらででも行うことができます。 プレイヤーの情報として、それぞれの腕で行った場合の精度の安定率を表す値が16種類、下記のように与えられます。

lt_lt lt_rt lt_lk lt_rk
rt_lt rt_rt rt_lk rt_rk
lk_lt lk_rt lk_lk lk_rk
rk_lt rk_rt rk_lk rk_rk

ただし、 lt は左腕でトン, rt は右腕でトン, lk は左腕でコツ, rk は右腕でコツの動作を表します。 例えば、 lt_rk は左腕でトンのあとに右腕でコツを行った時の精度の安定の度合いを表し、この値によって左腕でトンのあとに右腕でコツを行うときの精度が、下記のように変化します。

プレイヤーの精度 = max(0, (精度の安定率 - 10) * 10 + 一つ前の精度) (%)

曲の情報は以下のとおりです。 曲の長さを表す L 、譜面を表す L 個の数字 si (0 ≤ i < L )で示される。譜面の先頭は s0 である。 si の値は以下の3つです。

0 ... ノートなし
1 ... トン
2 ... コツ

プレイヤーが最初に和太鼓を叩くときの精度は100%です。 また、プレイヤーは譜面を無視することができます。 ノートがなかったり、ノートを無視した場合、プレイヤーの精度は100%になります。

各ノートに合わせて和太鼓を叩いたときの得点は下記のようになります。

得点 = A + B * min(コンボ数, 10)

この問題におけるコンボ数とは、連続してノートに合わせて和太鼓を叩けた数です。 プレイヤーがノートに合わせて叩いた場合、上記の式を元に得点が入り、その後にコンボ数が1増えます。 ノートに合わせて和太鼓を叩けなかった場合、コンボが途切れ、コンボ数が0になります。

Input

入力は複数のデータセットからなります。 各データセットは以下のとおりです。

lt_lt lt_rt lt_lk lt_rk
rt_lt rt_rt rt_lk rt_rk
lk_lt lk_rt lk_lk lk_rk
rk_lt rk_rt rk_lk rk_rk
L
s0 s1 s2sL - 1
A B

入力の終わりは負の整数4つからなります。

Constraints

入力は以下の条件を満たします。

  • 0 < L ≤ 100
  • 0 ≤ 精度の安定率 ≤ 10
  • 精度の安定率は整数
  • 0 < A , B ≤ 10000
  • A B はともに100の倍数
  • データセットの数は100個以下

Output

各入力に対して、クリアできる確率を1行で出力しなさい。 ただし、出力は0.001以下の誤差を含んでも良いです。

Sample Input

9 0 0 0
0 9 0 0
0 0 0 0
0 0 0 0
5
1 1 1 1 1
1000 500
10 10 10 10
10 10 10 10
10 10 10 10
10 10 10 10
5
1 0 2 0 1
1000 2000
3 8 6 10
0 1 6 8
10 2 4 7
8 6 6 8
19
2 2 0 2 2 0 2 1 0 1 2 0 1 2 0 1 0 2 2
200 100
-1 -1 -1 -1

Sample Output

0.3024000000
0.0000000000
0.5120000000

Source: Ritsumeikan University Competitive Programming Camp 2013, Day1 , Problem set from University of Aizu teams, Shiga, Japan, 2013-03-11