Guess a Number After Lies Begin
National Olympiad — National round (2016 season)
Submission name: findnumber.cpp
Problem summary
Guess x∈[0,N) through cyclic-interval membership questions. Replies are truthful until an unknown time, then every later reply is inverted. Meet the official worst-case query limits.
Source clarification. This is an interactive judge-function task. The example describes the grader call rather than a standard-input file; the hidden number and lie-switch time belong to the grader. Compile with the provided findnumber.h and grader, without adding a contestant main.
Input
Grader calls long long play(long long N). Query using bool isInside(long long l,long long r) from findnumber.h.
Output
Return the hidden integer from play; do not print or define main.
Constraints
1 ≤ N ≤ 10^15. Limits: 200 queries for N≤100; 65 for N≤10^9; 48 for N≤10^12; 10 for N≤92; 56 for 10^12<N≤10^15.
Worked example
Illustrative grader scenario. The official statement gives one possible dialogue; replies depend on the hidden number and the switch time.
Input
Grader calls play(4), with x=2 and an unknown switch to permanent lies.
Output
play returns 2 within the permitted number of isInside calls.
Solution analysis
- Maintain disjoint candidate sets A and B. A means replies so far can still all be truthful; B means the switch to permanent lies has already occurred. Initially A=[0,N), B is empty. A remains one ordinary interval; B is a union of O(q) intervals.
- If a question selects A1⊆A and B1⊆B, a yes reply changes state to (A1, (A\A1)∪(B\B1)); a no reply changes it to (A\A1, A1∪B1). The capacity H(a,k), the largest b solvable with k questions, is 2^k−a(k+1) on a finite domain a≤m[k]. Here m[0]=1; for k≥1 let s=floor(2^(k−1)/(k+1)) and m[k]=2s, adding one exactly when 2^(k−1)−k(s+1)=s.
- Choose the smallest feasible k. Split a into a1=floor(a/2) and a2=a−a1. Choose b1 so both next states fit k−1 questions: max(0,a2+b−H(a1,k−1))≤b1≤min(b,H(a2,k−1)−a1). The lower endpoint works. Select A1 as a suffix of A, then extend the cyclic question clockwise until it includes b1 candidates from B. For N=2 this naturally uses at most three questions: one membership split, an empty-set truthfulness check, and at most one known-inverted binary question.
Why it works
The two state transitions follow by separating truthful and permanently inverted replies. The capacity recurrence is H(a,k)=max(H(u,k−1)+H(v,k−1))−a over u+v=a for which each branch can contain the other part. Substitution and induction yield the displayed arithmetic capacity and domain endpoint m[k]; balanced u,v attain it. The selected b1 satisfies both branch capacities, so every reply reduces the remaining bound by one. A suffix of A followed clockwise by B points realizes these subset sizes with one cyclic interval, including irrelevant eliminated candidates harmlessly. At one remaining candidate its identity is forced. Evaluating the capacity formula gives all stated query limits, including 10 for N=92 and 56 for N=10^15.
Watch out. The grader can begin lying before the first question or never lie. Cyclic intervals with equal endpoints are empty. Keep the real judge interface; standard-input simulations are only local harnesses.
Commented C++17 solution
Judge submission: include the supplied findnumber.h and link this play function with the official grader. There is intentionally no main().
#include"findnumber.h"
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
using Integer=long long;
using Interval=pair<Integer,Integer>;
vector<Interval>mergeIntervals(vector<Interval>ranges){
sort(ranges.begin(),ranges.end());
vector<Interval>result;
for(auto range:ranges){
if(range.first==range.second){
continue;
}
if(!result.empty()&&range.first<=result.back().second){
result.back().second=max(result.back().second,range.second);
}
else{
result.push_back(range);
}
}
return result;
}
long long play(long long n){
Integer power[61],domain[61];
power[0]=1;
domain[0]=1;
for(int k=1;k<=60;++k){
power[k]=power[k-1]*2;
Integer s=power[k-1]/(k+1);
domain[k]=2*s+(power[k-1]-k*(s+1)==s?1:0);
}
Integer left=0,right=n;
vector<Interval>inverted;
while(true){
Integer a=right-left,b=0;
for(auto range:inverted){
b+=range.second-range.first;
}
if(a+b==1){
return a==1?left:inverted[0].first;
}
int questions=0;
while(a>domain[questions]||a*(questions+1)+b>power[questions]){
++questions;
}
Integer a1=a/2,a2=a-a1;
Integer capacity1=power[questions-1]-a1*questions;
Integer b1=max(0LL,a2+b-capacity1);
Integer queryLeft=right-a1,queryRight=right;
Integer remaining=b1;
// Walk B clockwise from the end of A, wrapping at n if necessary.
for(int pass=0;pass<2&&remaining>0;++pass){
for(auto range:inverted){
Integer begin=pass==0?max(range.first,right):range.first;
Integer end=pass==0?range.second:min(range.second,right);
if(begin>=end){
continue;
}
Integer amount=min(remaining,end-begin);
queryRight=begin+amount;
remaining-=amount;
if(remaining==0){
break;
}
}
}
vector<Interval>selected,rejected;
vector<Interval>question;
if(queryLeft<queryRight){
question.push_back({queryLeft,queryRight});
}
else if(queryLeft>queryRight){
question.push_back({queryLeft,n});
question.push_back({0,queryRight});
}
for(auto range:inverted){
vector<Integer>cuts={range.first,range.second};
for(auto part:question){
if(range.first<part.first&&part.first<range.second){
cuts.push_back(part.first);
}
if(range.first<part.second&&part.second<range.second){
cuts.push_back(part.second);
}
}
sort(cuts.begin(),cuts.end());
for(size_t i=1;i<cuts.size();++i){
if(cuts[i]==cuts[i-1]){
continue;
}
bool inside=false;
for(auto part:question){
if(part.first<=cuts[i-1]&&cuts[i-1]<part.second){
inside=true;
}
}
if(inside){
selected.push_back({cuts[i-1],cuts[i]});
}
else{
rejected.push_back({cuts[i-1],cuts[i]});
}
}
}
if(isInside(queryLeft,queryRight)){
rejected.push_back({left,right-a1});
left=right-a1;
inverted=mergeIntervals(rejected);
}
else{
selected.push_back({right-a1,right});
right-=a1;
inverted=mergeIntervals(selected);
}
}
}