問題一覧 > 通常問題

No.3643 Not a Bad Apple!!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 16
作問者 : kazuppa / テスター : Tamiji153 Unbakedbread
ProblemId : 13631 / Paken新入生コンday2 (順位表) / 自分の提出
問題文最終更新日: 2026-08-25 18:37:34
Paken新入生コンday2の他の問題:

問題文

$N$ 個のリンゴがあります。このうち $B$ 個は悪いリンゴ、残りの $N-B$ 個は良いリンゴです。良いリンゴを食べても何も起こりませんが、悪いリンゴを食べるとお腹を壊してしまいます。

kazuppa君は $N$ 以下の非負整数 $k$ とランダムなリンゴ $k$ 個を選び、選んだリンゴを全て食べます。この時、kazuppa君の幸福度は以下のようになります。

  • もし悪いリンゴを食べてお腹を壊したなら、幸福度は $0$
  • もし悪いリンゴを食べなかったら、幸福度は $k$

kazuppa君の幸福度の期待値が最大となる時の $k$ を一つ求めてください。

$T$ 個のテストケースが与えられるので、全てについて答えを求めてください。

制約

  • $1\leq T\leq 2\times 10^5$
  • $1\leq N\leq 10^{12}$
  • $0\leq B\leq N$
  • 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

小課題名 配点 制約
小課題110 %$N=1$
小課題230 %$N \leq 2000,$ 全てのテストケースにおける $N$ の総和は $2000$ を超えない
小課題330 %$N\leq 2\times 10^5,$ 全てのテストケースにおける $N$ の総和は $2\times 10^5$ を超えない
小課題430 %追加の制約はない

入力

$T$
$Test_1$
$Test_2$
$\vdots$
$Test_T$
また、各テストケースは以下の形式で与えられます 
$N\ B$

出力

$T$ 行出力してください。

$i$ 行目には、$i$ 番目のテストケースの答えを出力してください。

サンプル

サンプル1
入力
3
6 2
10 10
169231 667
出力
2
0
253

$1$ つ目のテストケースを考えます。

$k=1$ を選んだ時、悪いリンゴを食べない確率は $\frac{2}{3}$ なので、幸福度の期待値は $\frac{2}{3}$ です。

$k=2$ を選んだ時、悪いリンゴを食べない確率は $\frac{2}{5}$ なので、幸福度の期待値は $\frac{4}{5}$ です。

この場合では $k=2$ の時の $\frac{4}{5}$ が幸福度の期待値の最大のため、$2$ が答えとなります。

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