No.1835 Generalized Monty Hall Problem
タグ : / 解いたユーザー数 128
作問者 : Sumitacchan / テスター : hitonanode 👑 ygussany
問題文
あなたは
モンティ・ホール問題
をもとにしたゲームに挑戦し、景品の獲得を目指します。
ゲームは司会者が進行を務め、$N$ 個のドアを用いて次の手順で行われます。
- 司会者は、$N$ 個のドアから無作為に $M$ 個のドアを当たりとして選び、当たりのドアの後ろに景品を置きます。どのドアが当たりかあなたには知らされません。
- あなたは、$N$ 個のドアから自由に $1$ 個のドアを選びます。
- 司会者は、あなたが 2. で選んでいない $N-1$ 個のドアのうち当たりでないものの中から無作為に $K$ 個のドアを選んで開け、それらは当たりでないことをあなたに示します。
(制約より、条件を満たすドアは必ず $K$ 個以上存在します。) - あなたは、まだ開けられていない $N-K$ 個のドア(あなたが 2. で選んだドアも含む)からもう一度自由に $1$ 個のドアを選び、そのドアを開けます。
- あなたが 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もしくは右上の雲マークをクリックしてアカウントを作成してください。