Exact Grade Percentages
National Olympiad — National round (2017 season)
Submission name: percent.cpp
Problem summary
For each of N classes, five integer percentages describe the students receiving each of five grades. Find the smallest positive class size for which all five student counts are integers.
Input
N, followed by N rows of five percentages.
Output
For each class, print its minimum possible size on a separate line.
Constraints
2 ≤ N ≤ 100; percentages lie in [0,100] and each row sums to 100.
Worked example
An independently prepared example for this explanation.
Input
2 40 30 20 5 5 20 0 50 30 0
Output
20 10
Solution analysis
- If a class has s students and a grade has p percent, its student count is s·p/100. This must be an integer for each of the five percentages.
- The answer is 100 divided by gcd(100, p1, p2, p3, p4, p5). Compute the gcd incrementally, starting with 100. Zero percentages are harmless because gcd(g,0) = g.
- For 40,30,20,5,5 the gcd is 5, so the minimum size is 20. The grade counts become 8,6,4,1,1. For 20,0,50,30,0 the gcd is 10 and the answer is 10.
Why it works
For a percentage p, integrality requires s to be a multiple of 100/gcd(100,p). The least common multiple of these five required divisors is 100/gcd(100,p1,...,p5), as follows by comparing each prime exponent in the divisors of 100. Thus the formula is feasible and divides every feasible size.
Watch out. Do not round fractional student counts. A row containing 100 and four zeros has answer 1.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
// The shared gcd determines the smallest exact percentage denominator.
int common = 100;
for (int grade = 0; grade < 5; ++grade) {
int percentage;
cin >> percentage;
common = gcd(common, percentage);
}
cout << 100 / common << '\n';
}
}