| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 11 | 1 | 1 | 33.333% |
Teacher Laur organized a programming contest for his $N$ students and now wants to award them prizes according to their results. The prizes were lined up on a shelf in correct order, but then Toots toppled the shelf with his horseplay. As the prizes are in identical boxes, the teacher put them back on the shelf in a random order.
The prizes have different weights and the teacher has balance scales that he can use to compare two boxes and find out which is intended for the student with the better result. However, each weighing takes time and the first $M$ students have already lined up behind his door to receive their prizes...
To minimize the total time that students spend waiting for their prizes, the teacher wants to give each student their prize with as few weighings as possible. Write a program to help the teacher do that.
This is an interactive task. When your program starts, the first line of input contains $N,ドル the number of prizes $N$ (1ドル \le N \le 100$), and $M,ドル the number of students lined up (1ドル \le M \le N$). The prizes are numbered 1ドル \ldots N$ in their order on the shelf.
Then the grading system will give $M$ queries to your program. The program must process and answer each query; then the grading system gives the next query. After answering the last query, your program should quit.
Each query is given as integer $K$ (1ドル \le K \le N$), indicating the rank of the next student coming to collect their prize (there were no ties in the contest).
To process the query, your program may ask the teacher to perform a number of weighings. To request a weighing, the program should output a line of the form '? $A$ $B$', where $A$ and $B$ are the numbers of two prize boxes (1ドル \le A \le N,ドル 1ドル \le B \le N,ドル $A \ne B$). In response, the grading system will give the result of the weighing on the next line of input: '<' if the prize in the box $A$ is for the student with the better rank, or '>' otherwise.
When the program has identified the box holding the prize intended for the student ranked $K$-th, it should output a line of the form '! $C$', where $C$ is the number of the box (1ドル \le C \le N$); with that, the query is processed. If there are more queries, the grading system will issue the next one on the next input line. When the program has answered all the queries, it should quit.
In this task, a program that gives the wrong prize to any student will get 0ドル$ points for that test case. A program that gives the correct prizes to all students will get points according to how much time in total the students spent waiting for their prizes. Specifically, each weighing while there are $p$ students waiting will give the program $p$ penalty points and the program's score for a test case is $10ドル \cdot \min(0.1 + 0.9^{100 \cdot P / Q - 99}, 1)$$ of the value of the test case, where $Q = N \cdot M \cdot \log_2(N \cdot M) / 2$ and $P$ is the sum of penalty points the program got in the test case. You may assume that in all test cases, the orders of both the prizes and the students are chosen randomly.
3 2 1 > < 3 >
? 1 2 ? 2 3 ! 2 ? 1 3 ! 1
There are 3ドル$ prizes and 2ドル$ students waiting in this example. Suppose the order of the prizes is 3,ドル 1, 2$; that is, the first box contains the prize for the 3ドル$rd place, the second box the prize of the 1ドル$st place, and the third box the prize for the 2ドル$nd place.
The student who got the 1ドル$st place enters first. The program asks the teacher to weigh the boxes 1ドル$ and 2ドル$ and gets the response that the box 2ドル$ contains the better prize. Then the program asks the teacher to weigh the boxes 2ドル$ and 3ドル$ and gets the response that again the box 2ドル$ contains the better prize. Thus, the prize for the 1ドル$st place must be in the box 2ドル$ and the program outputs this as the answer.
The student who got the 3ドル$rd place enters next. The program asks the teacher to weigh the boxes 1ドル$ and 3ドル$ and gets the response that in this pair, the box 3ドル$ contains the better prize. Thus, the prize for the 3ドル$rd place must be in the box 1ドル$ and the program outputs this as the answer.
With that, all the queries are processed and the program quites, having accumulated 2ドル \cdot 2 + 1 \cdot 1 = 5$ penalty points (2ドル$ weighings with 2ドル$ students waiting and 1ドル$ weighing with 1ドル$ student waiting); thus the program scores 100ドル \%$ in this test case.