Guessing with Unequal Answer Costs
Autumn Tournament (2015)
Submission name: game.cpp
Problem summary
An opponent chooses one integer from 1 to n. You may ask whether it belongs to any subset you choose. A no answer costs a euros and a yes answer costs b euros. Find the smallest budget that guarantees identification, regardless of the chosen number.
Input
Three integers n, a and b.
Output
Print the minimum guaranteed worst-case cost.
Constraints
1 < n < 10^18; 1 ≤ a,b < 1000. The largest original subtask has a=1; this solution also supports arbitrary permitted a and b.
Worked example
Official sample. Four euros distinguish all five possibilities even though yes and no have different costs.
Input
5 1 2
Output
4
Solution analysis
- Instead of asking for the minimum cost for every possible n, reverse the question: let capacity[t] be the maximum number of candidates distinguishable with budget t. With only one candidate, no question is necessary, so capacity is at least one for every nonnegative budget.
- A useful question must leave a nonempty set after either answer. If t < max(a,b), this is impossible because one answer would already exceed the budget. Otherwise the no branch can contain capacity[t-a] candidates and the yes branch capacity[t-b]. Thus capacity[t] = capacity[t-a] + capacity[t-b]. Arbitrary subset questions allow exactly such a partition; the candidates do not need to form an interval.
- For a=1,b=2, the capacities for budgets 0,1,2,3,4 are 1,1,2,3,5. The first capacity reaching n=5 occurs at budget 4. One first question can put two candidates in the yes branch, leaving budget 2, and three in the no branch, leaving budget 3.
- Compute budgets in increasing order and cap capacities at n. Larger capacities are irrelevant and capping prevents overflow. A balanced binary decision tree uses at most ceil(log2 n) questions, each costing at most max(a,b), so the required DP has only about sixty thousand states even for the full input range.
Why it works
Every strategy begins with a partition into yes and no candidates. Its branches cannot distinguish more than the capacities for the remaining budgets, giving the recurrence as an upper bound. Conversely, partitioning into sets of those sizes and applying their optimal strategies achieves that bound. Induction on t proves every capacity, and the first t reaching n is precisely the required minimum.
Watch out. Do not assume equal-size branches are optimal when answer costs differ. A branch with no candidates is not a useful question. Use a 64-bit type for n and saturate additions; the result itself is small.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
unsigned long long n;
int noCost,yesCost;
cin>>n>>noCost>>yesCost;
vector<unsigned long long>capacity;
for(int budget=0;;budget++){
unsigned long long ways=1;
if(budget>=max(noCost,yesCost)){
auto left=capacity[budget-noCost];
auto right=capacity[budget-yesCost];
// Values larger than n are unnecessary; this also avoids overflow.
ways=left>=n-right?n:left+right;
}
capacity.push_back(ways);
if(ways>=n){
cout<<budget<<'\n';
break;
}
}
}