問題一覧 > 通常問題

No.2845 Birthday Pattern in Two Different Calendars

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 66
作問者 : 👑 AngrySadEight / テスター : 👑 qand torisasami4
お気に入りにしたユーザー ProblemId : 11019 / 自分の提出
問題文最終更新日: 2024-07-17 00:52:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 441 (順位表) の他の問題:

Problem Statement

There are $2$ countries, Country yuki and Country coder. In both of these $2$ countries, $1$ year consists of $K$ days, and they use a calendar in which a date is written as "Day $n$", simply using the integer $n$ that indicates which day of the $1$ year it is (months are not used to represent dates).

However, the calendar of Country yuki and the calendar of Country coder differ in when the $1$ year begins.

Specifically, when it is Day $1$ in the calendar of Country yuki, it is Day $M$ in the calendar of Country coder. More generally, when it is Day $k$ in the calendar of Country yuki, it is Day $((k + M - 2) \bmod{K}) + 1$ in the calendar of Country coder.

For example, when $K = 7, M = 4$, the situation is as shown in the figure below.

Determine whether there exists a set of birthdays of $N$ people satisfying the following condition, and if one exists, output $1$ possible set of birthdays of those $N$ people in the calendar of Country yuki.

  • Let Day $A_i$ be the birthday of the $i(1 \leq i \leq N)$-th person in the calendar of Country yuki, and let Day $B_i$ be that person's birthday in the calendar of Country coder.
  • Then, the $2N$ integers $A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_N$ are all distinct.

You are given $T$ test cases; solve each of them.

Constraints

  • All input values are integers.
  • $1 \leq T \leq 2 \times 10^5$
  • $1 \leq M \leq K \leq 2 \times 10^5$
  • $1 \leq N \leq K$
  • The sum of $K$ in $1$ input file does not exceed $4 \times 10^5$.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ denotes the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$K$ $M$ $N$

Output

For each test case, output as follows.

  • If no set of birthdays of $N$ people satisfying the condition exists, output No.
  • If a set of birthdays of $N$ people satisfying the condition exists, output the birthdays of the $N$ people in the calendar of Country yuki in the following format.
Yes
$A_1$ $A_2$ $\cdots$ $A_N$

Sample

Sample 1
Input
4
5 2 2
8 1 1
14 8 7
35 6 17
Output
Yes
1 4
No
Yes
1 2 3 4 5 6 7
No

For test case $1$, $1$ year consists of $5$ days, and when it is Day $1$ in the calendar of Country yuki, it is Day $2$ in the calendar of Country coder. Therefore, for example, setting $A_1 = 1, A_2 = 4$ gives $B_1 = 2, B_2 = 5$, which satisfies the condition.

For test case $2$, $1$ year consists of $8$ days, and when it is Day $1$ in the calendar of Country yuki, it is also Day $1$ in the calendar of Country coder. In this case, the dates in the calendar of Country yuki and the calendar of Country coder are always equal, so the condition cannot be satisfied.

For test case $3$, the condition is satisfied when $A_1 = 1, A_2 = 2, A_3 = 3, A_4 = 4, A_5 = 5, A_6 = 6, A_7 = 7$, as shown below.

For test case $4$, no set of birthdays satisfying the condition exists.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。