No.2845 Birthday Pattern in Two Different Calendars
タグ : / 解いたユーザー数 66
作問者 : 👑
torisasami4
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もしくは右上の雲マークをクリックしてアカウントを作成してください。