Acrobat
Autumn Tournament (2008)
Submission name: acrobat.cpp
Problem summary
Six judges give integer scores. Discard one occurrence of the smallest score and one occurrence of the largest, then average the four remaining scores. The result is guaranteed to be an integer.
Input
Six integer scores.
Output
The final integer score.
Constraints
Each score is between 1 and 1000000000000. The trimmed average is integral.
Worked example
Original statement sample.
Input
36 24 72 8 10 22
Output
23
Solution analysis
- Accumulate the sum and track the smallest and largest score. Only one copy of each extreme must be removed.
- Subtract the two extremes from the sum and divide by four. Even when several scores equal an extreme, subtracting its value once removes exactly one occurrence.
- The sample total is 172. Removing 8 and 72 leaves 92, so the final score is 92/4 = 23.
Why it works
The tracked sum contains each of the six scores once. Subtracting one minimum and one maximum leaves exactly the four scores prescribed by the rules. Their sum divided by four is the required average.
Watch out. Use 64-bit integers: both individual scores and their sum exceed the 32-bit range. Remove one extreme occurrence, not all occurrences.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long sum=0;
long long lowest=numeric_limits<long long>::max();
long long highest=0;
for(int judge=0;judge<6;judge++){
long long score;
cin>>score;
sum+=score;
lowest=min(lowest,score);
highest=max(highest,score);
}
// Exactly four scores remain after removing two occurrences.
cout<<(sum-lowest-highest)/4<<'\n';
}