Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
D
Take a Guess
Codeforces
1800
原题
← CE →
翻译中…

image

翻译中…

This is an interactive task

翻译中…

William has a certain sequence of integers $a_1, a_2, \dots, a_n$ in his mind, but due to security concerns, he does not want to reveal it to you completely. William is ready to respond to no more than $2 \cdot n$ of the following questions:

翻译中…
  • What is the result of a bitwise AND of two items with indices $i$ and $j$ ($i \neq j$)
  • What is the result of a bitwise OR of two items with indices $i$ and $j$ ($i \neq j$)
翻译中…

You can ask William these questions and you need to find the $k$-th smallest number of the sequence.

翻译中…

Formally the $k$-th smallest number is equal to the number at the $k$-th place in a 1-indexed array sorted in non-decreasing order. For example in array $[5, 3, 3, 10, 1]$ $4$th smallest number is equal to $5$, and $2$nd and $3$rd are $3$.

翻译中…

Input

翻译中…

It is guaranteed that for each element in a sequence the condition $0 \le a_i \le 10^9$ is satisfied.

翻译中…

Interaction

翻译中…

In the first line you will be given two integers $n$ and $k$ $(3 \le n \le 10^4, 1 \le k \le n)$, which are the number of items in the sequence $a$ and the number $k$.

翻译中…

After that, you can ask no more than $2 \cdot n$ questions (not including the "finish" operation).

翻译中…

Each line of your output may be of one of the following types:

翻译中…
  • "or i j" $(1 \le i, j \le n, i \neq j)$, where $i$ and $j$ are indices of items for which you want to calculate the bitwise OR.
  • "and i j" $(1 \le i, j \le n, i \neq j)$, where $i$ and $j$ are indices of items for which you want to calculate the bitwise AND.
  • "finish res", where $res$ is the $k$th smallest number in the sequence. After outputting this line the program execution must conclude.
翻译中…

In response to the first two types of queries, you will get an integer $x$, the result of the operation for the numbers you have selected.

翻译中…

After outputting a line do not forget to output a new line character and flush the output buffer. Otherwise you will get the "Idleness limit exceeded". To flush the buffer use:

翻译中…
  • fflush(stdout) in C++
  • System.out.flush() in Java
  • stdout.flush() in Python
  • flush(output) in Pascal
  • for other languages refer to documentation
翻译中…

If you perform an incorrect query the response will be $-1$. After receiving response $-1$ you must immediately halt your program in order to receive an "Incorrect answer" verdict.

翻译中…

Hacking

翻译中…

To perform a hack you will need to use the following format:

翻译中…

The first line must contain two integers $n$ and $k$ $(3 \le n \le 10^4, 1 \le k \le n)$, which are the number of items in the sequence $a$ and the number $k$.

翻译中…

The second line must contain $n$ integers $a_1, a_2, \dots, a_n$ $(0 \le a_i \le 10^9)$, the sequence $a$.

翻译中…

Note

翻译中…

In the example, the hidden sequence is $[1, 6, 4, 2, 3, 5, 4]$.

翻译中…

Below is the interaction in the example.

翻译中…
Query (contestant's program) Response (interactor) Notes
and 2 5 2 $a_2=6$, $a_5=3$. Interactor returns bitwise AND of the given numbers.
or 5 6 7 $a_5=3$, $a_6=5$. Interactor returns bitwise OR of the given numbers.
finish 5 $5$ is the correct answer. Note that you must find the value and not the index of the kth smallest number.
翻译中…

样例

Input #1
7 6

2

7
Output #1
and 2 5

or 5 6

finish 5
InputCopy OutputCopy
题目信息
题号
1556D
时间限制
2 s
内存限制
256 MB
标签
位运算
构造
交互题
数学

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。