Library game
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: games, greedy, interactive, sortings

Alessia and Bernardo are discovering the world of competitive programming through the books of their university library.

The library consists of $$$m$$$ sections numbered from $$$1$$$ to $$$m$$$. Each section contains only books dedicated to a particular subject and different sections correspond to different subjects. In order to prevent the students from wandering in the library, the university has established a system of passes. Each pass has a length $$$y$$$ associated to it and allows access to an interval of $$$y$$$ consecutive sections in the library. During a visit, the student must choose exactly one book from one of these sections and leave the library. Each pass can be used only once.

At the moment Alessia and Bernardo have $$$n$$$ passes of lengths $$$x_1, \, x_2, \, \dots, \, x_n$$$. They have different opinions on the best way to improve: Alessia thinks that it is important to study many different topics, while Bernardo believes that it is important to study deeply at least one topic. So, Alessia wants to use the $$$n$$$ passes to get $$$n$$$ books on distinct topics, while Bernardo would like to get at least two books on the same topic.

They have reached the following agreement: for each of the following $$$n$$$ days, Alessia will choose a pass of length $$$y$$$ among those which are still available and an interval of $$$y$$$ sections in the library, and Bernardo will go into the library and will take exactly one book from one of those sections.

Can Bernardo manage to get at least two books on the same subject, or will Alessia be able to avoid it?

You should decide whether you want to be Alessia or Bernardo, and you have to fulfill the goal of your chosen character. The judge will impersonate the other character. Note that, even if at some moment Bernardo has already taken two books on the same subject, the interaction should go on until the end of the $$$n$$$ days.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$n \le m \le 5000$$$) — the number of passes and the number of sections.

The second line contains $$$n$$$ integers $$$x_1, \, x_2, \, \dots, \, x_n$$$ ($$$1 \le x_i \le m$$$) — the lengths of the passes available.

Interaction format:
First, you should print a line containing either the string $$$\texttt{Alessia}$$$ or the string $$$\texttt{Bernardo}$$$ — the character that you want to impersonate.

Then, for each of the $$$n$$$ turns:

- If you are taking the role of Alessia, print a single line consisting of two integers $$$y$$$ and $$$a$$$ ($$$1 \le a \le m - y + 1$$$) — you are choosing a pass of length $$$y$$$ and the interval of sections $$$[a, a + y - 1]$$$. Note that at least one pass of length $$$y$$$ must still be available. After this, read a single integer $$$b$$$ ($$$a \le b \le a + y - 1$$$) — the subject of the book selected by Bernardo.
- If you are taking the role of Bernardo, read two integers $$$y$$$ and $$$a$$$ ($$$1 \le a \le m - y + 1$$$) — the length of the pass chosen by Alessia and the index of the first section of the interval. It is guaranteed that there is at least one pass of length $$$y$$$ available. Then, print a line consisting of a single integer $$$b$$$ ($$$a \le b \le a + y - 1$$$) — the subject from which you choose to take a book.

If one of your interactions is malformed, the interactor terminates immediately and your program receives the verdict $$$\texttt{WRONG-ANSWER}$$$. Otherwise, you will receive the verdict according to the game's criteria described above.

After printing a line do not forget to end the line and flush the output. Otherwise, you will get the verdict $$$\texttt{TIMELIMIT}$$$. To flush the output, use:

- $$$\texttt{fflush(stdout)}$$$ in C;
- $$$\texttt{fflush(stdout)}$$$, $$$\texttt{cout <}\texttt{< flush}$$$ or $$$\texttt{cout.flush()}$$$ in C++;
- $$$\texttt{System.out.flush()}$$$ in Java and Kotlin;
- $$$\texttt{sys.stdout.flush()}$$$ in Python.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, it can be shown that Alessia can accomplish her goal. An example of interaction (after reading the input) follows:

$$$$$$ \begin{array}{|c|c|c|} \hline \textbf{Contestant} & \textbf{Judge} & \textbf{Explanation} \\ \hline \texttt{Alessia} & & \text{The program will act as Alessia} \\ \hline 3 \quad 11 & & \text{Choose $y = 3$ and $a = 11$} \\ \hline & 13 & \text{Judge selects $b = 13$} \\ \hline 10 \quad 2 & & \text{Choose $y = 10$ and $a = 2$} \\ \hline & 9 & \text{Judge selects $b = 9$} \\ \hline 7 \quad 1 & & \text{Choose $y = 7$ and $a = 1$} \\ \hline & 4 & \text{Judge selects $b = 4$} \\ \hline 2 \quad 10 & & \text{Choose $y = 2$ and $a = 10$} \\ \hline & 10 & \text{Judge selects $b = 10$} \\ \hline 3 \quad 6 & & \text{Choose $y = 3$ and $a = 6$} \\ \hline & 7 & \text{Judge selects $b = 7$} \\ \hline \end{array} $$$$$$

The program of the contestant wins because all the books chosen by Bernardo pertain to different topics. The actions performed by the contestant and the judge in this example of interaction may be non-optimal.

In the second sample, it can be shown that Bernardo can manage to fulfil his goal. An example of interaction (after reading the input) follows:

$$$$$$ \begin{array}{|c|c|c|} \hline \textbf{Contestant} & \textbf{Judge} & \textbf{Explanation} \\ \hline \texttt{Bernardo} & & \text{The program will act as Bernardo} \\ \hline & 4 \quad 1 & \text{Judge chooses $y = 4$ and $a = 1$} \\ \hline 4 & & \text{Select $b = 4$} \\ \hline & 1 \quad 10 & \text{Judge chooses $y = 1$ and $a = 10$} \\ \hline 10 & & \text{Select $b = 10$} \\ \hline & 6 \quad 3 & \text{Judge chooses $y = 6$ and $a = 3$} \\ \hline 4 & & \text{Select $b = 4$} \\ \hline & 4 \quad 5 & \text{Judge chooses $y = 4$ and $a = 5$} \\ \hline 8 & & \text{Select $b = 8$} \\ \hline \end{array} $$$$$$

The program of the contestant wins because Bernardo has selected two books on topic number $$$4$$$. The actions performed by the contestant and the judge in this example of interaction may be non-optimal.

Example input:
5 14
3 7 2 3 10

Example output:
-

Example input:
4 10
4 1 6 4

Example output:
-

Editorial:
Sort the numbers $$$x_1, x_2, \dots, x_n$$$ in decreasing order, i.e. $$$x_1 \ge x_2 \ge \cdots \ge x_n$$$. For a real number $$$x$$$, let $$$\lfloor x \rfloor$$$ and $$$\lceil x \rceil$$$ denote, respectively the floor function of $$$x$$$ (that is, the largest integer which does not exceed $$$x$$$) and the ceil function of $$$x$$$ (that is, the smallest integer which is not less than $$$x$$$).
Lemma. Bernardo has a winning strategy if and only if there exists an index $$$1 \le k \le n$$$ such that $$$x_k > \lfloor m/k \rfloor$$$.
Proof. We will show the correctness of the criterion above by exhibiting a winning strategy for both Alessia (when the condition is not satisfied) and Bernardo (when the condition is satisfied).
• First, suppose that such an index $$$k$$$ does not exist. Alessia will play by choosing the number $$$x_i$$$ in her $$$i$$$-th turn (recall that the $$$x_i$$$'s are sorted decreasingly). Let us show that, at the beginning of Alessia's $$$i$$$-th turn, there is necessarily an interval of length $$$x_i$$$ that does not contain any number selected by Bernardo. Indeed, Bernardo has so far selected $$$i - 1$$$ numbers, which form $$$i$$$ "gaps" among the numbers $$$1, 2, \dots, m$$$. By the pigeonhole principle, one of these gaps contains at least $$$\left\lceil \frac{m - i + 1}{i} \right\rceil = \left\lfloor \frac{m}{i} \right\rfloor \ge x_i$$$, where the last inequality follows from our hypothesis. Then, Alessia can safely choose this interval.
• Now suppose that $$$x_k > \lfloor m/k \rfloor$$$ for some $$$k$$$. Bernardo will play every turn as follows: if the interval chosen by Alessia contains at least one multiple of $$$x_k$$$, he selects one of those multiples; otherwise, he selects any number in the interval. Note that, every time Alessia chooses an $$$x_i$$$ with $$$i \le k$$$, whatever interval she chooses next will contain a multiple of $$$x_k$$$ (because $$$x_i \ge x_k$$$). Since there are $$$\lfloor m/x_k \rfloor$$$ multiples of $$$x_k$$$ in $$$[1, m]$$$, and the condition $$$x_k > \lfloor m/k \rfloor$$$ is equivalent to $$$k > \lfloor m/x_k \rfloor$$$, again by the pigeonhole principle there will necessarily be a turn where the multiple of $$$x_k$$$ selected by Bernardo was already selected previously.
Implementing the strategies described is not difficult, due to the generous constraints that allow for implementations with $$$\mathcal O(nm)$$$ runtime.
Remark. In fact, if a "bad" $$$k$$$ exists it is necessarily greater than $$$1$$$, since $$$a_1 \le m$$$ by the problem assumptions.
Remark. In the proofs above, we took for granted that $$$\left\lceil \frac{m - i + 1}{i} \right\rceil = \left\lfloor \frac{m}{i} \right\rfloor$$$ and that $$$x_k > \lfloor m/k \rfloor$$$ if and only if $$$k > \lfloor m/x_k \rfloor$$$. The former is the well-known $$$\left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a + b - 1}{b} \right\rfloor$$$ when $$$a$$$, $$$b$$$ are integers (just replace $$$a$$$ with $$$m - i + 1$$$ and $$$b$$$ with $$$i$$$). The latter can be proved by observing that both inequalities are equivalent to $$$k \cdot x_k > m$$$.
Understanding the game's criterion
How does one come up with Bernardo's winning condition $$$x_k > \lfloor m/k \rfloor$$$? While everyone has their own combination of methods, intuition and luck, in this problem it can be particularly useful to focus on small values of $$$n$$$, and specifically on the case $$$n = 2$$$ ($$$n = 1$$$ is not interesting at all: Alessia always wins!).
For $$$n = 2$$$, it might be easier to visualize what is going on, and to figure out that Bernardo wants to select the first number so that it is as close as possible to $$$m/2$$$ (indeed, he wants to minimize the largest of the two gaps that the selected number creates). After understanding this case, one can try to generalize to other values of $$$n$$$.