시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
20 초 (추가 시간 없음) | 1024 MB | 0 | 0 | 0 | 0.000% |
In this problem, when something is said to be chosen at random, it means uniformly at random from among all valid possibilities, and independently of any other choice.
Code Jam contestants once helped the mighty Goro sort an array of integers. (You do not need to read that problem to solve this one.) Once again, Goro needs your help. He has $\mathbf{N}$ boxes lined up on the table in a single row, numbered $1$ through $\mathbf{N}$ from left to right. Each box has exactly one ball inside. Balls are also numbered $1$ through $\mathbf{N}$. Goro wants ball $i$ to end up in box $i$, for all $i$. That is, he wants to leave the balls in sorted order. Unfortunately, that is not initially the case.
When Goro bumps the table with his powerful fists, balls pop up in the air and fall back in boxes. Goro can do this so accurately that exactly one ball falls into each box. A ball may fall into the same box it came out of, or into a different one.
Better yet, Goro also has the ability to assign colors to boxes before each bump. Then, he can bump the table in such a way that balls coming out of a box of color $c$ always fall into a box of color $c$. As impressive as this accuracy is, Goro does not have any more control than that. Within each color, balls end up assigned to boxes at random.
For example, suppose the balls appear in the order $1, 4, 3, 6, 5, 2$ (as seen above). He might choose — not necessarily optimally — to give the first box the color red, the second and sixth boxes the color green, and the third through fifth boxes the color blue. Then, after Goro bumps the table,
So, for example, the probability of the bump leaving the balls in the order $1, 2, 3, 5, 6, 4$ is $\frac{1}{12}$. If Goro got this or some other non-sorted result, he would have to designate a set of box colors for the next round, and so on, until he eventually arrives at the sorted $1, 2, 3, 4, 5, 6$. Goro can assign colors to boxes in any way before each bump, regardless of previous assignments.
Can you help Goro implement a better strategy that will efficiently sort the balls? It is guaranteed that the balls start in a random non-sorted order.
This is an interactive problem.
Initially, your program should read a single line containing three integers, $\mathbf{T}$ $\mathbf{N}$ $\mathbf{K}$: the number of test cases, the number of boxes per test case, and the total number of bumps allowed for all test cases combined. Then, $\mathbf{T}$ test cases must be processed.
Each test case begins with the judge sending one line with $\mathbf{N}$ integers, with each integer from $1$ to $\mathbf{N}$ appearing exactly once, and with the list chosen at random from all non-sorted lists. Then you must engage in a series of interactions with the judge. Each interaction works as follows:
As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment. Also, if your program continues to wait for the judge after receiving a $-1$, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error.
Be advised that the judge uses the same source of randomness each time, so in the absence of other errors (e.g. Time Limit Exceeded, Memory Limit Exceeded), submitting the exact same code twice will yield the same outcome twice.
2 4 8 1 4 3 2 0 1 4 3 2 1 2 1 4 3 1
1 2 3 2 1 2 3 2 4 4 4 4
Note that the sample interaction does not satisfy the constraints of any of the test sets. It is only presented to clarify the input and output format.
Contest > Google > Code Jam > Google Code Jam 2022 > Round 3 A번