dwangoプログラミングコンテスト

C - ゲーマーじゃんけん


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

ドワンゴ社内には、ポーカー部、軽音同好会、料理研究会といった様々な同好会があり、ニコニコ動画を支える社員たちは仕事の合間に部活動を楽しんでいます。

ボードゲーム部も、社内に数多くある同好会の一つです。ボードゲーム部で遊ばれる多くのゲームはターン制のものですが、よくある悩みは、最初のプレイヤーをどうやって決めるかというものです。典型的にはじゃんけんで最後まで勝ち残った人を決めますが、この方法では参加者が多くなるとあいこになりやすく、効率的ではありません。

こんなときボードゲーム部では、ボードゲーム好きの間で古くから伝わる「ゲーマーじゃんけん」と呼ばれる変種のじゃんけんを行います。そのルールは以下のようなものです。

ルール

「ラウンド」と呼ばれる勝負を繰り返し、 1 人の勝者を決めます。

最初のラウンドには、全てのプレイヤーが参加します。ラウンドの勝者が複数人いた場合、勝者のみでラウンドを行うことを繰り返します。ラウンドの勝者が 1 人だけだった場合、そのラウンドの勝者がこのじゃんけんの勝者になります。

ラウンド

ラウンドに参加するプレイヤーは、グー・チョキ・パーの手を選んで出す。

  1. 出された手が 1 種類の場合
    • あいこである。全てのプレイヤーは勝者となる。
  2. 出された手が 2 種類以上の場合
    • 出したプレイヤーの数が最も少ない手に注目する。
      1. そのような手が 1 種類あった場合
        • その手を出したプレイヤーのみ勝者となる。
      2. そのような手が 2 種類あった場合
        • その 2 種類の手の強弱 (*1) を判定し、強い手を出したプレイヤーのみが勝者となる。残る 1 種類の手を出したプレイヤーも敗退する。
      3. そのような手が 3 種類あった場合
        • あいこである。全てのプレイヤーは勝者となる。

補足

ラウンドの具体例

このゲーマーじゃんけんでは、人数が多くても効率的に 1 人の勝者を決めることができます。N 人のプレイヤーがゲーマーじゃんけんを行ったとき、最後に 1 人の勝者が決まるまでに行われるラウンドの回数の期待値を計算してください。ただし、全てのプレイヤーはグー・チョキ・パーを同じ確率で出すものとします。


入力

入力は以下の形式で標準入力から与えられる。

N

出力

1 行目には、ラウンドの回数の期待値を表す実数を出力せよ。小数点以下何桁でも出力してよいが、10-6 を超える絶対誤差を含んではならない。

入力例1

3

出力例1

1.5

Submit提出する