Problem F
Chocolate Balls
Bruno and Sofie are members of a mathematics club at their high school and go to a grocery store to buy snacks for their club meeting. When they were at the grocery store, they saw something incredible: Chocolate balls for only $2$ kr each!!! Bruno and Sofie immediately started putting chocolate balls into their respective paper bags, paying for the chocolate balls, and then returning to school. When they returned to school, they wanted to distribute the chocolate balls among $N$ paper bags evenly so that the number of chocolate balls in all $N$ bags is as close as possible, so that all $N$ students can get their own bag of chocolate balls. The chocolate balls are evenly distributed among all bags if the difference in the number of chocolate balls between any 2 bags never exceeds 1.
To get all the chocolate balls distributed as evenly as possible among all $N$ bags, Bruno and Sofie can only make the following move any number of times: Move one chocolate ball from their own bag to another bag.
Given that there were $B$ chocolate balls in Bruno’s paper bag, and $S$ chocolate balls in Sofie’s paper bag, how many chocolate balls do Bruno and Sofie need to move at least for the number of chocolate balls in all $N$ bags to be as evenly distributed as possible? In other words, what is the minimum number of moves needed for all chocolate balls to be as evenly distributed as possible among all $N$ bags?
Note that Bruno’s and Sofie’s paper bags with chocolate balls are also included in the $N$ paper bags.
Input
The first row consists of an integer, $N$ $(2 \leqslant N \leqslant 10^9)$. The second row consists of two integers, $B$ och $S$ $(0 \leqslant B,S \leqslant 10^9)$.
1 Output
Output a single integer, the minimum number of chocolate balls that has to be moved by Bruno and Sofie.
2 Scoring
Your solution will be tested on several test case groups. To
get the points for a group, it must pass all the test cases in
the group.
|
Group |
Point value |
Constraints |
|
$1$ |
$15$ |
$N=2$, $B+S \leqslant 10$ |
|
$2$ |
$15$ |
$N=3$, $B+S \leqslant 100$ |
|
$3$ |
$30$ |
$N \leqslant 10^3$ , $B+S \leqslant 10^3$ |
|
$4$ |
$20$ |
It is guaranteed that the number of chocolate balls divides evenly, meaning that there can be an equal number of chocolate balls in each bag. |
|
$5$ |
$20$ |
No further constraints. |
Explanation of Sample 1
In the first test case, there are only 2 bags, Bruno’s bag with 6 chocolate balls, and Sofie’s bag with 4 chocolate balls. To distribute them evenly, Bruno needs to move only 1 chocolate ball from his bag to Sofie’s bag.
Explanation of Sample 2
In the second test case, there are 3 bags initially. The third bag is empty at first. But after Bruno moves 2 chocolate balls from his bag to the empty bag, there will eventually be 3 in Bruno’s bag, 3 in Sofie’s bag, and 2 in the third bag. This way, the chocolate balls are distributed as evenly as possible, as it is not possible to distribute 8 chocolate balls among three bags any better than that.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 6 4 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 3 |
2 |
