The task is essentially binary searching for a number with the constraint that we get each answer with one query delay.
There are many subtasks with small n that still reward some nice points, that should ease out a bit of the thinking part.
The implementation is a bit annoying though. :'(

For n <= 50 we can fully summarize the current state of the problem in (l, r, x) -- what interval the hidden number is in and
what was the last query (that we do not know the answer of). Each time we should pay attention to the worst possible transition we can get into.
This leads to a O(n^4) dp solution -- O(n^3) states each with O(n) possible transistions.

Something we can easily notice about the dp is that the values of l and r (2 parameters) don't matter that much -- what matters is the length (1 parameter).
The easiest way to fix our previous solution is to always force l = 1 if that is not right. The complexity is now O(n^2).

Another reduction in the number of states is the following: notice that if, for example the hidden number is in [l, x - 1], it is really useless to consider
any states of the type (l, x - 1, y) for x - 1 <= y. This is not very useful by itself but hints at the idea of seperating the states in two types:
 -- the pending query will be useful;
 -- the pending query will not be useful.

For all dp states where the pending query will be useful, it is only reasonable to consider the optimal one. If the pending query will not be useful, you will waste
one query to transition in a state with a useful query. The number of states drops to O(n) and the complexity is now O(n^2).

Because of the analogy with binary search, it is reasonable to think that the dp values remain comperatively small. It seems a bit annoying to calculate so many
states and transitions for some answer that won't surpass 44 (see the statement). In such cases it is useful to think wheter we can "flip" the dp state -- 
right now for some length of the interval we calculate how many queries we need to find the hidden number.
Let's instead, for a fixed number of queries, find the longest interval we can answer using at most that many queries.

We preserve our idea about the (not) useful pending query and the dp state becomes (cnt_queries, pending)
useless query: ret = max(ret, get_max_length_with(query - 2, 0) + get_max_length_with(query - 2, 1) + 1);
useful  query: ret = max(ret, get_max_length_with(query - 1, 0) + get_max_length_with(query - 1, 1) + 1);

note that in the case of useless query, we have to spend another query to really orient ourselves in which subinterval to go.
the + 1 term is for the case where I hit the number and need to wait another query to finish the communication.

Using this information we can solve the O(nlogn) and O(logn) subtasks.

There are some partial solutions based on implementing binary/ternary search for the last subtask.