Time Limit: 2 sec / Memory Limit: 256 MB
問題文
狐のジャップルさんは, 日々 K4PC (Kool code for Programming Contest) に出題する問題を考えています.
今日, 彼はこのような問題を思いつきました.
Do use Dynamic Programming
問題文
スーパーの生鮮食品コーナーには N 本の胡瓜が売られています. レジで会計をするときに, 生鮮食品コーナーで買った胡瓜の重さの合計が W 以下だと, 生産者のミカミさん直筆のサインが貰えます.
ケンスケくんはミカミさんの作る胡瓜が大好きなので, 出来るだけ多くのサインが欲しいです. ケンスケくんの為に, ミカミさんからサインを貰う方法の個数を求めて挙げて下さい.
課題
N 個の荷物があって, それぞれの荷物には正整数の重さ a_i (1 ≦ i ≦ N) が付いている.
重さの和が W 以下となるような荷物の集合の個数を求めよ.
制約
- 1 ≦ N ≦ 1000.
- 1 ≦ W ≦ 1000.
- 1 ≦ a_i ≦ 1000.
入力
N W a_1 a_2 … a_N出力
問題の解を 1 行に出力せよ.
入力例 1
4 4 1 1 2 3出力例 1
11\{\},\ \{a_1\},\ \{a_2\},\ \{a_3\},\ \{a_4\},\ \{a_1,\ a_2\},\ \{a_1,\ a_3\},\ \{a_2,\ a_3\},\ \{a_1,\ a_4\},\ \{a_2,\ a_4\},\ \{a_1,\ a_2,\ a_3\} が条件を満たす荷物の集合である.
ジャップルさんはこの問題が簡単過ぎる気がしてきたため, 次のような問題を思いつきました.
課題
問題 " Do use Dynamic Programming " (問題文を参照) の入力であって, 答えが x となるようなものを 1 つ出力せよ.
制約
すべての入力データは以下の制約を満たす.
- 1 ≦ x ≦ 10^{18}.
この制約条件のもとで,条件を満たすような答が存在することが保証されている.(13:51 追記)
また,この問題には部分点が設定されており,2 点分の入力データは追加で以下の制約を満たす.
- x ≦ 1000.
入力
x
出力
与えられた入力が, 問題 " Do use Dynamic Programming " の正しい出力となるような, 問題 " Do use Dynamic Programming " の入力を 1 つ作り出力せよ.
入力例 1
11
出力例 1
4 4 1 1 2 3
Problem: kagamiz
Tester: kyuridenamida