A Prefix of Colored Balls
National Olympiad — Municipal round (2017 season)
Submission name: balls.cpp
Problem summary
A row consists of all n1 balls of the first given type followed by all n2 balls of the other type. The types are A and B. Take the first k balls and count how many are type A.
Input
n1 and its type; n2 and its type; then k.
Output
The number of type-A balls taken.
Constraints
1 ≤ n1, n2 ≤ 100; 0 ≤ k ≤ n1 + n2.
Worked example
An independently prepared example for this explanation.
Input
5 A 6 B 7
Output
5
Solution analysis
- The first block contributes min(k, n1) taken balls. Only when k exceeds n1 do we take anything from the second block.
- If the first type is A, its contribution is the whole answer. Otherwise A is the second type and the answer is max(0, k − n1). The upper bound on k ensures this does not exceed n2.
- With 5 A balls followed by 6 B balls, taking 7 includes all five A balls and two B balls, so the answer is 5. Reversing the types gives 2 A balls in that same seven-ball prefix.
Why it works
Taking a prefix consumes the first block before entering the second. Its overlap with the first block is min(k, n1), and its overlap with the second is max(0, k − n1). Exactly one block is type A, so choosing that overlap gives precisely the A count.
Watch out. The order of the input blocks matters. Do not assume type A is first.
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);
int n1, n2, k;
char type1, type2;
cin >> n1 >> type1 >> n2 >> type2 >> k;
// A prefix finishes the first block before entering the second.
if (type1 == 'A') {
cout << min(k, n1) << '\n';
} else {
cout << max(0, k - n1) << '\n';
}
return 0;
}