No.2027 (1, 2, 3, …, N) 's Subset Sum
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 178
作問者 :
Shirotsume
/ テスター :
👑 
ygussany
とりゐ
タグ : / 解いたユーザー数 178
作問者 :
Shirotsume
/ テスター :
👑 ygussany
とりゐ
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。