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

狐のジャップル正在为编程竞赛平台 K4PC 出题。今天，他想出了这样一个问题。 #### 问题描述 在超市的生鲜食品摊上，有 $ N $ 根黄瓜待售。结账时，如果你购买的黄瓜总重量不超过 $ W $，就能够获得生产者三木先生的亲笔签名。 健介非常喜爱三木先生种植的黄瓜，因此他想尽可能多地收集到这些签名。请你帮忙计算一下，有多少种购买组合可以使他获得签名。 #### 任务 有 $ N $ 个物品，每个物品的重量都是一个正整数 $ a_i $ ($ 1 \leq i \leq N $)。 求所有重量和不超过 $ W $ 的物品组合的数量。 #### 约束条件 - $ 1 \leq N \leq 1000 $。 - $ 1 \leq W \leq 1000 $。 - $ 1 \leq a_i \leq 1000 $。 #### 输入格式 输入包括一行： > $ N $ $ W $ $ a_1 $ $ a_2 $ … $ a_N $ #### 输出格式 输出一个整数，表示满足条件的购买组合数量。 #### 输入样例 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 \leq x \leq 10^{18} $。 提前保证在上述条件下，问题有解。（13:51 更新） 此外，为部分分问题数据集，要求输出 $ x \leq 1000 $。 **本翻译由 AI 自动生成**

> $ 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 $.