問題一覧 > 通常問題

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

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 192
作問者 : Shirotsume / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 8269 / 自分の提出
問題文最終更新日: 2022-08-05 19:47:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 355 (順位表) の他の問題:

Problem Statement

Determine whether there exists a subsequence, not necessarily contiguous, of $A = (1, 2, 3, \dots, N)$ whose sum is $S$, and if one exists, output $1$ such subsequence.

Constraints

  • All input values are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $\displaystyle 1 \leq S \leq \frac{N(N+1)}{2}$

Input

The input is given from Standard Input in the following format.

$N$ $S$

Output

If no such subsequence exists, output -1.

If such subsequences exist, let $A' = (A'_1, A'_2, \dots, A'_K)$ be $1$ of them. Output in the following format.

$K$
$A'_1$ $A'_2$ $\dots$ $A'_K$
If multiple subsequences satisfy the condition, any of them will be accepted.

Sample

Sample 1
Input
5 10
Output
4
1 2 3 4

$A' = (1, 2, 3, 4)$ is a subsequence of $A = (1, 2, 3, 4, 5)$ and its sum is $10$, so it is accepted.

$A' = (1, 4, 5)$ and $A' = (2, 3, 5)$ are also accepted.

Note that $A'$ must be a subsequence of $A$. For example, $A' = (1, 3, 2, 4)$ is not accepted.

Sample 2
Input
10 17
Output
4
2 3 5 7

Note that $S$ may not fit in a 32bit integer.

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