← 返回题目列表

Codeforces · 1039/B

B. 地铁追击

中文机器翻译题面 查看原题

这是一个交互问题。

在未来的美好大都市,不需要地铁司机。由于技术进步,它们被人工智能(AI)所取代。不幸的是,有一天,科幻作家的预言成真了:人工智能叛变了,现在地铁里出现了一列无法控制的火车。这可能很危险!你的任务是找到火车并阻止人工智能。

大都会地铁为单线(无自相交的常规直线),设有$$$n$$$个车站,从$$$1$$$到$$$n$$$连续索引。火车每时每刻都在某个车站。您需要确定该车站的索引,以便火车安全。

为了找到火车,调度员 Sarah 给了你一个小工具,允许你选择任意数字 $$$l$$$ 和 $$$r$$$ ($$$l \le r$$$),然后检查火车是否位于索引在 $$$l$$$ 和 $$$r$$$(含)之间的车站。不幸的是,该小工具的充电需要一些时间(并且每次您使用它时都要尽快),因此在该小工具的两次应用之间,火车可以移动到最多 $$$k$$$ 站外的任何车站。正式来说,如果应用小工具时火车位于车站 $$$x$$$,则在下一次应用小工具时,火车可以出现在任何车站 $$$y$$$,使得 $$$\max(1, x - k) \leq y \leq \min(n, x + k)$$$。

请注意,AI 并不知道您正在尝试赶火车,因此它会根据其预定义的计划进行所有移动。

检查该小工具后,您发现它非常旧,最多只能容纳$$$4500$$$应用程序,之后它就会损坏,您的任务将被视为失败。

您能使用不超过$$$4500$$$的小工具应用程序找到有火车的车站吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$0 \leq k \leq 10$$$) - 车站数量以及火车在小工具的两个应用程序之间可以移动的最大车站数量。

互动

您最多可以应用该小工具 $$$4500$$$ 次。为了应用该小工具,您需要打印两个空格分隔的整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$)。如果火车在 $$$l$$$ 站和 $$$r$$$ 站(含)之间,您将收到字符串“Yes”,否则会收到字符串“No”。如果 $$$l = r$$$ 并且您收到“是”,则您已成功找到火车,并且您的程序必须立即停止。

回答“不好”而不是“是”或“否”意味着您进行了无效查询或进行了太多查询。收到“Bad”后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出行尾并刷新输出。否则您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

为了破解,您应该以以下格式进行测试。

第一行应包含三个整数 $$$n$$$、$$$k$$$ 和 $$$p$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le k \le 10$$$, $$$1 \le p \le n$$$) - 车站数量,火车在该小工具的两个应用程序之间可以移动的最大车站数量和列车的初始位置。

接下来的 $$$4500$$$ 行应包含一个整数 $$$x$$$ ($$$1 \le x \le n$$$) - 每次查询后列车的位置。两个连续位置(包括第一个位置)的差异不应超过 $$$k$$$。

例如,以下行是示例测试的第一行。

示例

输入 #1

10 2
Yes
No
Yes
Yes

输出 #1

3 5
3 3
3 4
5 5

注意

在第一个示例中,火车最初位于 $$$5$$$ 车站,第一次应用该小工具后它没有移动,第二次应用后它移动到车站 $$$3$$$,第三次应用后再次移动到车站 $$$5$$$。