Candy Bowl Walk
National Olympiad — Regional round (2016 season)
Submission name: candies.cpp
Problem summary
Maya takes one candy from bowls in the repeating order left, middle, right, middle. She stops immediately when the next required bowl is empty. Given A, B and C candies, find how many she eats.
Input
A B C.
Output
The number of candies eaten before the first failed attempt.
Constraints
A, B, C are nonnegative; 0 < A + B + C ≤ 2,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
3 3 3
Output
7
Solution analysis
- The attempt indices are zero-based. The left bowl is visited at 0, 4, 8, …, so its first failed visit is at index 4A. The right bowl is visited at 2, 6, 10, …, so its first failure is 4C + 2.
- The middle bowl is visited at every odd index 1, 3, 5, …, making its first failure 2B + 1. The process stops at the minimum of these three failure indices. That index is also the number of successful attempts before it.
- For A = B = C = 3 the first failure indices are 12, 7 and 14. The middle bowl fails first at index 7, after exactly seven candies. A left bowl initially empty instead causes immediate failure and an answer of zero.
Why it works
For each bowl its arithmetic progression lists exactly all attempts to take from it. After its initial candy count of successful visits, the next visit is its first failure, giving the three formulas. The earliest failure among all bowls ends the process, and all earlier attempts succeeded, so its zero-based index is the number eaten.
Watch out. The middle bowl is visited twice per four-step cycle. Zero candies in individual bowls are allowed. Compute intermediate failure indices in long long.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b, c;
cin >> a >> b >> c;
// These are the zero-based attempt indices of each bowl's first failure.
cout << min({4 * a, 2 * b + 1, 4 * c + 2}) << '\n';
return 0;
}