#46. 琪露诺猜数字

琪露诺猜数字

琪露诺猜数字

题目背景

琪露诺最近迷上了猜数字游戏。

灵梦偷偷想好了一个整数 xx,并告诉琪露诺:

1≤x≤1001 \le x \le 100

但是,她当然不会直接把答案告诉琪露诺。

琪露诺每次可以猜一个数字,灵梦则会告诉她:真正的答案比这个数字大、比这个数字小,还是刚好相等。

请你帮助琪露诺,在有限的询问次数内找到灵梦想好的数字。

本题是一道 交互题。


交互方式

你最多可以进行 7 次询问。

每次询问时,输出:

? y

其中 1≤y≤1001 \le y \le 100,表示你猜测答案是否为 yy。

输出后,你会得到一个字符作为回复:

  • <:表示 x<yx<y;
  • >:表示 x>yx>y;
  • =:表示 x=yx=y。

当你确定答案后,输出:

! y

其中 yy 为你认为的最终答案。

如果 y=xy=x,则你的程序成功完成任务。

否则,你的答案将被判定为错误。


询问限制

你最多只能进行 77 次形如

? y

的询问。

最终答案

! y

不计入询问次数。

如果询问次数超过 77 次,你的程序将被判定为错误。

所有询问中的 yy 都必须满足:

1≤y≤1001 \le y \le 100

注意事项

这是一道交互题。

每次输出询问后,你都必须立即 刷新输出缓冲区,否则交互器可能无法收到你的询问。

例如,在 C++ 中可以使用:

std::cout << "? " << y << std::endl;

其中 std::endl 会在输出换行后刷新缓冲区。

也可以使用:

std::cout << "? " << y << '\n';
std::cout.flush();

当你输出最终答案后,应立即结束程序:

std::cout << "! " << answer << std::endl;
return 0;

如果交互器已经返回错误结果,你的程序也应立即结束。


交互示例

假设灵梦想好的数字是 6565。

你的程序与交互器之间可能进行如下对话:

? 50
>
? 75
<
? 62
>
? 68
<
? 65
=
! 65

其中:

第一次询问 5050,交互器回答 >,说明答案大于 5050。

第二次询问 7575,交互器回答 <,说明答案小于 7575。

经过若干次询问后,可以确定答案为 6565。

注意:以上交互过程仅用于说明,本题不存在固定的样例输入输出。