No.2845 Birthday Pattern in Two Different Calendars
タグ : / 解いたユーザー数 63
作問者 : 👑 AngrySadEight / テスター : 遭難者 torisasami4
問題文
yuki 国と coder 国の $2$ つの国があります.この $2$ つの国では,どちらも $1$ 年が $K$ 日間であり,日付を単に $1$ 年の中の何日目かを表す整数 $n$ を用いて「$n$ 日」と表す暦を採用しています(日付を表すのに,「月」は用いません).
ただし,yuki 国の暦と coder 国の暦では,$1$ 年の始まりのタイミングが異なります.
具体的には,yuki 国の暦で $1$ 日のとき,coder 国の暦では $M$ 日です.より一般には,yuki 国の暦で $k$ 日のとき,coder 国の暦では $((k + M - 2) \bmod{K}) + 1$ 日となります.
例えば,$K = 7, M = 4$ のときは,以下の図のようになります.
さて,次の条件を満たす $N$ 人の誕生日の組は存在するか判定し,存在する場合は,その $N$ 人の yuki 国の暦における誕生日の組としてありうる例を $1$ 組出力してください.
- $i(1 \leq i \leq N)$ 番目の人の yuki 国の暦における誕生日を $A_i$ 日,coder 国の暦における誕生日を $B_i$ 日とする.
- このとき,$2N$ 個の整数 $A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_N$ がすべて異なる.
$T$ 個のテストケースが与えられるので,それぞれについて答えてください.
制約
- 入力はすべて整数である.
- $1 \leq T \leq 2 \times 10^5$
- $1 \leq M \leq K \leq 2 \times 10^5$
- $1 \leq N \leq K$
- $1$ つの入力ファイルに対する $K$ の総和は $4 \times 10^5$ を超えない.
入力
入力は以下の形式で標準入力から与えられる.ここで,$\mathrm{case}_i$ は $i$ 番目のテストケースを表す.
$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$
各テストケースは以下の形式で与えられる.
$K$ $M$ $N$
出力
各テストケースごとに,以下のように出力せよ.
- 条件を満たす $N$ 人の誕生日の組が存在しない場合,
No
と出力する. - 条件を満たす $N$ 人の誕生日の組が存在する場合,以下の形式で,$N$ 人の yuki 国の暦における誕生日を出力する.
Yes $A_1$ $A_2$ $\cdots$ $A_N$
サンプル
サンプル1
入力
4 5 2 2 8 1 1 14 8 7 35 6 17
出力
Yes 1 4 No Yes 1 2 3 4 5 6 7 No
$1$ 個目のテストケースについて,$1$ 年は $5$ 日からなり,yuki 国の暦で $1$ 日のとき coder 国の暦では $2$ 日です.したがって,例えば $A_1 = 1, A_2 = 4$ とすれば,$B_1 = 2, B_2 = 5$ となり,条件を満たします.
$2$ 個目のテストケースについて,$1$ 年は $8$ 日からなり,yuki 国の暦で $1$ 日のとき coder 国の暦でも $1$ 日です.この場合,yuki 国での暦と coder 国での暦が必ず等しくなってしまい,条件を満たしません.
$3$ 個目のテストケースについて,$A_1 = 1, A_2 = 2, A_3 = 3, A_4 = 4, A_5 = 5, A_6 = 6, A_7 = 7$ のときに,以下のように条件を満たします.
$4$ 個目のテストケースについて,条件を満たす誕生日の組は存在しません.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。