Writing

Finding the Rivals

The city where Taki lives consists of ~N~ houses, built along a straight line and numbered from ~1~ to ~N~, from left to right. Any two consecutive houses are ~1~ unit of distance apart.

In the same city, two of Taki's rivals live in houses ~A~ and ~B~, where ~A \lt B~. Taki does not know the locations of ~A~ and ~B~, but his friend Giannis does.

Giannis does not want his friend to get into fights, but he is tired of the excessive peace and quiet in his city. Therefore, he wants to reveal the secret locations to Taki in an... indirect way. Taki can point to a house ~X~ and Giannis will respond with the sum of the distances from ~X~ to houses ~A~ and ~B~, that is, ~|X - A| + |X - B|~. Taki has no time to waste. He wants to find his rivals' houses by asking Giannis at most ~Q~ questions of this kind.

Before Taki starts asking questions, Giannis tells him the number of houses, namely ~N~. Also, depending on his mood, Giannis may reveal the distance ~D~ between houses ~A~ and ~B~ (which is obviously equal to ~B - A~), but he may also choose not to reveal it.

Surprisingly, Taki managed to solve the problem. Now it's your turn! Put yourself in his shoes and find houses ~A~ and ~B~, without exceeding the limit of ~Q~ queries per test case.

Problem

This is an interactive problem. If you have never encountered this kind of problem before, consult the guide on the OJDP website (http://www.pdp.gr/). You can also download the compressed file grader.zip from the same website. It contains a sample program to help you understand how the interaction works, as well as a sample grader, along with commands to compile and run your code on your own computer.

Interaction:

Write a program that interacts with Giannis as Taki and attempts to solve one or more independent instances of the above problem, possibly with different values of ~N~, ~A~, and ~B~, but with the same ~Q~. Giannis will either reveal the distance ~D~ between the two houses in all instances of the problem, or he will not reveal it in any of them.

You must include the following line in your code:

• #include "findinglib.h" (in C++ or C)
• uses findinglib; (in Pascal)
• findinglib grader = new findinglib(); (in Java)

This gives you access to the following functions, through which you can interact with Giannis:

• int getSubtask();
• int getN();
• int getD();
• int query(int X);
• bool answer(int A, int B);

These functions work as follows:

1. The function ~getSubtask()~ returns the subtask number (see below), which will be the same for all instances within a test case.
2. The function ~getN()~ returns the number of houses, ~N~.
3. The function ~getD()~ returns the distance between houses ~A~ and ~B~, if Giannis chooses to reveal it; otherwise, it returns ~-1~.
4. The function ~query(X)~ returns Giannis's response when Taki points to house ~X~, that is, the sum of the distances from houses ~A~ and ~B~ to house ~X~. Obviously, ~1 \le X \le N~ must hold.
5. The function ~answer(A,;B)~ must be called at the end of each instance of the problem, once Taki has identified the hidden houses ~A~ and ~B~. The condition ~1 \le A \lt B \le N~ must hold. The function returns ~true~ if there will be another independent instance of the problem (with different values of ~N~, ~A~, and ~B~), or ~false~ if your program must stop its execution.

No input or output files are used for this problem. Your program communicates with the grader only through the functions listed above.

Example interaction:

\<table style="border-collapse:collapse;"> \<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">**Your program \<br> calls**\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">**Function \<br> returns**\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">**Description**\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~getN()~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~5~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">There are ~5~ houses, numbered from ~1~ to ~5~.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~getD()~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~2~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">Suppose the hidden houses are at positions ~2~ \<br> and ~4~ (of course, your program does not know this yet). \<br> The distance between the hidden houses is ~2~, and Giannis \<br> decides to reveal it.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~query(2)~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~2~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">The total distance from the two houses to position ~2~ \<br> is ~0 + 2 = 2~.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~query(3)~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~2~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">The total distance from the two houses to position ~3~ \<br> is ~1 + 1 = 2~.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~answer(2,4)~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~true~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">Taki correctly guesses the locations of the two houses. \<br> Another instance will follow.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~getN()~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~8~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">In the new instance, there are ~8~ houses.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~getD()~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~3~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">Suppose that this time the hidden houses are at positions \<br> ~1~ and ~4~. The distance between the hidden houses is ~3~, \<br> and Giannis reveals it again.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~query(8)~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~11~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">The total distance from the two houses to position ~8~ \<br> is ~7 + 4 = 11~.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~query(5)~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~5~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">The total distance from the two houses to position ~5~ \<br> is ~4 + 1 = 5~.\</td> \</tr>

\<tr style="border-bottom:1px solid black;border-top:1px solid;"> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;">~answer(1,4)~\</td> \<td style="text-align:center;white-space:nowrap;border-left:1px solid;border-right:1px solid;">~false~\</td> \<td style="text-align:left;white-space:nowrap;border-left:1px solid;border-right:1px solid;">Taki once again correctly guesses the locations of the two houses. \<br> There will be no further instances.\</td> \</tr>

\</table>

\<br>

Constraints

• ~3 \le N \le 1000~
• The sum of ~N~ over all instances in a test case will not exceed ~100.000~.
• ~1 \le A \lt B \le N~
• If you violate the communication protocol, your program will be terminated and the test case will be considered failed. The following are examples of communication protocol violations:

1. Calling ~query~ or ~answer~ with parameters outside the specified bounds.
2. Calling ~query~ more than ~Q~ times in any instance.
3. Calling ~answer~ with incorrect values of ~A~ and ~B~.
4. Calling any function after ~answer~ returns ~false~.
5. Using any input/output operation.

Subtasks:

In the first three subtasks, Giannis will reveal the distance ~D~ between houses ~A~ and ~B~.

1. (4 points) ~D = 1~, ~Q = 1000~
2. (6 points) ~Q = 1000~
3. (20 points) ~Q = 1~

In the remaining subtasks, Giannis will not reveal the distance between the houses.

1. (6 points) ~Q = 1000~
2. (9 points) ~Q = 37~
3. (12 points) ~Q = 21~
4. (17 points) ~Q = 11~
5. (26 points) ~Q = 2~

Notes:

• Maximum execution time: ~1~ sec.
• Maximum available memory: ~16~ MB.