The Closest Guess
National Olympiad — Regional round (2017 season)
Submission name: game.cpp
Problem summary
Chris secretly chooses M and Eva chooses K. Eva announces positive integers. Chris sums only the even ones and remembers the position of the most recent number closest to M. Stop after the sum becomes strictly greater than K, or after 200 numbers. Report the remembered position and final even sum.
Input
M and K, followed by the announced positive integers in order.
Output
The 1-based position of the last closest number and the final sum of even numbers.
Constraints
1 ≤ M, K ≤ 100000; at most 200 numbers are processed. The PDF gives no separate bound for the announced numbers.
Worked example
An independently prepared example for this explanation.
Input
7 30 1 3 12 8 25 6 14
Output
6 40
Solution analysis
- Process each announcement before checking whether the game ends. An even number contributes its full value to the sum; an odd number contributes nothing.
- Compare the absolute distance from M with the best distance seen so far. Update on a smaller or equal distance, because the latest occurrence wins a tie. The PDF gives no upper bound for announcements, so decimal strings support exact subtraction, comparison, and addition without assuming a machine-integer bound.
- For M = 7 in the first sample, 8 and 6 are both one unit away. The later 6 is at position 6, so it wins. The final 14 raises the even sum to 40, exceeding 30, and stops the game.
Why it works
After each processed announcement, the maintained sum contains exactly the even announcements so far. Updating the recorded position on distance ≤ the current best maintains the latest closest position. The first satisfied stopping condition matches the rule, so both reported quantities are correct.
Watch out. The stopping condition is sum > K, not ≥ K. Odd numbers can still be the closest guess. Announced values have no printed upper bound, so use the supplied decimal-string arithmetic rather than a fixed-width input type.
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;
string normalized(string value) {
size_t first = value.find_first_not_of('0');
return first == string::npos ? "0" : value.substr(first);
}
int compare(const string &a, const string &b) {
if (a.size() != b.size()) {
return a.size() < b.size() ? -1 : 1;
}
if (a == b) {
return 0;
}
return a < b ? -1 : 1;
}
string addDecimal(const string &a, const string &b) {
string result;
int i = static_cast<int>(a.size()) - 1;
int j = static_cast<int>(b.size()) - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int digit = carry;
if (i >= 0) {
digit += a[i] - '0';
--i;
}
if (j >= 0) {
digit += b[j] - '0';
--j;
}
result += static_cast<char>('0' + digit % 10);
carry = digit / 10;
}
reverse(result.begin(), result.end());
return result;
}
string subtractDecimal(const string &a, const string &b) {
// The caller supplies a >= b, so ordinary borrowing is sufficient.
string result;
int j = static_cast<int>(b.size()) - 1;
int borrow = 0;
for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
int digit = a[i] - '0' - borrow;
if (j >= 0) {
digit -= b[j] - '0';
--j;
}
borrow = digit < 0 ? 1 : 0;
if (digit < 0) {
digit += 10;
}
result += static_cast<char>('0' + digit);
}
reverse(result.begin(), result.end());
return normalized(result);
}
int main() {
string m, k;
cin >> m >> k;
m = normalized(m);
k = normalized(k);
string sum = "0";
string bestDistance;
int bestPosition = 1;
for (int position = 1; position <= 200; ++position) {
string value;
if (!(cin >> value)) {
break;
}
value = normalized(value);
string distance = compare(value, m) >= 0 ? subtractDecimal(value, m) : subtractDecimal(m, value);
// Equality replaces the previous guess because the latest closest one wins.
if (position == 1 || compare(distance, bestDistance) <= 0) {
bestDistance = distance;
bestPosition = position;
}
if ((value.back() - '0') % 2 == 0) {
sum = addDecimal(sum, value);
}
if (compare(sum, k) > 0) {
break;
}
}
cout << bestPosition << ' ' << sum << '\n';
}