分数: 500 点
问题陈述
这是一个交互式任务 (您的程序通过输入和输出与法官的程序交互)。
我们有一个 N-by-N 棋盘和 N 车。下面的广场 i从顶部算起的第行和 j从左边算起的第列表示为 (i, j).
考虑将车放在棋盘的方格上。在这里,您必须放置车以满足以下所有条件。
- 没有行包含两个或更多车。
- 没有列包含两个或更多车。
现在, N-1 车被放置在棋盘上,以满足上述所有条件。您将选择一个未被车占据的方格,并将车放在该方格上。 (可以证明,在该条件下,至少有一个格子可以放置车。)
但是,您无法直接看到棋盘上的哪些方格被车占据。
相反,你最多可能会问 20 按以下方式向法官提问。
- 您选择整数 A, B, C,和 D 这样 1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N,询问正方形形成的矩形区域内的车数量 (i, j) 这样 A \leq i \leq B, C \leq j \leq D.
找到一个方格来放置车。
约束
- 2 \leq N \leq 10^3
- N 是一个整数。
输入和输出
这是一个交互式任务(您的程序通过输入和输出与法官的程序交互)。
首先,接收棋盘的尺寸, N,来自标准输入。
N
接下来,重复问一个问题,直到找到一个可以放置车的方块。
问题应按以下格式打印到标准输出:
? A B C D
标准输入将以以下格式给出响应:
T
在这里, T 是对问题的回答,或者 -1 如果问题无效或超过 20 已提出问题。
当法官返回时 -1,提交已被视为不正确。在这种情况下,请立即终止程序。
当你找到一个可以放置车的格子时,让 (X, Y) 是那个正方形并按以下格式打印答案。然后,立即终止程序。
! X Y
如果有多个合适的答案,则其中任何一个都将被接受。
注释
- 每次打印内容时,以换行符结束,然后刷新标准输出。否则,您可能会得到一个 TLE 判决。
- 如果在交互过程中打印出无效的输出,则结论将是不确定的。
- 打印答案后立即终止程序。否则,判决将是不确定的。
示例交互
下面是一个交互,其中 N=3 车被放置在 (1, 2) 和 (2, 1).
| 输入 | 输出 | 说明 |
|---|---|---|
3 |
判断首先给出整数 N. | |
? 1 2 1 3 |
参与者提出问题 (A,B,C,D)=(1,2,1,3). | |
2 |
法官返回问题的答案,即 2. | |
? 2 3 1 1 |
参与者提出问题 (A,B,C,D)=(2,3,1,1). | |
1 |
法官返回问题的答案,即 1. | |
? 1 3 3 3 |
参与者提出问题 (A,B,C,D)=(1,3,3,3). | |
0 |
法官返回问题的答案,即 0. | |
! 3 3 |
参与者发现答案是 (3, 3) 并打印它。 |