AT_k4pc_e はじめての動的計画法(Easy Dynamic Programming)

[problemUrl]: https://atcoder.jp/contests/k4pc/tasks/k4pc_e 狐のジャップルさんは, 日々 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\} $ が条件を満たす荷物の集合である. ジャップルさんはこの問題が簡単過ぎる気がしてきたため, 次のような問題を思いつきました. #### 問題文 スーパーの生鮮食品コーナーには $ 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\} $ が条件を満たす荷物の集合である.

> $ x $

与えられた入力が, 問題 " *Do use Dynamic Programming* " の正しい出力となるような, 問題 " *Do use Dynamic Programming* " の入力を 1 つ作り出力せよ.

### 課題 問題 " *Do use Dynamic Programming* " (問題文を参照) の入力であって, 答えが $ x $ となるようなものを 1 つ出力せよ. ### 制約 すべての入力データは以下の制約を満たす． - $ 1\ ≦\ x\ ≦\ 10^{18} $. **この制約条件のもとで，条件を満たすような答が存在することが保証されている．(13:51 追記)** また，この問題には部分点が設定されており，$ 2 $ 点分の入力データは追加で以下の制約を満たす． - $ x\ ≦\ 1000 $.