计数近距离对(Count Close Pairs)

题目描述

这是一道交互题。

数轴上有 $N$ 个点，编号为 $1$ 到 $N$，从左到右排列。点 $i$ 的坐标为 $P_i$（实数），满足 $P_1 < P_2 < \ldots < P_N$。

最初你只知道 $N$。你可以向评判程序提问最多 $2N$ 次：

选择 $i, j$（$1 \leq i < j \leq N$），询问点 $i$ 和点 $j$ 的距离是否不超过 $1$。评判程序回答 Yes 或 No。

请输出距离不超过 $1$ 的点对 $(i, j)$（$i < j$）的数量。

交互格式

• 提问格式：? i j（$1 \leq i < j \leq N$），评判程序回答 Yes 或 No
• 答案格式：! X，其中 $X$ 为距离不超过 $1$ 的点对数量

注意事项

• 每次输出后需刷新标准输出（如 cout << flush 或 fflush(stdout)）
• 交互中输出无效或程序中途终止则结果不定
• 输出答案后立即终止程序

交互示例

$N = 3$，坐标为 $0, 0.7, 1.5$：

数据范围

• $2 \leq N \leq 10^3$
• $N$ 为整数
• 坐标 $P_i$ 为实数，满足 $P_1 < P_2 < \ldots < P_N$

知识点与难度

本题涉及的知识点从属于 GESP 三级，难度等级：⭐⭐。

测试点分布