実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
以下の条件を全て満たす整数集合 S を一つ構築してください。なお、この問題の制約下で条件を満たす S が少なくとも一つ存在することが証明できます。
- S の要素数は N
- S の要素は -10^7 以上 10^7 以下の相異なる整数
- \displaystyle \sum _{s \in S} s = M
- S の任意の相異なる要素 x,y,z (x < y < z) について y-x\neq z-y
制約
- 1 \leq N \leq 10^4
- |M| \leq N\times 10^6
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
S の要素を s_1,s_2,\ldots,s_N とする。条件を満たす S を 1 つ以下の形式で出力せよ。
s_1 s_2 \ldots s_N
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 9
出力例 1
1 2 6
2-1 \neq 6-2 であり、 1+2+6=9 なのでこの出力は条件を満たします。他にも様々な答えが考えられます。
入力例 2
5 -15
出力例 2
-15 -5 0 2 3
M が負のこともあります。
Score : 700 points
Problem Statement
Construct a set S of integers satisfying all of the conditions below. It can be proved that at least one such set S exists under the Constraints of this problem.
- S has exactly N elements.
- The element of S are distinct integers between -10^7 and 10^7 (inclusive).
- \displaystyle \sum _{s \in S} s = M.
- y-x\neq z-y for every triple x,y,z (x < y < z) of distinct elements in S.
Constraints
- 1 \leq N \leq 10^4
- |M| \leq N\times 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Let s_1,s_2,\ldots,s_N be the elements of S. Print a set S that satisfies the conditions in the following format:
s_1 s_2 \ldots s_N
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 9
Sample Output 1
1 2 6
We have 2-1 \neq 6-2 and 1+2+6=9, so this output satisfies the conditions. Many other solutions exist.
Sample Input 2
5 -15
Sample Output 2
-15 -5 0 2 3
M may be negative.