题意#

这是一道交互题。

平面直角坐标系中有一个矩形。矩形的顶点都是整点，且四条边均与 $x$ 或 $y$ 轴平行。

你需要在最多 4 次询问中，求出这个矩形的周长。

每次询问，第一行输出 ? k，表示你要询问 $k$ 个点，第二行输出 $k$ 个坐标，表示询问的是这 $k$ 个点。之后，交互库会返回询问的 $k$ 个点在矩形内（包含边界）的点的个数。

若你已经确定了答案为 $p$，请输出 ! p。

这个坐标系的范围是 $1\leq x,y \leq 200$.

题解#

求周长 $\Leftrightarrow$ 求出两个边长。

设矩形边上分别有 $x,y$ 个点（面积为 $(x-1)(y-1)$，周长为 $x+y-2$）

先对整个棋盘都查询一遍，得到 $s=x\times y$，还剩三次查询。

考虑隔行查询，对所有形如 $(ki, j)$,$1\leq i\leq \lfloor\frac{200}{d}\rfloor,1\leq j\leq 200$ 的点进行查询，设答案为 $f(k)$.

哪些 $f(k)$ 能与已经查询过的 $f(1)$ 产生联系？

如上图，$2^k\mid x\Leftrightarrow k \times f(2^k)=f(1)$，注意到，若 $2^k\mid x$ 且 $2^{k+1}\nmid x$，则有：

$$|f(2^k)-2f(2^{k+1})|=y$$

显然 $k\in\{0,1,2,3,4,5,6,7\}$，有八种可能，直接二分即可将询问次数降至 $3$ 次。

二分：若 $2^t\nmid x$，说明 $k\in[0, t-1]$.