No.2972 確率的素数判定
タグ : / 解いたユーザー数 45
作問者 : 👑 p-adic / テスター : Moss_Local
問題文
確率的素数判定大好きbotは確率的素数判定が大好きなbotです。
確率的素数判定大好きbot大好きbotは確率的素数判定大好きbotが大好きなbotです。もちろん $2$ 体は別物です。
ここで次のような問題を考えます:
入力に正整数 $N$ と、$100$ 以下の非負整数 $P, Q$ が与えられます。
確率的素数判定大好きbotに正整数を読み込ませると、以下の挙動を示します:
- 読み込んだ正整数が素数であるならば、$P$ %の確率で
Yes
と返答し、$(100 - P)$ %の確率でNo
と返答する。- 読み込んだ正整数が素数でないならば、$Q$ %の確率で
No
と返答し、$(100 - Q)$ %の確率でYes
と返答する。確率的素数判定大好きbot大好きbotが $N$ 以下の正整数全体の中から正整数 $n$ をランダムに(どの正整数が選ばれるかが等確率になるように)選び、確率的素数判定大好きbotに読み込ませました。あなたは $n$ の値を知りませんが、確率的素数判定大好きbotは
Yes
と返答をしたことだけを確認しました。上記の情報が与えられている状況のもとで $n$ が素数である確率を求めてください。(以下この値を、この問題に対する答えと呼ぶ)
入力の最初に正整数 $T$ が与えられます。その後 $T$ 個の問題に答えてください。
入力
この時、入力は以下の形式で標準入力から $1 + T$ 行で与えられます:
- $1$ 行目に $T$ が半角空白区切りで与えられます。
- $T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力が $1 + t$ 行目に与えられます。
$T$ ($1$ 個目の問題に対する入力) $\vdots$ ($T$ 個目の問題に対する入力)
$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力は以下の形式で与えられます:
- $N, P, Q$ が半角空白区切りで $1$ 行で(入力全体の $1 + t$ 行目に)与えられます。
$N$ $P$ $Q$
各問題における未知数 $n$ は入力では与えられません。
制約
入力は以下の制約を満たします:
- $T$ は $1 \leq T \leq 10^5$ を満たす整数である。
- $T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力を $N, P, Q$ と置くと、
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $P$ は $0 < P \leq 100$ を満たす整数である。
- $Q$ は $0 \leq Q \leq 100$ を満たす整数である。
- $N > 1$ かつ $0 < P$ であるか、または $Q < 100$ である。
出力
$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する答えを小数表示で $t$ 行目に出力してください。
最後に改行してください。
なお、この問題は小数誤差許容問題です。厳密な答えの小数点以下 $10$ 桁精度近似値からの絶対誤差か相対誤差のいずれかが $10^{-5}$ 以下であれば正解となります:
ただしここで実数 $x$ の小数点以下 $10$ 桁精度近似値とは、小数点以下高々 $10$ 桁の有限小数表示を持ち $x$ を超えない最大の実数を表します。
また、ジャッジ側の都合で各出力は $500$ 桁未満にしてください。
サンプル
サンプル1
入力
1 1 90 80
出力
0
確率的素数判定大好きbotがYes
と返答した事実に関係なく、$N = 1$ 以下の正整数 $n$ が素数である確率は $0$ です。誤差許容問題の仕様上、この他にも
0.00
や
-0.00001
などと出力しても正解となります。今回は $T = 1$ であるため、これにて全ての問題に答えられました。
サンプル2
入力
1 2 100 0
出力
0.5
$P = 100$ かつ $Q = 0$ であるため、確率的素数判定大好きbotはどんな正整数を読み込んでもYes
と返します。従って確率的素数判定大好きbotがYes
と返答したという情報は $n$ が素数であるか否かに関して何の情報も与えません。以上より求める値は $n$ が $N = 2$ 以下の正整数全体 $\{1,2\}$ の中からランダムに選ばれた時に $n$ が素数 $2$ である確率に他ならず、それは $0.5$ となります。
今回は $T = 1$ であるため、これにて全ての問題に答えられました。
サンプル3
入力
2 3 100 100 4 50 50
出力
1 0.5
まず $1$ つ目の問題に答えます。今回は $P = 100$ かつ $Q = 100$ であるため、確率的素数判定大好きbotは読み込まれた正整数が素数であるか否かを常に正確に判定します。確率的素数判定大好きbotの返答はYes
であったので、$n$ が素数である確率は $1$ です。
次に $2$ つ目の問題に答えます。今回は $P = 50$ かつ $Q = 50$ であるため、確率的素数判定大好きbotの返答がYes
となるかNo
となるは $n$ に依存せずランダムに決まります。従って確率的素数判定大好きbotがYes
と返答したという情報は $n$ が素数であるか否かに関して何の情報も与えません。以上より求める値は $n$ が $N = 4$ 以下の正整数全体 $\{1,2,3,4\}$ の中からランダムに選ばれた時に $n$ が素数 $2,3$ のいずれかである確率に他ならず、それは $0.5$ となります。
今回は $T = 2$ であるため、これにて全ての問題に答えられました。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。