#E. 希蒙的炼金术2

    传统题 1000ms 256MiB

希蒙的炼金术2

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

希蒙现在又要开始新的炼金了,现在希蒙拥有N(1<=N<=20)N(1 <= N <= 20)瓶药水,每瓶药水都有一个确定的魔力值Hi(1<=Hi<=1,000,000)H_i(1 <= H_i <= 1,000,000)。可以通过中和现有炼金药水得到一瓶新的炼金药水,新炼金药水的魔力值为其所有中和炼金药水的魔力值之和,希蒙的目标是通过中和多瓶药水,得到一瓶魔力值为至少B的药水,并且保证一定有解。 但是希蒙同时也是一个吝啬的人,在新药水魔力值达到B的同时,他不想浪费任何一丁点的魔力,但是这很难做到,因此现在需要设计一个程序,计算在选择的药水魔力值之和达到B的情况下,超出B的最少魔力。

输入格式

第1行: 2个用空格隔开的整数:NNBB

第2..N+1行: 第i+1行是1个整数:HiH_i

输出格式

第1行: 输出1个非负整数,即药水中和的魔力值最少比所需魔力值大的数量

样例

样例输入 #1

5 16
3
1
3
5
6

样例输出 #1

1

数据范围与提示

魔力值中和>=16的情况有2种

第一种 :3 + 3 + 5 + 6 = 17。

第二种 :3 + 1 + 3 + 5 + 6 = 18。

我们选最小的情况,此时浪费了1点魔力值,所以输出1

第二期冯诺依曼班结营测试

未参加
状态
已结束
规则
IOI
题目
6
开始于
2022-7-28 9:30
结束于
2022-7-28 12:00
持续时间
2.5 小时
主持人
参赛人数
49