D - リミックスジュース
Editorial
/
Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
ひらきち君は,以下の問題を作りました.
n 個のりんごが一列に並んでおり,i 番目のりんごの大きさは a_i です. ここから連続する 1 つ以上のりんごを選ぶ選び方のうち,大きさの和が k 以下になるものはいくつありますか? 制約: 入力はすべて整数 1 \leq n \leq 1000 0 \leq a_i \leq 10^9 0 \leq k \leq 10^9
ところで,ひらきち君は悪夢を見ました. 夢の中で世界は PAKEN 連邦に支配されており,あなたは不幸にも捕まってしまいます.あなたをかばい,すべての責任を負うひらきち君に対し,PAKEN 連邦の指導者 E666666 に言い渡された釈放の条件とは...
E666666「なに?貴様は競技プログラミングの選手だと?それなら答えてみろ:
- 上述の問題の入力であって,n=N かつ答えが X となるものがあるか判定し,あるならば 1 つ示せ。
できたら許してやる.できなかったらミックスジュースだ.」
あなたはミックスジュースになりたくないので,疲れて寝てしまったひらきち君の代わりに上の質問に答えることにしました.
制約
- N は 1 以上 1000 以下の整数
- X は 0 以上 \frac{N(N+1)}{2} 以下の整数
部分点
この問題はいくつかの小課題に分けられ,その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます.
提出したソースコードの得点は,正解した小課題の点数の合計となります.
- (20 点) N \leq 20 を満たす.
- (6 点) X=1 を満たす.
- (15 点) X=\frac{S(S-1)}{2} を満たす整数 S が存在する.
- (59 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられます.
N X
出力
条件にあてはまる入力が存在しなければ -1
と出力してください.
存在するならば,一例を次のように出力してください.
k a_1 a_2 \dots a_N
入力例 1
6 14
出力例 1
15 8 6 9 1 2 0