Card Game II

Time Limit : 5 sec, Memory Limit : 65536 KB

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

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

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

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

  • 十分大きい正整数 K を取ると p×10K が 整数となる場合, 小数部は途中から 0 が続くが,その 0 も出力すること. 例えば, p = 3/8 = 0.375 の場合, r = 5 なら 0.37500 と出力し, r = 2 なら 0.37 と出力する. p = 1.0 の場合も同様に, 例えば r = 3 なら 1.000 と出力すること.
  • 例えば 0.150000… は循環小数 0.1499999… として表すこともできるが, このような場合, 前者の表し方を用いる.

入力ファイルの 1 行目には整数 n,k,m,r がこの順に空白を区切り文字として書いてある. 1 ≦ n ≦ 10000, 1 ≦ k ≦ 100, m = 0 または m = 1, 1 ≦ r ≦ 10000 である.

 アップロードする出力ファイルにおいては, 指定通りに出力した p の後に改行を入れること.

入力例1 入力例2 入力例3
2 1 0 53 1 1 32 2 1 3
 
出力例1 出力例2 出力例3
0.500000.8331.000

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Notes on Submission

標準入出力を行うプログラムを作成して下さい。

上記の形式で複数のデータセットが与えられます。n, k, m, r がすべて0のとき入力が終了します。

Sample Input

2 1 0 5
3 1 1 3
2 2 1 3
0 0 0 0

Sample Output

0.50000
0.833
1.000

Source: Japanese Olympiad in Informatics, Preliminary Round , 2006-01-15
http://www.ioi-jp.org/