Jack 和 Jill 在玩一个名为“更热，更冷”（Hotter, Colder）的游戏。Jill 有一个 $1$ 到 $N$ 之间的数字，Jack 需要通过反复猜测来猜出这个数字。

Jack 的每次猜测都是一个 $1$ 到 $N$ 之间的数字。对于每次猜测，Jill 会回答“更热”（hotter）、“更冷”（colder）或“相同”（same）。对于 Jack 的第一次猜测，Jill 总是回答“相同”。对于后续的猜测，Jill 的回答规则如下： 如果本次猜测比上一次猜测更接近 Jill 的数字，回答“更热”。 如果本次猜测比上一次猜测更远离 Jill 的数字，回答“更冷”。 * 如果本次猜测与上一次猜测相比，距离 Jill 的数字既没有更近也没有更远，回答“相同”。

你需要实现一个过程 HC(N) 来扮演 Jack 的角色。该实现可以反复调用 Guess(G)，其中 $G$ 是 $1$ 到 $N$ 之间的数字。Guess(G) 将返回 $1$ 表示“更热”，返回 $-1$ 表示“更冷”，返回 $0$ 表示“相同”。HC(N) 必须返回 Jill 的数字。

样例

假设 $N=5$，且 Jill 选择的数字是 $2$。当过程 HC 进行以下一系列 Guess 调用时，第二列将返回相应的结果。

此时 Jack 知道了答案，HC 应该返回 $2$。Jack 总共用了 $5$ 次猜测确定了 Jill 的数字。你可以做得更好。

子任务

子任务 1 [25 分]

HC(N) 调用 Guess(G) 的次数最多为 $500$ 次。对于 $N$ 在 $1$ 到 $500$ 之间的情况，最多会有 $125\,250$ 次对 HC(N) 的调用。

子任务 2 [25 分]

HC(N) 调用 Guess(G) 的次数最多为 $18$ 次。对于 $N$ 在 $1$ 到 $500$ 之间的情况，最多会有 $125\,250$ 次对 HC(N) 的调用。

子任务 3 [25 分]

HC(N) 调用 Guess(G) 的次数最多为 $16$ 次。对于 $N$ 在 $1$ 到 $500$ 之间的情况，最多会有 $125\,250$ 次对 HC(N) 的调用。

子任务 4 [最高 25 分]

令 $W$ 为满足 $2^W \le 3N$ 的最大整数。对于此子任务，你的得分规则如下： 如果 HC(N) 调用 Guess(G) 的次数达到 $2^W$ 次或更多，得 $0$ 分。 如果 HC(N) 调用 Guess(G) 的次数最多为 $2^W - \alpha W$ 次，得 $25\alpha$ 分，其中 $\alpha$ 是满足 $0 < \alpha < 1$ 的最大实数。 * 如果 HC(N) 调用 Guess(G) 的次数最多为 $W$ 次，得 $25$ 分。

对于 $N$ 在 $1$ 到 $500\,000\,000$ 之间的情况，最多会有 $1\,000\,000$ 次对 HC(N) 的调用。

请确保每次调用 HC 时都初始化所使用的任何变量。

实现细节

• 实现文件夹：/home/ioi2010-contestant/hottercolder/
• 选手需实现：hottercolder.c 或 hottercolder.cpp 或 hottercolder.pas
• 选手接口：hottercolder.h 或 hottercolder.pas
• 评测接口：grader.h 或 graderlib.pas
• 样例评测程序：grader.c 或 grader.cpp 或 grader.pas 以及 graderlib.pas
• 样例评测输入：grader.in.1, grader.in.2。 说明：输入文件包含多行，每行包含 $N$ 和 Jill 的数字。
• 样例评测的预期输出：评测程序将创建文件 grader.out.1, grader.out.2 等。
  • 如果实现正确完成了子任务 1，输出的一行将包含 OK 1
  • 如果实现正确完成了子任务 2，输出的一行将包含 OK 2
  • 如果实现正确完成了子任务 3，输出的一行将包含 OK 3
  • 如果实现正确完成了子任务 4，输出的一行将包含 OK 4 alpha α
• 编译并运行（命令行）：runc grader.c 或 runc grader.cpp 或 runc grader.pas
• 编译并运行（gedit 插件）：编辑任何实现文件时，按 Control-R。
• 提交（命令行）：submit grader.c 或 submit grader.cpp 或 submit grader.pas
• 提交（gedit 插件）：编辑任何实现文件或评测文件时，按 Control-J。