P8122 [BalticOI 2021] A Difficulty Choice (Day1)

**本题为交互题。** 感谢交互库与 checker 的提供者 [Hi_chocolate](https://www.luogu.com.cn/user/193198) 为本题做出的巨大贡献。 ### 特别提示 **在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：** 1. 提交时请在程序里加入以下函数声明语句： ```cpp extern "C" long long skim (int i); extern "C" void answer (std::vector v); extern "C" void impossible (); ``` 你实现的 `solve` 函数应为： ```cpp extern "C" void solve (int N, int K, long long A, int S); ``` 2. 程序开头不用，也不应该包含 `books.h` 头文件。 3. 仅支持 `C++`（含 `C++`，`C++11`，`C++14`，`C++17`）提交。

您致力于 AK BalticOI，而 AK BalticOI 的方式就是学习。您走进了一家书店，架子上有 $N$ 本书，编号为 $1$ 到 $N$，第 $i$ 本的难度为 $x_i$。您要从这 $N$ 本书中挑选出 $K$ 本书用来学习，您不希望学到太简单或太难的东西，所以您想要保证这 $K$ 本书的难度之和位于 $[A,2A]$ 的区间内。 可惜的是，您并不知道 $x_i$ 的具体数值，所以您要浏览这些书籍以得知他们的难度。书店老板有洁癖，他不希望您浏览太多的书籍，所以他规定您最多只能浏览 $S$ 本书，然后确定这些书的难度。幸运的是，您被告知这 $N$ 本书按照编号的增加，难度呈单调递增。 请编写一个程序，通过浏览书籍，购买您需要的书籍，或者指出无解。 ### 交互格式 本题为交互题，您需要编写 `void solve (int N, int K, long long A, int S)` 函数，$N,K,A,S$ 在上面已经定义，并且保证 $x_1

见「交互格式」。

见「交互格式」。

#### 样例 1 解释 $N=15$，$K=3$，$A=42$，$S=8$，下面是可能的两种会被判为通过的调用结果： 示例 1： |你的程序|返回值| |:-:|:-:| |`skim(1)`|$1337$| |`impossible`|-| 示例 2： |你的程序|返回值| |:-:|:-:| |`skim(1)`|$7$| |`skim(15)`|$21$| |`answer({11,15,7})`|-| #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$S=N$，$170 \le N \le 1000$，$K=3$。 - Subtask 2（15 pts）：$S=N$，$N \ge 170$。 - Subtask 3（10 pts）：$S \ge 170$，$x_{i+1}-x_i \le \frac A K$。 - Subtask 4（15 pts）：$S \ge 170$，$x_{i+1}-x_i \le A$。 - Subtask 5（15 pts）：$S \ge 170$。 - Subtask 6（20 pts）：$S \ge 40$，$x_{i+1}-x_i \le A$。 - Subtask 7（20 pts）：$S \ge 40$。 对于 $100\%$ 的数据，$K \le N$，$3 \le N,S \le 10^5$，$1 \le A,x_i \le 10^{17}$，$3 \le K \le 10$。 #### 说明 翻译自 [BalticOI 2021 Day1 A A Difficulty Choice](https://boi.cses.fi/files/boi2021_day1.pdf)。