| 第５回日本情報オリンピック 予選 |
|
|
2006年1月15日
情報オリンピック日本委員会
|
次のようなゲームを考える． 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 位まで求めて出力するプログラムを作りなさい． ただし， 次の条件を満たすように出力すること．
入力ファイルの 1 行目には整数 n，k，m，r がこの順に空白を区切り文字として書いてある． 1 ≦ n ≦ 10000， 1 ≦ k ≦ 100， m = 0 または m = 1， 1 ≦ r ≦ 10000 である．
アップロードする出力ファイルにおいては， 指定通りに出力した p の後に改行を入れること．
| 入力例１ | 入力例２ | 入力例３ | |
|---|---|---|---|
| 2 1 0 5 | 3 1 1 3 | 2 2 1 3 | |
| 出力例１ | 出力例２ | 出力例３ | |
| 0.50000 | 0.833 | 1.000 |