問題一覧 > 通常問題

No.1835 Generalized Monty Hall Problem

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 128
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
3 ProblemId : 7115 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-15 16:08:27

問題文

あなたは モンティ・ホール問題 をもとにしたゲームに挑戦し、景品の獲得を目指します。
ゲームは司会者が進行を務め、$N$ 個のドアを用いて次の手順で行われます。

  1. 司会者は、$N$ 個のドアから無作為に $M$ 個のドアを当たりとして選び、当たりのドアの後ろに景品を置きます。どのドアが当たりかあなたには知らされません。
  2. あなたは、$N$ 個のドアから自由に $1$ 個のドアを選びます。
  3. 司会者は、あなたが 2. で選んでいない $N-1$ 個のドアのうち当たりでないものの中から無作為に $K$ 個のドアを選んで開け、それらは当たりでないことをあなたに示します。
    (制約より、条件を満たすドアは必ず $K$ 個以上存在します。)
  4. あなたは、まだ開けられていない $N-K$ 個のドア(あなたが 2. で選んだドアも含む)からもう一度自由に $1$ 個のドアを選び、そのドアを開けます。
  5. あなたが 4. で選んで開けたドアが当たりであれば、あなたは景品を獲得できます。

あなたが最適に行動するとき、景品を獲得できる確率を求めてください。
なお、答えは正の有理数になるので、答えを既約分数 $P/Q\ (P,Q>0)$ として表したときの $P,Q$ の値をそれぞれ出力してください。

入力

$N\ \ M\ \ K$

  • $3\le N \le 10^6$
  • $1\le M \le N-2$
  • $1\le K \le N-M-1$
  • 入力は全て整数である。

出力

答えを既約分数 $P/Q\ (P,Q>0)$ として表したときの $P,Q$ の値を次の形式で出力してください。

$P\ \ Q$

サンプル

サンプル1
入力
3 1 1
出力
2 3

モンティ・ホール問題そのものです。
あなたが 2. で当たりでないドアを選んだ(その確率は $2/3$ です)とすると、3. の後に残ったもう一方のドアが当たりです。
2. と 4. で違うドアを選ぶという戦略により、$2/3$ の確率で景品を獲得できます。

サンプル2
入力
1000000 1 999998
出力
999999 1000000

サンプル1と同様の戦略により、2. で当たりでないドアを選ぶ確率 $999999/1000000$ で景品を獲得できます。

サンプル3
入力
1000000 999998 1
出力
999999 1000000

サンプル4
入力
1234 56 789
出力
2877 22829

既約分数として出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。