P16532 [THUPC 2026 Final] Paper Review

From the final of the 2026 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2026). Resources such as editorials can be found at https://github.com/dapingguo8/THUPC2026-final. > After many fun activities came to an end, the venue welcomed a tea break during the intermission. During casual chats, people talked about how hard research is and how difficult it is to submit papers: Little T sighed that after each submission, he would keep withdrawing and resubmitting, polishing the paper again and again; while Little S, as a reviewer, said that he would certainly review strictly and try his best to filter out the manuscripts in hand. > > Based on this conversation, Little T and Little S suddenly had an idea: if they meet an extremely picky reviewer, what would the path to publication become? So they proposed a game model. In this model, the two sides will play as the author and the reviewer, playing a game around a long review queue. The queue is mixed with many other people's manuscripts, and only one paper is submitted by the author. The author hopes to let his paper cycle in the queue repeatedly for polishing, to increase its final academic score as much as possible when it gets published; while the reviewer will check strictly, looking for a chance to directly reject this paper so that the author gets nothing.

The review queue consists of $n$ papers, where the $m$-th paper is submitted by the author. Initially, the academic score of this paper is $1$. The game starts with the **author**, and then the two players take turns. On each turn, the current player must perform the following operations in order: 1. Take out $k$ papers one by one from the front of the review queue. If fewer than $k$ papers remain in the queue, take out all of them. 2. Among the papers taken out, choose to publish or permanently reject $0$ or $1$ paper, i.e., remove it completely. 3. Reinsert **all** papers that are not removed into the end of the review queue in **any** order. Since the review queue is fully public, both players can know the new position of each paper exactly after reinsertion. The author’s final score is determined by the result of his submitted paper: - On each turn, if this paper is not removed and is reinserted into the end of the review queue, its academic score increases by $1$; - If the **author** removes this paper in some operation, then the paper is successfully published, the game ends immediately, and the author gets the current academic score; - If the **reviewer** removes this paper in some operation, then the paper is permanently rejected, the game ends immediately, and the author gets $0$ points. The author’s goal is to maximize the score, while the reviewer’s goal is to minimize the author’s score. Little T and Little S saw your excellent performance in the previous game, so they invited you to analyze this interesting model. You need to compute the author’s final score when both the author and the reviewer use optimal strategies. If you can help them figure it out, maybe they will be willing to help you revise your paper in person!

Each test point contains multiple sets of testdata. The first line contains a positive integer $T \ (1 \le T \le 50)$, the number of test cases. For each test case: - The first line contains three positive integers $n, k, m \ (1 \le n, k \le 10 ^ 9, \ 1 \le m \le n)$, representing the length of the review queue, the number of papers taken out each turn, and the initial position of the author’s submitted paper.

For each test case, output one integer per line, representing the author’s final score. In particular, if the game will never end, output $-1$.

Translated by ChatGPT 5