P7909 [CSP-J 2021] Candy Distribution

The children at Red Sun Kindergarten are starting to share candies.

There are $n$ children at Red Sun Kindergarten, and you are one of them. It is guaranteed that $n \ge 2$. One day, you find infinitely many candies in the back garden of the kindergarten, and you plan to take some candies back to share with the children. However, since you are just an ordinary kindergarten child, your strength is limited, and you can carry at most $R$ candies back. But carrying too few is not enough to share, so you must carry at least $L$ candies back. It is guaranteed that $n \le L \le R$. That is, if you take $k$ candies, you must ensure that $L \le k \le R$. If you take $k$ candies, you will put these $k$ candies into a basket, and require everyone to share candies as follows: as long as there are **at least** $n$ candies in the basket, all $n$ children in the kindergarten (including yourself) each take **exactly** one candy from the basket, until the number of candies in the basket becomes **less than** $n$. At that point, all remaining candies in the basket belong to you — these candies are **your reward for carrying the candies**. As a high-quality kindergarten child, you want the number of candies you get **as your reward for carrying the candies** ( **not the total number of candies you finally get** ) to be as large as possible. Therefore, you need to write a program that reads $n, L, R$ and outputs the maximum number of candies you can obtain **as your reward for carrying the candies**.

One line contains three positive integers $n, L, R$, representing the number of children, and the lower and upper bounds on the number of candies.

Output one line containing one integer, representing the maximum number of candies you can obtain **as your reward for carrying the candies**.

**Sample Explanation #1** Take $k = 20$ candies and put them into the basket. The basket now has $20 \ge n = 7$ candies, so all children each get one candy. The basket now has $13 \ge n = 7$ candies, so all children each get one candy. The basket now has $6 < n = 7$ candies, so these $6$ candies are **your reward for carrying the candies**. It is easy to see that the number of candies you get **as your reward for carrying the candies** cannot exceed $6$ (otherwise, the basket would still have at least $n$ candies in the end, and everyone would need to take one more candy). Therefore, the answer is $6$. **Sample Explanation #2** It is easy to see that when the number of candies you take $k$ satisfies $14 = L \le k \le R = 18$, after all children each take one candy, the remaining $k - 10$ candies are always the number of candies **as your reward for carrying the candies**. Therefore, taking $k = 18$ is optimal, and the answer is $8$. **Constraints** | Test Point | $n \le$ | $R \le$ | $R - L \le$ | |:-:|:-:|:-:|:-:| | $1$ | $2$ | $5$ | $5$ | | $2$ | $5$ | $10$ | $10$ | | $3$ | ${10}^3$ | ${10}^3$ | ${10}^3$ | | $4$ | ${10}^5$ | ${10}^5$ | ${10}^5$ | | $5$ | ${10}^3$ | ${10}^9$ | $0$ | | $6$ | ${10}^3$ | ${10}^9$ | ${10}^3$ | | $7$ | ${10}^5$ | ${10}^9$ | ${10}^5$ | | $8$ | ${10}^9$ | ${10}^9$ | ${10}^9$ | | $9$ | ${10}^9$ | ${10}^9$ | ${10}^9$ | | $10$ | ${10}^9$ | ${10}^9$ | ${10}^9$ | For all testdata, it is guaranteed that $2 \le n \le L \le R \le {10}^9$. 【Thanks for providing hack data】 [wangbinfeng](/user/387009) Translated by ChatGPT 5