Codeforces ラウンド #275 (ディビジョン 1)C (プレッシャー + 期待)_html/css_WEB-ITnose

C. 文字列を使ったゲーム

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

あなたは、友達とゲーム。このゲームの説明は以下に記載されています。

あなたの友達は、同じ長さ m の異なる n 個の文字列を作成し、すべての文字列を教えてくれます。その後、彼はそのうちの 1 つをランダムに選択します。彼は文字列を確率的に選択します。つまり、n 個の文字列のそれぞれを選択する確率は等しいです。あなたは友達がどの文字列を選択したかを推測したいです。

友達がどの文字列を選択したかを推測するために、あなたは彼に質問することができます。各質問の形式は次のとおりです。「選択した文字列の位置 pos にある文字は何ですか?」指定された質問に対する回答によって文字列が一意に識別される場合、その文字列は推測されたとみなされます。文字列が推測されたら、質問をやめます。

あなたには特定の戦略がないため、質問するたびに、おそらくまだ言及されていない立場について質問します。あなたのタスクは、友達が選択した文字列を推測するために必要な質問の予想数を決定することです。

入力

最初の行には 1 つの整数 n (1?≤?n?≤?50) ?友達が思いついた文字列の数です。

次の n 行には、友達が作成した文字列が含まれます。すべての文字列が個別であり、大小の英語文字のみで構成されていることが保証されます。さらに、すべての文字列の長さは同じで、1 から 20 までの範囲になります。

出力

単一の数値を出力しますか?期待値。絶対誤差または相対誤差が 10?-?9 を超えない場合、答えは正しいとみなされます。

サンプル テスト

入力

2aabaac

出力

2.000000000000000

input

りー

出力

3aaAaBaCaa

入力

1.666666666666667

出力

3acavacwqq

注

最初のサンプルでは、​​文字列は文字が異なるだけです。 3番目の位置にあります。したがって、次の状況のみが考えられます:

1 つの質問で文字列を推測します。イベントの確率は ;

2 つの質問の文字列を推測します。イベントの確率は ・ = (この場合、最初の質問は 3 番目以外の位置について尋ねるはずです);

3 つの質問で文字列を推測します。イベントの確率は ・ ・ = ;

したがって、期待値は

に等しいです。2 番目のサンプルでは、​​質問のペアは文字列を一意に識別するため、最大 2 つの質問が必要です。したがって、予想される質問数は次のとおりです。

3 番目のサンプルでは、​​最初の質問でどのような立場について質問しても、すぐに文字列を識別します。

题意：RT

思路：f[s] s二通過状態下，s里面1の数はすでに通過した位置の文字符，0は猜がない

移動情况: f[s]任意の0转移動来，此过程其实である逆方向、从终点推方向起点

设s の下次状態态 である p、つまり p 一定比 s多一 1、那么f[s]=1/d∑( m/n*1 + f[ p] ) その中 d は s の下次状態の状態数、

m は現在の状態の合法文字列数、n は总的文字列、f[p] は次の状態の予想

最後後f[0]就是答案、即起点