分数: 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.
由于回答的对数也是正确的,因此如果程序在此之后立即终止,则判断为正确。