No.3643 Not a Bad Apple!!
タグ : / 解いたユーザー数 26
作問者 :
kazuppa
/ テスター :
Tamiji153
Unbakedbread
Problem Statement
There are $N$ apples. Of these, $B$ are bad apples, and the remaining $N-B$ are good apples. Eating a good apple has no effect, but eating a bad apple gives you a stomachache.
kazuppa chooses a non-negative integer $k$ not exceeding $N$ and $k$ random apples, then eats all of the chosen apples. His happiness is then determined as follows.
- If he ate a bad apple and got a stomachache, his happiness is $0$.
- If he did not eat any bad apple, his happiness is $k$.
Find one value of $k$ that maximizes the expected value of kazuppa's happiness.
You are given $T$ test cases; find the answer for all of them.
Constraints
- $1\leq T\leq 2\times 10^5$
- $1\leq N\leq 10^{12}$
- $0\leq B\leq N$
- All input values are integers.
Subtasks
This problem has partial scoring by subtasks.
| Subtask | Points | Constraints |
|---|---|---|
| Subtask 1 | 10 % | $N=1$ |
| Subtask 2 | 30 % | $N \leq 2000,$ the sum of $N$ over all test cases does not exceed $2000$ |
| Subtask 3 | 30 % | $N\leq 2\times 10^5,$ the sum of $N$ over all test cases does not exceed $2\times 10^5$ |
| Subtask 4 | 30 % | No additional constraints |
Input
$T$ $Test_1$ $Test_2$ $\vdots$ $Test_T$Each test case is given in the following format.
$N\ B$
Output
Print $T$ lines.
On the $i$-th line, print the answer to the $i$-th test case.
Sample
Sample 1
Input
3 6 2 10 10 169231 667
Output
2 0 253
Consider the $1$st test case.
If $k=1$ is chosen, the probability of not eating a bad apple is $\frac{2}{3}$, so the expected happiness is $\frac{2}{3}$.
If $k=2$ is chosen, the probability of not eating a bad apple is $\frac{2}{5}$, so the expected happiness is $\frac{4}{5}$.
In this case, the maximum expected happiness is $\frac{4}{5}$ at $k=2$, so the answer is $2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。