Equal Candy Gifts
National Olympiad — Regional round (2025 season)
Submission name: candies.cpp
Problem summary
Each student has some candies. Buy and add candies so every student finishes with the same count; candies cannot be removed. Find the minimum number to buy and how many students receive extra candies.
Input
N, then N initial candy counts.
Output
The minimum candies to buy and the number of recipients.
Constraints
2 ≤ N ≤ 5000; each initial count is in [1,1000].
Worked example
An independently prepared example for this explanation.
Input
5 3 2 4 1 4
Output
6 3
Solution analysis
- Because candies can only be added, the final common count must be at least the initial maximum. Choosing exactly that maximum is cheapest.
- Track the total sum, largest count, and number of students currently tied for that maximum. A larger value resets its frequency to one; an equal value increases the frequency.
- The sample maximum is four, held by two students. Five students need 20 candies in total and currently hold 14, so buy six candies and give them to 5−2=3 students.
Why it works
Any common count below the maximum is impossible, and increasing the common count only adds cost. At the maximum, the needed total is N·maximum−sum, and precisely those below the maximum receive candies, giving N−maximumFrequency recipients.
Watch out. If everyone already has the same count, both outputs are zero. Count students below the maximum, not the number of distinct smaller counts.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int maximum = 0, maximumCount = 0, sum = 0;
for (int i = 0; i < n; i++) {
int candies;
cin >> candies;
sum += candies;
if (candies > maximum) {
maximum = candies;
maximumCount = 1;
} else if (candies == maximum) {
maximumCount++;
}
}
// Raising everyone to the current maximum is the cheapest possible target.
cout << n * maximum - sum << ' ' << n - maximumCount << '\n';
}