CF1867E1.Salyg1n and Array (simple version)
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is the simple version of the problem. The only difference between the versions is the limit on the number of queries. In this version, you can make no more than 100 queries. You can make hacks only if both versions of the problem are solved.
This is an interactive problem!
salyg1n has given you a positive integer k and wants to play a game with you. He has chosen an array of n integers a1,a2,…,an ( 1≤ai≤109 ). You must print a1⊕a2⊕…⊕an , where ⊕ denotes the bitwise XOR operation. You can make queries of the following type:
- ? i : in response to this query, you will receive ai⊕ai+1⊕…⊕ai+k−1 . Also, after this query, the subarray ai,ai+1,…,ai+k−1 will be reversed, i.e., the chosen array a will become: a1,a2,…ai−1,ai+k−1,ai+k−2,…,ai+1,ai,ai+k,…,an .
You can make no more than 100 queries to answer the problem.
输入格式
The first line contains a single integer t ( 1≤t≤1000 ) – the number of test cases.
输出格式
The interaction between your program and the jury's program begins with reading two positive even integers n and k ( 1≤k≤n≤k2≤2500 ) – the length of the chosen array and the length of the query subarray, respectively.
To find the value of ai⊕ai+1⊕…⊕ai+k−1 , print the query in the format ? i ( 1≤i≤n−k+1 ). Then read a single integer – the answer to your query.
You can make no more than 100 queries. When you are ready to print the answer, output it in the format ! x . After that, proceed to process the next test case or terminate the program if it was the last test case. Printing the answer does not count as one of the 100 queries.
If your program makes more than 100 queries for one set of input data, or makes an invalid query, then the response to the query will be -1. After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
It is guaranteed that the sum of n over all test cases does not exceed 10000 . The interactor in this problem is not adaptive.Hacks:
To perform a hack, use the following format:
The first line contains a single integer t – the number of test cases.
The description of each test case should consist of two lines. The first line contains the numbers n and k – the length of the chosen array and the length of the query subarray, respectively. The second line contains n numbers a1,a2,…,an – the array that the jury should choose for this test case.
输入输出样例
输入#1
2 4 2 6 4 6 6 4
输出#1
? 1 ? 3 ! 2 ? 1 ! 4
说明/提示
In the first test case, the jury has chosen the array a = [4,2,5,1]
In the second test case, the jury has chosen the array a = [5,7,1,3,3,7]