308678: CF1556D. Take a Guess

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Take a Guess

题意翻译

这是一道交互题,给定两个正整数 $n,k$,你需要通过 $\leq2n$ 次询问猜出长度为 $n$ 的序列 $\{a_i\}$ 中的第 $k$ 小值。 询问分为两种类型: 1. `or i j`,交互器会返回 $a_i \operatorname{or}a_j$ 的值。 2. `and i j`,交互器会返回 $a_i\operatorname{and}a_j$ 的值。 其中需要满足 $1\leq i,j\leq n$ 且 $i\not = j$。 最后你需要输出 `finish res`,其中 $res$ 表示你的答案。 $3\leq n \leq 10^4,1\leq k\leq n,0\leq a_i\leq 10^9$。

题目描述

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1556D/63568455333cc0a029d6e5fa4f79ae6dd332397f.png)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](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of two items with indices $ i $ and $ j $ ( $ i \neq j $ ) - What is the result of a [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#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 $ .

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

7 6

2

7

输出样例 #1

and 2 5

or 5 6

finish 5

说明

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

题意翻译

这是一道交互题,给定两个正整数 $n,k$,你需要通过 $\leq2n$ 次询问猜出长度为 $n$ 的序列 $\{a_i\}$ 中的第 $k$ 小值。 询问分为两种类型: 1. `or i j`,交互器会返回 $a_i \operatorname{or}a_j$ 的值。 2. `and i j`,交互器会返回 $a_i\operatorname{and}a_j$ 的值。 其中需要满足 $1\leq i,j\leq n$ 且 $i\not = j$。 最后你需要输出 `finish res`,其中 $res$ 表示你的答案。 $3\leq n \leq 10^4,1\leq k\leq n,0\leq a_i\leq 10^9$。

加入题单

上一题 下一题 算法标签: