Splitting a Treasure
National Olympiad — Regional round
Submission name: divide.cpp
Problem summary
A piece of weight 2^n may be split into two equal pieces in one operation. Partition it among three recipients so their exact totals are a, b, and 2^n−a−b. Find the fewest splitting operations.
Input
n a b.
Output
The minimum operation count.
Constraints
2≤n≤30; a≥1; b≥1; a+b<2^n.
Worked example
An independently prepared example for this explanation.
Input
3 1 3
Output
3
Solution analysis
- Every resulting piece has power-of-two weight. Any total x needs at least popcount(x) such pieces.
- Use the binary decomposition of each of the three totals. These pieces sum to the original power of two and can be obtained by recursively splitting.
- A split increases the piece count by one, so subtract one from the sum of the three popcounts.
Why it works
Combining equal-sized pieces never increases their count, and leaves the unique binary representation, proving the lower bound. Conversely the required multiset can be merged from smallest sizes into one piece because its sum is a power of two; reversing these merges constructs it.
Watch out. Include the third recipient’s remainder, and distinguish 2^n from 2n.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Combining equal-sized pieces never increases their count, and leaves the unique binary
// representation, proving the lower bound. Conversely the required multiset can be merged from
// smallest sizes into one piece because its sum is a power of two; reversing these merges constructs
// it.
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main(){
int n;
long long a,b;
cin>>n>>a>>b;
long long c=(1LL<<n)-a-b;
cout<<__builtin_popcountll(a)+__builtin_popcountll(b)+__builtin_popcountll(c)-1<<'\n';
}