#joi2006yoe. [joi2006yo_e]JOI 2006 予選 問題5

[joi2006yo_e]JOI 2006 予選 問題5

問題

次のようなゲームを考える.11 から nn までの数が 11 つずつ書かれた nn 枚のカードが kk 組ある.これら knkn 枚のカードをよくシャッフル(よく切ること)して,kk 枚ずつの山を作り横一列に並べる.このようにしてできる nn 個の山の左から ii 番目の(kk 枚のカードの)山を「山 ii」と呼ぶことにする.

2006-yo-t5-fig_base.png

ゲームは山 11 から始める.山の一番上のカード 11 枚を引き(引いたカードは元の山に戻さない),そのカードに書かれていた数が ii だった場合には山 ii の一番上のカード 11 枚を引く.このようにして,引いたカードに書かれていた数を番号とする山の一番上のカード 11 枚を引くことを繰り返し,すべての山にカードが無くなれば成功である.まだカードが残っている山があるのに,次にカードを引くべき山が無くなっていた場合は失敗である.

途中で失敗した場合には,そのまま失敗で終了するか,または残ったカードの山をそのまま(山の番号もそのまま)にしてゲームを再開する.ゲームを再開する場合は,最初に引くカードはカードが残っている山のうちの一番左の山からとする(その山の一番上のカードが最初に引かれるカードとなる).再開後も再開前と同様の方法でゲームを進め,すべての山にカードが無くなれば成功であり,まだカードが残っている山があるのに,次にカードを引くべき山が無くなった場合は失敗である.

2006-yo-t5-fig_sample.png

このようなゲームの再開を最大 mm 回まで行うものとする.ただし,mm0011 である.つまり,11 回も再開しないか,11 回だけ再開するかのいずれかである.ゲーム開始前のシャッフルの仕方によりカードの初期配置は異なる.当然,カードの初期配置により,再開せずに成功することもあれば,再開して成功することも,再開して失敗することもある.十分シャッフルしているので,どの初期配置も全て同じ確率で現れるものと考えることにして,再開が mm 回以内で成功する確率 pp を求めたい.この確率 pp を小数で表し,小数第 rr 位まで求めて出力するプログラムを作りなさい.ただし,次の条件を満たすように出力すること.

十分大きい正整数 KK を取ると ptimes10Kp \\times 10^K が 整数となる場合,小数部は途中から 00 が続くが,その 00 も出力すること.例えば,p=3/8=0.375p = 3/8 = 0.375 の場合,r=5r = 5 なら 0.375000.37500 と出力し,r=2r = 2 なら 0.370.37 と出力する.p=1.0p = 1.0 の場合も同様に,例えば r=3r = 3 なら 1.0001.000 と出力すること. 例えば 0.150000cdots0.150000\\cdots は循環小数 0.1499999cdots0.1499999\\cdots として表すこともできるが,このような場合,前者の表し方を用いる. 入力の 11 行目には整数 n,k,m,rn, k, m, r がこの順に空白を区切り文字として書いてある.1leqqnleqq10,0001 \\leqq n \\leqq 10\\,0001leqqkleqq1001 \\leqq k \\leqq 100m=0m = 0 または m=1m = 11leqqrleqq10,0001 \\leqq r \\leqq 10\\,000 である.

出力においては,指定通りに出力した pp の後に改行を入れること.


入力例 1

2 1 0 5

出力例 1

0.50000

入力例 2

3 1 1 3

出力例 2

0.833

入力例 3

2 2 1 3

出力例 3

1.000