← 返回题目列表

AtCoder · abc466_c

C. 计算接近的对

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

分数: 300 点

问题陈述

这是一个 交互问题 (您的程序和判断程序通过标准输入和输出进行通信)。

在数轴上,点 1, 2, \ldots, N 从左到右排列 按此顺序.

最初,您只得到整数 N.

那么,你最多可以问法官以下问题 \bm{2N} 次。

  • 选择整数 i 和 j 满意 1 \leq i < j \leq N,询问点之间的距离是否 i 和 j 最多是 1.

输出距离最大的点对的数量 1,即整数对的数量 (i,j) 满意 1 \leq i < j \leq N 使得点之间的距离 i 和 j 最多是 1.

约束

  • 2 \leq N \leq 10^3
  • N 是一个整数。

互动

首先,接收整数 N 代表标准输入的点数:

N

然后,你最多可以向评委重复问题陈述中描述的问题 2N 次。

按以下格式将问题输出到标准输出, 哪里 i 和 j 必须是满足以下条件的整数 1 \leq i<j \leq N:

? i j

作为对此的响应,标准输入将给出以下内容之一:

Yes
No

在这里, Yes 表示点之间的距离 i 和 j 最多是 1,和 No 表示点之间的距离 i 和 j 大于 1.

一旦你找到答案 X 针对问题,按以下格式输出答案,然后立即终止程序:

! X

注释

  • 每次输出内容时,在末尾插入换行符并刷新标准输出。否则,判断结果可能是 TLE.
  • 如果在交互过程中输出了无效的内容,或者程序提前终止,则判断结果是不确定的。
  • 输出答案后立即终止程序。否则,判定结果不确定。
  • 分数和答案的排列在您与评委之间的互动开始时就已固定,并且不会根据您提出的问题等因素而改变。

示例交互

下面是一个交互示例,其中 N = 3 和点的坐标 分别为 1,2,3 是 0, 0.7, 1.5。 (点的坐标 1,2,3 未作为输入给出。) 给出了

输入 输出 说明
3 N 。
? 1 2 询问判断点间距离是否 1 和 2 最多是 1.
Yes 从判断点之间的距离获取响应 1 和 2 最多是 1.
? 1 3 询问判断点间距离是否 1 和 3 最多是 1.
No 从判断点之间的距离获取响应 1 和 3 最多不是 1.
? 2 3 询问判断点间距离是否 2 和 3 最多是 1.
Yes 从判断点之间的距离获取响应 2 和 3 最多是 1.
! 2 答案 2 作为满足条件的对的数量。

问题数量为 3,特别是最多 2N=6.
由于回答的对数也是正确的,因此如果程序在此之后立即终止,则判断为正确。