問題一覧 > 通常問題

No.2027 (1, 2, 3, …, N) 's Subset Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 141
作問者 : ShirotsumeShirotsume / テスター : とりゐとりゐ 👑 ygussanyygussany
2 ProblemId : 8269 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-05 19:47:02

問題文

$A = (1, 2, 3, \dots, N)$ の連続とは限らない部分列であって、総和が $S$ となるものが存在するか判定し、存在するなら $1$ つ出力してください。

制約

  • 入力は全て整数
  • $1 \leq N \leq 2 \times 10^5$
  • $\displaystyle 1 \leq S \leq \frac{N(N+1)}{2}$

入力

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

$N$ $S$

出力

答えとなる部分列が存在しないならば、-1 と出力せよ。

答えとなる部分列が存在するならば、そのうちの $1$ つを $A' = (A'_1, A'_2, \dots, A'_K)$ とする。以下の形式で出力せよ。

$K$
$A'_1$ $A'_2$ $\dots$ $A'_K$
複数通りの部分列が答えとなる場合、どれを出力しても正解となる。

サンプル

サンプル1
入力
5 10
出力
4
1 2 3 4

$A' = (1, 2, 3, 4)$ は、$A = (1, 2, 3, 4, 5)$ の部分列であって、総和が $10$ となるので、正解となります。

$A' = (1, 4, 5)$ や $A' = (2, 3, 5)$ も正解となります。

$A'$ は $A$ の部分列であることに注意してください。例えば、 $A' = (1, 3, 2, 4)$ などは不正解となります。

サンプル2
入力
10 17
出力
4
2 3 5 7

$S$ は 32bit整数に収まらない可能性があるので注意してください。

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