/ Vijos / 题库 /

金币

金币

时间限制:1秒  内存限制:256M


【题目描述】

  小何有 \(N\) 个金币,第 \(i\) 个金币的面额为 \(C_i\) 元。

  小何在小沐买了一个价格为 \(K\) 元的商品,由于小沐没有钱,所以小何必须选择一些金币,使得它们的面额和恰好为 \(K\) 元。

  小沐在收到小何的钱后,准备向小阳买价格为x的商品。但是小阳也没有钱,所以小沐必须在小何给他的金币中挑选一些,使得它们的面额和恰好为 \(X\)。

  现在小沐想知道,他在小阳那里能购买那些价格的商品,即小沐能付出 \(X\) 元由多少种可能性?

【输入格式】

  输入的第一行是两个正整数 \(N,\ K\),中间用一个空格分开。接下来的 \(N\) 行,每行是一个整数 \(C_i\),分别表示小何拥有的金币的币值(单位:元)。

【输出格式】

  输出的第一行为一个正整数,表示小沐可购买商品价格的个数。第二行升序输出每个合法的定价的值 \(X\)(单位:元)。

【输入输出样例1】

 Input

6 18
5 6 1 10 12 2

 Output

15
1 2 3 5 6 7 8 10 11 12 13 15 16 17 18

【样例1解释】

  若小沐收到小何的金币是5,1,10,2,则小沐用这些金币可以购买的商品的价格有:
  1 = 1
  2 = 2
  3 = 1+2
  4 = 2+2
  5 = 5
  6 = 5+1
  ……

【输入输出样例2】

 Input

10 41
2 4 9 6 12 8 4 10 6 8

 Output

33
2 4 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 35 37 39 41 

【数据限制】

  对于 \(30\%\) 的数据,\(N,K,C_i≤10\)
  对于 \(60\%\) 的数据,\(N,K,C_i≤50\)
  对于 \(100\%\) 的数据,\(N,K,C_i≤500\)

【来源】

  Mr.he

信息

ID
2284
难度
9
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
3
已通过
1
通过率
33%
被复制
2
上传者