問題一覧 > 通常問題

No.2560 A_1 < A_2 < ... < A_N

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 269
作問者 : Kyo_s_s / テスター : deuteridayo 👑 AngrySadEight kusirakusira Magentor DeltaStruct 👑 loop0919 bluebery1001 rotti_coder ragna マベマス（mavemas_413） けんぴん aki
1 ProblemId : 10161 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-01 20:16:10

問題文

正整数 N,XN, X が与えられます。NN 個の正整数からなる数列 A1,A2,…,ANA_1, A_2, \ldots, A_N であって、次の条件:

  • 0<A1<A2<⋯<AN−1<AN0 < A_1 < A_2 < \cdots < A_{N-1} < A_N
  • ∑i=1NAi=X\displaystyle \sum_{i=1}^N A_i = X

をすべて満たすものが存在するか判定してください。 存在するなら辞書順最小のものを一つ出力してください。

TT 個のテストケースが与えられるので、それぞれについて答えを求めてください。

長さが等しい数列の辞書順とは？ ある 22 つの長さが等しい整数列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots ,A_N) と B=(B1,B2,…,BN)B=(B_1,B_2,\ldots ,B_N) が以下を満たすとき、またその時に限り辞書順で A<BA < B と定義されます。
  • ある整数 i (1≤i≤N)i \ (1 \le i \le N) が存在し、 1≤j<i1 \le j < i であるすべての整数 jj に対し Aj=BjA_j = B_j が成り立ち、かつ Ai<BiA_i < B_i が成り立つ。

制約

  • 1≤T≤1051 \leq T \leq 10^5
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤X≤10181 \leq X \leq 10^{18}
  • 11 個の入力に含まれるテストケースについて、それらの NN の総和は 2×1052 \times 10^5 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。 

TT
case1\text{case}_1
⋮\vdots
caseT\text{case}_T

各テストケース casei (1≤i≤T)\text{case}_i~(1 \leq i \leq T) は、以下の形式で与えられる。 

N XN ~ X

出力

TT 行出力せよ。ii 行目では、テストケース casei\text{case}_i において条件を満たす数列が存在するならばその数列を空白区切りで 11 行で、存在しないなら −1-1 を出力せよ。

サンプル

サンプル1
入力
3
4 10
3 5
3 9
出力
1 2 3 4
-1
1 2 6
  • テストケース 11 について、問題文の 22 つの条件を満たす数列は (1,2,3,4)(1, 2, 3, 4) のみです。よってこれを出力します。
  • テストケース 22 について、問題文の 22 つの条件を満たす数列は存在しません。 よって −1-1 を出力します。
  • テストケース 33 について、問題文の 22 つの条件を満たす数列は
    • (1,2,6)(1, 2, 6)
    • (1,3,5)(1, 3, 5)
    • (2,3,4)(2, 3, 4)
    の 33 つのみです。よって、この中で辞書順最小の (1,2,6)(1, 2, 6) を出力します。

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