問題一覧 > 通常問題

No.2845 Birthday Pattern in Two Different Calendars

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

問題文

yuki 国と coder 国の 22 つの国があります.この 22 つの国では,どちらも 11 年が KK 日間であり,日付を単に 11 年の中の何日目かを表す整数 nn を用いて「nn 日」と表す暦を採用しています(日付を表すのに,「月」は用いません).

ただし,yuki 国の暦と coder 国の暦では,11 年の始まりのタイミングが異なります.

具体的には,yuki 国の暦で 11 日のとき,coder 国の暦では MM 日です.より一般には,yuki 国の暦で kk 日のとき,coder 国の暦では ((k+M2)modK)+1((k + M - 2) \bmod{K}) + 1 日となります.

例えば,K=7,M=4K = 7, M = 4 のときは,以下の図のようになります.

さて,次の条件を満たす NN 人の誕生日の組は存在するか判定し,存在する場合は,その NN 人の yuki 国の暦における誕生日の組としてありうる例を 11 組出力してください.

  • i(1iN)i(1 \leq i \leq N) 番目の人の yuki 国の暦における誕生日を AiA_i 日,coder 国の暦における誕生日を BiB_i 日とする.
  • このとき,2N2N 個の整数 A1,A2,,AN,B1,B2,,BNA_1, A_2, \dots, A_N, B_1, B_2, \dots, B_N がすべて異なる.

TT 個のテストケースが与えられるので,それぞれについて答えてください.

制約

  • 入力はすべて整数である.
  • 1T2×1051 \leq T \leq 2 \times 10^5
  • 1MK2×1051 \leq M \leq K \leq 2 \times 10^5
  • 1NK1 \leq N \leq K
  • 11 つの入力ファイルに対する KK の総和は 4×1054 \times 10^5 を超えない.

入力

入力は以下の形式で標準入力から与えられる.ここで,casei\mathrm{case}_iii 番目のテストケースを表す.

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
\vdots
caseT\mathrm{case}_T

各テストケースは以下の形式で与えられる.

KK MM NN

出力

各テストケースごとに,以下のように出力せよ.

  • 条件を満たす NN 人の誕生日の組が存在しない場合,No と出力する.
  • 条件を満たす NN 人の誕生日の組が存在する場合,以下の形式で,NN 人の yuki 国の暦における誕生日を出力する.
Yes
A1A_1 A2A_2 \cdots ANA_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

11 個目のテストケースについて,11 年は 55 日からなり,yuki 国の暦で 11 日のとき coder 国の暦では 22 日です.したがって,例えば A1=1,A2=4A_1 = 1, A_2 = 4 とすれば,B1=2,B2=5B_1 = 2, B_2 = 5 となり,条件を満たします.

22 個目のテストケースについて,11 年は 88 日からなり,yuki 国の暦で 11 日のとき coder 国の暦でも 11 日です.この場合,yuki 国での暦と coder 国での暦が必ず等しくなってしまい,条件を満たしません.

33 個目のテストケースについて,A1=1,A2=2,A3=3,A4=4,A5=5,A6=6,A7=7A_1 = 1, A_2 = 2, A_3 = 3, A_4 = 4, A_5 = 5, A_6 = 6, A_7 = 7 のときに,以下のように条件を満たします.

44 個目のテストケースについて,条件を満たす誕生日の組は存在しません.

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