Distinct Integer Sums of Fraction Pairs
National Olympiad — Municipal round (2024 season)
Submission name: sumfraction.cpp
Problem summary
Choose two different list positions containing nonnegative fractions. Count distinct integer values obtainable as their sum.
Input
n followed by n numerator-denominator pairs.
Output
The number of distinct integer sums.
Constraints
2≤n≤5000; 0≤numerator≤50000; 1≤denominator≤50000.
Worked example
Input and output for the worked example discussed below.
Input
5 1 2 2 1 5 2 1 1 7 1
Output
3
Solution analysis
- The exact sum a/b+c/d has numerator ad+cb and denominator bd. It is an integer exactly when the numerator is divisible by the denominator; no floating-point tolerance is needed.
- Enumerate i<j to use distinct positions once each. Every sum lies in [0,100000], so mark successful integer values in a Boolean array and count first-time marks.
- The sample produces integer sums 3,3,9,8. Repeated 3 counts only once, leaving the three values 3,8,9.
Why it works
Cross-multiplication gives the exact sum, and divisibility characterizes an integer. Pair enumeration covers every legal choice, while marking by value removes duplicates without discarding any distinct result.
Watch out. Cross-products can overflow int; use long long before multiplying. Zero is an integer result. Equal fractions at different positions can form a pair.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long>a(n);
vector<long long>b(n);
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
vector<bool>seen(100001,false);
int answer=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
long long top=a[i]*b[j]+a[j]*b[i];
long long bottom=b[i]*b[j];
// Exact divisibility avoids rounding rational values.
if(top%bottom==0&&!seen[top/bottom]){
seen[top/bottom]=true;
answer++;
}
}
}
cout<<answer<<'\n';
}