問題一覧 > 通常問題

No.1835 Generalized Monty Hall Problem

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 137
作問者 : Sumitacchan / テスター : 👑 hitonanode ygussany
お気に入りにしたユーザー ProblemId : 7115 / 自分の提出
問題文最終更新日: 2022-01-15 16:08:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 331 (順位表) の他の問題:

Problem Statement

You are taking on a game based on the Monty Hall problem and aim to win a prize.
The game is run by a host and is played with $N$ doors according to the following procedure.

  1. The host randomly chooses $M$ of the $N$ doors as winning doors and places a prize behind each winning door. You are not told which doors are winning doors.
  2. You freely choose $1$ door out of the $N$ doors.
  3. Among the $N-1$ doors you did not choose in step 2., the host randomly chooses $K$ doors from those that are not winning doors, opens them, and shows you that they are not winning doors.
    (By the constraints, there are always at least $K$ doors satisfying the condition.)
  4. You once again freely choose $1$ door from the $N-K$ doors that have not yet been opened (including the door you chose in step 2.), and open that door.
  5. If the door you chose and opened in step 4. is a winning door, you win the prize.

Find the probability that you win the prize when you act optimally.
The answer is a positive rational number, so when it is expressed as an irreducible fraction $P/Q\ (P,Q>0)$, output the values of $P,Q$.

Input

$N\ \ M\ \ K$

  • $3\le N \le 10^6$
  • $1\le M \le N-2$
  • $1\le K \le N-M-1$
  • All inputs are integers.

Output

When the answer is expressed as an irreducible fraction $P/Q\ (P,Q>0)$, output the values of $P,Q$ in the following format. 

$P\ \ Q$

Sample

Sample 1
Input
3 1 1
Output
2 3

This is exactly the Monty Hall problem.
If you chose a non-winning door in step 2. (which happens with probability $2/3$), the other door remaining after step 3. is the winning door.
With the strategy of choosing different doors in steps 2. and 4., you can win the prize with probability $2/3$.

Sample 2
Input
1000000 1 999998
Output
999999 1000000

With the same strategy as in Sample 1, you can win the prize with probability $999999/1000000$, the probability of choosing a non-winning door in step 2.

Sample 3
Input
1000000 999998 1
Output
999999 1000000

Sample 4
Input
1234 56 789
Output
2877 22829

Output the answer as an irreducible fraction.

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