Description

You are determined to get accepted on BalticOI, and the way to do that is studying. You walk into a bookstore. There are $N$ books on the shelf, numbered from $1$ to $N$. The difficulty of the $i$-th book is $x_i$. You want to choose $K$ books out of these $N$ books for studying. You do not want the material to be too easy or too hard, so you want to ensure that the sum of difficulties of these $K$ books lies in the interval $[A,2A]$.

Unfortunately, you do not know the exact values of $x_i$, so you need to skim the books to learn their difficulties. The shop owner is a neat freak and does not want you to skim too many books, so you are allowed to skim at most $S$ books and then decide. Luckily, you are told that as the book index increases, the difficulty is strictly increasing.

Please write a program that, by skimming books, buys the books you need, or reports that it is impossible.

Interaction Format

This is an interactive problem. You need to write the function void solve (int N, int K, long long A, int S). $N,K,A,S$ are defined above, and it is guaranteed that $x_1<x_2<\cdots<x_n$. This function is called exactly once.

You may also call the following functions:

• long long skim (int i) skims the $i$-th book to obtain its difficulty $x_i$.
• void answer (vector<int> v) buys the books you need. Here $v=\{i_1,i_2,\cdots,i_K\}$, and it must satisfy:

• void impossible () reports that it is impossible to buy $K$ books as required.

If there exist $K$ books satisfying the requirement, you must call answer exactly once. Otherwise, you must call impossible exactly once. After that, the program stops automatically.

If your function calls do not follow the format above, or if you call skim more than $S$ times, the program stops automatically and the test will be judged as Not correct. You must not output anything to standard output, otherwise you will be judged as Security violation.

If you use C++, please include the books.h header file. If you want to check the correctness of your program, you can download sample_grader.cpp and books_sample.cpp from the attachments below; they are used for correctness checking and as an example, respectively.

If you use Python, you can download books_sample.py from the attachments below for testing.

The interactive library expects two lines on standard input:

• The first line contains four integers, $N,K,A,S$.
• The second line contains $N$ integers, $x_1,x_2,\cdots,x_N$.

Then the interactive library will call your program. Finally, the interactive library will output a message to standard output:

For the error cases above, the interactive library will only return Not correct, or Correct when your solution is correct. Whenever any of the errors above occurs, or when your program calls answer or impossible, the program will be stopped automatically.

Input Format

See “Interaction Format”.

Output Format

See “Interaction Format”.

15 3 42 8

Hint

Sample 1 Explanation

$N=15$, $K=3$, $A=42$, $S=8$. Below are two possible sequences of calls that would be accepted:

Example 1:

Example 2:

Constraints and Assumptions

This problem uses bundled testdata.

• 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$.

For $100\%$ of the testdata, $K \le N$, $3 \le N,S \le 10^5$, $1 \le A,x_i \le 10^{17}$, $3 \le K \le 10$.

Note

Translated from BalticOI 2021 Day1 A A Difficulty Choice.

Translated by ChatGPT 5