← 返回题目列表

AtCoder · abc269_e

H. 最后一辆车

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

分数: 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) 并打印它。