問題一覧 > 通常問題

No.2845 Birthday Pattern in Two Different Calendars

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 63
作問者 : 👑 AngrySadEightAngrySadEight / テスター : 遭難者遭難者 torisasami4torisasami4
0 ProblemId : 11019 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-17 00:52:32

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。