#joi2006yoe. [joi2006yo_e]JOI 2006 予選 問題5
[joi2006yo_e]JOI 2006 予選 問題5
問題
次のようなゲームを考える. から までの数が つずつ書かれた 枚のカードが 組ある.これら 枚のカードをよくシャッフル(よく切ること)して, 枚ずつの山を作り横一列に並べる.このようにしてできる 個の山の左から 番目の( 枚のカードの)山を「山 」と呼ぶことにする.
ゲームは山 から始める.山の一番上のカード 枚を引き(引いたカードは元の山に戻さない),そのカードに書かれていた数が だった場合には山 の一番上のカード 枚を引く.このようにして,引いたカードに書かれていた数を番号とする山の一番上のカード 枚を引くことを繰り返し,すべての山にカードが無くなれば成功である.まだカードが残っている山があるのに,次にカードを引くべき山が無くなっていた場合は失敗である.
途中で失敗した場合には,そのまま失敗で終了するか,または残ったカードの山をそのまま(山の番号もそのまま)にしてゲームを再開する.ゲームを再開する場合は,最初に引くカードはカードが残っている山のうちの一番左の山からとする(その山の一番上のカードが最初に引かれるカードとなる).再開後も再開前と同様の方法でゲームを進め,すべての山にカードが無くなれば成功であり,まだカードが残っている山があるのに,次にカードを引くべき山が無くなった場合は失敗である.
このようなゲームの再開を最大 回まで行うものとする.ただし, は か である.つまり, 回も再開しないか, 回だけ再開するかのいずれかである.ゲーム開始前のシャッフルの仕方によりカードの初期配置は異なる.当然,カードの初期配置により,再開せずに成功することもあれば,再開して成功することも,再開して失敗することもある.十分シャッフルしているので,どの初期配置も全て同じ確率で現れるものと考えることにして,再開が 回以内で成功する確率 を求めたい.この確率 を小数で表し,小数第 位まで求めて出力するプログラムを作りなさい.ただし,次の条件を満たすように出力すること.
十分大きい正整数 を取ると が 整数となる場合,小数部は途中から が続くが,その も出力すること.例えば, の場合, なら と出力し, なら と出力する. の場合も同様に,例えば なら と出力すること. 例えば は循環小数 として表すこともできるが,このような場合,前者の表し方を用いる. 入力の 行目には整数 がこの順に空白を区切り文字として書いてある.,, または , である.
出力においては,指定通りに出力した の後に改行を入れること.