영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
There is a hidden permutation P_1,P_2,…,P_N of length N, which is guaranteed to be generated uniformly at random. The permutation contains the numbers 1, 2, 3, …, N exactly once each in some unknown order.
You can choose positions l and r, and ask queries of the form: “What is the sum of P_l + P_{l+1} + … + P_r”?
Your task is to find the position of the number 1 in P using as few queries as possible. You will score points based on how few queries you use.
Interaction
Your program should first read two integers on a line, T and N. T is the number of rounds your program will be run, and N is the length of P.
Then there will be T rounds:
When a round begins, you may start asking questions. Output a line with “? a b” to ask for the sum of the numbers between positions a and b (1 ≤ a ≤ b ≤ N).
After each query, your program should read an integer: the sum of the values in the interval.
Once you have found the position where the number 1 is located, output a line of the form “! i”, where i is the index such that P_i = 1. After you output this, the next round begins.
Make sure to flush the output after each query, otherwise you may get a Time Limit Exceeded. In C++, this can be done with, for example, cout << flush or fflush(stdout); in Python with stdout.flush(); and in Java with System.out.flush().
Scoring
Your program will be tested on a single test case, with N = T = 1000.
If any round gives the wrong answer, the submission will be judged as Wrong Answer.
Let M be the number of queries your program makes across all T rounds. You will receive min(100, 220 - M/2500) points. If you get negative points, it will count as zero.
In other words, if you use more than 550,000 queries, you get 0 points, and if you use 300,000 or fewer queries, you get 100 points. In between, the score increases linearly.