D - インフレゲーム
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
A + B + C 枚のカードがある。そのうち A 枚にはそれぞれ赤い数字で整数が 1 つ書かれている。別の B 枚にはそれぞれ青い数字で整数が 1 つ書かれている。残りの C 枚にはそれぞれ "湯たんぽ" が書かれている。高橋君はこれらのカードを用いて、以下の手順に従いゲームを行う。
- 1. A + B + C 枚のカードを一束にまとめ、偏りなくシャッフルしてテーブルの上に置き、山札とする。
- 2. 高橋君の得点を 0 とする。
- 3. 山札から一番上のカードを引く。
- 3-A. 引いたカードに赤い数字で整数が書かれていた場合、その整数を a として高橋君の得点が a だけ増加する。
- 3-B. 引いたカードに青い数字で整数が書かれていた場合、その整数を b として高橋君の得点が b 倍になる。
- 3-C. 引いたカードに "湯たんぽ" が書かれていた場合、ゲームオーバーである。その時点での高橋君の得点を高橋君の最終得点とし、ゲームを終了する（下記の手順 4 は行わない）。
- 4. 引いたカードを破り捨て、手順 3 を再び行う。
高橋君の最終得点の期待値を求めよ。
入力
入力は以下の形式で標準入力から与えられる。
A B C a_1 a_2 .. a_A b_1 b_2 .. b_B
- 1 行目には、3 個の整数 A, B, C (1 ≦ A, B, C ≦ 50) がスペース区切りで与えられる。これらはそれぞれ、赤い数字で整数が書かれたカードの枚数、青い数字で整数が書かれたカードの枚数、"湯たんぽ" が書かれたカードの枚数を表す。（ここで C ≧ 1 であることから、ゲームは必ず問題文の手順 3-C により終了する。）
- 2 行目には、赤い数字で整数が書かれたカード A 枚に書かれた A 個の整数 a_1, a_2, ..., a_A (1 ≦ i ≦ A なる各 i に対し 1 ≦ a_i ≦ 100) がスペース区切りで与えられる。
- 3 行目には、青い数字で整数が書かれたカード B 枚に書かれた B 個の整数 b_1, b_2, ..., b_B (1 ≦ i ≦ B なる各 i に対し 1 ≦ b_i ≦ 100) がスペース区切りで与えられる。
部分点
この問題には部分点が設定されている。
- 5 点分のテストケースは 1 ≦ A, B, C ≦ 3 を満たす。
- 別の 15 点分のテストケースは 1 ≦ A, B, C ≦ 8 を満たす。
- さらに別の 20 点分のテストケースは 1 ≦ A, C ≦ 50, 1 ≦ B ≦ 8 を満たす。
出力
高橋君の最終得点の期待値を 1 行目に出力せよ。審判の出力との絶対誤差または相対誤差が 10-6 以下であるとき正答とみなされる。指数表記で出力してもよい。
末尾の改行を忘れないこと。
入力例1
1 1 1 10 2
出力例1
6.666666666666666667
赤い数字で 10 が書かれたカード、青い数字で 2 が書かれたカード、"湯たんぽ" が書かれたカードがそれぞれ 1 枚ずつ、合計で 3 枚のカードがある。これら 3 枚のカードが偏りなくシャッフルされて山札となる。山札でカードが上から「赤、青、湯たんぽ」の順に並ぶと、最終得点は (0 + 10) × 2 = 20 となり、その確率は 1/6 である。順番が「赤、湯たんぽ、青」または「青、赤、湯たんぽ」の場合、最終得点はそれぞれ 0 + 10, 0 * 2 + 10 でいずれも 10 となり、その確率は合計で 1/6 + 1/6 = 2/6 である。これら以外の順番にカードが並ぶと最終得点は 0 となる。従って、最終得点の期待値は 20 × 1/6 + 10 × 2/6 = 20/3 である。
入力例2
4 1 1 1 1 1 3 2
出力例2
4
入力例3
7 2 2 1 1 1 1 5 5 5 5 5
出力例3
29.13333333333333333
入力例4
20 8 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8
出力例4
19030.73484848484849
入力例5
15 15 1 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
出力例5
5.626676749671402077e+030
このように指数表記で出力してもよい。