1、小 W 买礼物(bday.cpp)
【问题描述】
小 W 今天很高兴,因为商店给 OIer 们发购物券了。小 W 得到了一些价值不菲的 SHOP 购物券,所以他决定买 N 件礼物送给小 M。
当小 W 选好了 N 件礼物,高兴地去结账时,他突然发现 SHOP 对购物券的使用有非常奸商(天下哪有免费的购物券?)的规定:一次只允许使用一张、不找零、不与现金混用。小 W 身上根本没有现金,并且他不愿意全部放弃挑选好的礼物。这就意味着,他只能通过这些购物券结账,而且这张购物券所购买的物品的总价格,必须精确的等于这张购物券的面额。
怎么样才能顺利的买回这 N 件礼物中的部分或全部送给小 M 呢?
你的任务就是帮助小 W 确定是否存在一个购买方案。小 W 会告诉你每张购物券的面额以及所有商品的价格,对每张购物券,你只需要确定能否找到一种选礼物方案,使得选出来的礼物的价格总和正好是这张购物券的面额即可。
【输入格式】
输入文件 bday.in 中有多组数据,每组数据的第一行为两个整数 N 和 M,分别表示小 W 一共挑选了 N 件礼物以及小 W 的一张购物券的面额为 M。接下来一行有 N 个用空格隔开的正整数,第 I 个数表示第 I 个礼物的价格。
输入数据以 0 0 结束。
【输出格式】
输出文件 bday.out 包含若干行,每行一个单词“YES”或者“NO”,分别代表存在一个购买方案和不存在一个购买方案。
Sample 1
Input
10 2000
1000 100 200 300 400 500 700 600 900 800
10 2290
1000 100 200 300 400 500 700 600 900 800
0 0
Output
YES
NO
Limitation
1s, 64MiB for each test case.
【数据规模】
对于 30% 的输入文件,所有的 N≤20。
对于 100% 的输入文件,所有的 N≤40,并且 M 和物品的总价值不超过 2^31-1,测试组数不超过 10 组,不少于 5 组。
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 7
- 已通过
- 1
- 通过率
- 14%
- 上传者