- Whenever I've to face an interactive problem, I just change the question.
- i.e., I get scared because once I tried to solve Interactive Promblem and all time I got Idleness Limit Exceeded and after that day I ne'er solved any interactive question.
- But yesterday I found a nice problem which boosted my confidence over solving interactives.
- The question link...
So in this question my approch was :
- Check for the answer between l and r.
- Do it till we get answer from computer as "x";
- Now to identify what will be l and r,
- Use bitmask, like
Firstly l= 1st bit 1 and all zero before and after that, r=next bit of l (MSB of l)+1 to be 1 and all zero. Increase 1 bit each time.
(0, 1) then, (1, 10) then, (10, 100) and so on... (In binary representation).
This will lead to check answer between powers of 2.
(0,1) then (1,2) then (2,4) and so on..(till 2^31)
Now we do this to identify our answer lies between l+1 and r we get.
This is because l will be smallest number with that MSB so we check for all powers of 2.
We can get this in at most 31 queries.
Now,
If we binary search between l+1 and r then we will find our answer within 30 queries.
The binary search approch was like,
let m=(l+r)/2;
Ask for answer between l and m (Here we just need to print (? l m) and take input from computer).
If answer is "x" then shift r to m, shift l to m otherwise.
Hence, answer is l+1.
Now,
As we are dealing with interactive problem so we need to flush the output we give.
For that use 'endl' after each cout instead of '\n'.
That's all we need to change between a regular problem and interactive problem.
We can also use fflush(stdout) but 'endl' does it.
It was a blessing in disguise.
So I just want to conclude that Interactive problems ain't that arduous to deal with.
Thank You and let me know if I'm wrong.
