Complete Four Equally Spaced Numbers
National Olympiad — Regional round (2023 season)
Submission name: guessn.cpp
Problem summary
Three distinct positive integers were selected from four positive integers in an arithmetic progression with positive integer difference. Find every possible missing integer.
Input
Three integers a, b, c in arbitrary order.
Output
All possible missing values in increasing order.
Constraints
1 ≤ a,b,c ≤ 10^9; at least one solution exists.
Worked example
An independently prepared example for this explanation.
Input
4 6 8
Output
2 10
Solution analysis
- Sort the three given values. Instead of guessing a missing value, guess which of the four progression positions is missing. There are only four cases.
- For each case, assign the three sorted values to the remaining positions. The distance between the first two occupied positions determines the difference, which must be a positive integer. Reconstruct the starting value and check all three observations.
- For 4,6,8, missing the first position gives start 2 and difference 2; missing the last gives 10. The two internal-position possibilities fail their spacing checks. Store valid answers in a set to sort and deduplicate them.
Why it works
Every possible progression omits exactly one of the four positions and is checked in that case. Conversely, a retained candidate has positive start and difference and matches all observations, so it is valid.
Watch out. The missing value must be positive. Input order is irrelevant. A valid answer may exceed 10^9, so use long long.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int main() {
vector<long long> a(3);
for (long long &value : a) {
cin >> value;
}
sort(a.begin(), a.end());
set<long long> answers;
// Try each possible missing position in the four-term progression.
for (int missing = 0; missing < 4; missing++) {
vector<int> positions;
for (int position = 0; position < 4; position++) {
if (position != missing) {
positions.push_back(position);
}
}
long long gap = positions[1] - positions[0];
if ((a[1] - a[0]) % gap != 0) {
continue;
}
long long difference = (a[1] - a[0]) / gap;
long long first = a[0] - positions[0] * difference;
bool valid = first > 0 && difference > 0;
for (int i = 0; i < 3; i++) {
valid = valid && first + positions[i] * difference == a[i];
}
if (valid) {
answers.insert(first + missing * difference);
}
}
bool firstOutput = true;
for (long long answer : answers) {
if (!firstOutput) {
cout << ' ';
}
firstOutput = false;
cout << answer;
}
cout << '\n';
}