题目链接

题目大意：

交互题，给定 N = 2 或 18 或 64 或 512 或 1000，其中你要通过 19 次以内的询问在数列 1 - N 中找到给定的未知的两个数 x 和 y（本题解中设 x < y)，每次询问可以选择任意个数，若这任意个数中含有 x 和 y 中的一个则返回 1，否则返回 2。

10pts：

当 N = 2 时，我们可以轻易地发现 x 和 y 必分别为 1 和 2，直接输出就解决了。

20pts：

当 N = 18时，我们可以从 1 开始询问，每次询问后加上后一个数字，这样当返回值从 0 变为 1 时，则代表加入的数字为 x，当返回值再次从 1 变回 0 时，则代表加入的数字为 y。因为总共仅有 18 个数，故 19 次询问足以解决这种情况。

30pts：

好了，从现在起，前面的乱搞做法算是落下尾声了。正式拿到这道题，首先看到的就是极具特色的数据规模，除却前两个水点和最后一个接近但不完全是的 N = 1000 以外，所有的数据规模均为 2 的次幂。显然，这道题将与 二分 或是 倍增 有很强的联系。然而倍增由于需要再向后重新减去，相当于有一个常数为 4，这基本上排除了倍增的可行性，所以我们将目光射向二分。

显而易见的是，一旦程序得到了 1 的返回值，很快就可以用二分解决掉，几乎可以不做讨论，如果同学们有所疑惑，可以先在这里想一下，并不复杂，在这里不再赘述。

然而同学们只要简单地动手尝试一下平常的二分并采用最坏的不到最后不会出现 1 的情况就会发现，19 次的二分不足以支持这道题哪怕是 30pts 的解决，进而我们要尝试利用这道题目与普通二分的不同点来优化二分。而一个不太明显的特征是，本题的二分并不需要使用平常二分的单调性，所以我们可以把选取的段放在前一次二分的两段的中间，这样就可以利用上一步二分来只用一步变将整段化作四段。语言可能相对难以理解，上图！

图中红色部分为第一次询问，绿色部分为第二次询问。

在第一次询问中，返回值为 0，那么我们知道要么是 ① + ② 中有 x 和 y，要么是 ③ + ④ 中有 x 和 y。

在第二次询问中，返回值为 0，那么我们知道要么是 ① + ④ 中有 x 和 y，要么是 ② + ③ 中有 x 和 y。

综上所述，x 和 y 要么在 ① 中，要么在 ② 中，要么在 ③ 中，要么在 ④ 中，绝不会出现在某两个四分之一块中的情况，而使用一般的二分，达到这一步需要询问三次。

接着，我们在 ① 和 ② 两个块中间再使用一次绿色询问，就可以再把这两块分成四块，以此类推，我们可以节省一半的询问次数，30pts 成功解决。