問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 260
作問者 : Kyo_s_sKyo_s_s / テスター : deuteridayodeuteridayo 👑 AngrySadEightAngrySadEight kusirakusirakusirakusira MagentorMagentor DeltaStructDeltaStruct loop0919loop0919 bluebery1001bluebery1001 rotti_coderrotti_coder ragnaragna マベマス（mavemas_413）マベマス（mavemas_413） けんぴんけんぴん akiaki
1 ProblemId : 10161 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-01 20:16:10

問題文

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

  • $0 < A_1 < A_2 < \cdots < A_{N-1} < A_N$
  • $\displaystyle \sum_{i=1}^N A_i = X$

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

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

長さが等しい数列の辞書順とは？ ある $2$ つの長さが等しい整数列 $A=(A_1,A_2,\ldots ,A_N)$ と $B=(B_1,B_2,\ldots ,B_N)$ が以下を満たすとき、またその時に限り辞書順で $A < B$ と定義されます。
  • ある整数 $i \ (1 \le i \le N)$ が存在し、 $1 \le j < i$ であるすべての整数 $j$ に対し $A_j = B_j$ が成り立ち、かつ $A_i < B_i$ が成り立つ。

制約

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

入力

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

$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$

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

$N ~ X$

出力

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

サンプル

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

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