First Below the Threshold
National Olympiad — Regional round (2009 season)
Submission name: row.cpp
Problem summary
Given N values, find the first position whose value is at most one third of the minimum plus two thirds of the maximum.
Source clarification. The PDF sample visually merges the six values as 965781; its explanation identifies them as 9, 6, 5, 7, 8, 1. They are separated here according to the stated input format.
Input
N followed by N space-separated integers.
Output
The smallest qualifying position, numbered from 1.
Constraints
1 ≤ N < 1000; values are between 0 and 10,000.
Worked example
An independently prepared example for this explanation.
Input
6 9 6 5 7 8 1
Output
2
Solution analysis
- Find the minimum lo and maximum hi of the sequence. The required threshold is (lo + 2hi)/3.
- Avoid rounding the fractions independently. Instead test 3 × value ≤ lo + 2hi with integer arithmetic, then stop at the first successful position.
- For 9, 6, 5, 7, 8, 1, the threshold is 19/3. The initial 9 fails, and the next value 6 succeeds, so position 2 is returned.
Why it works
Multiplication by positive 3 preserves the threshold inequality. The scan tests positions in increasing order, so its first successful position is the smallest qualifying one. A qualifying position exists because the minimum is no larger than the threshold.
Watch out. Do not apply integer division separately to the two thirds. Output a 1-based index.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> values(n);
for (int &value : values) {
cin >> value;
}
int low = *min_element(values.begin(), values.end());
int high = *max_element(values.begin(), values.end());
for (int i = 0; i < n; i++) {
// Multiply the threshold inequality by 3 to avoid rounding.
if (3 * values[i] <= low + 2 * high) {
cout << i + 1 << '\n';
break;
}
}
}