No.2027 (1, 2, 3, …, N) 's Subset Sum
タグ : / 解いたユーザー数 192
作問者 :
とりゐ
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もしくは右上の雲マークをクリックしてアカウントを作成してください。