Problem 1387 - USTC Online Judge

Rank

Problem 1387

吸铁石

Time Limit: 3000ms
Memory Limit: 65536kb

Description

阿泰小时候很喜欢玩吸铁石，他在3岁的时候就发现了吸铁石的吸力不一样大。N年前的6.1儿童节，他妈妈送给他很多吸铁石。他陷入了深深的沉思：
他的吸铁石只能吸起吸力小于这块的吸铁石，而且当他的吸铁石吸了一个吸力更小的吸铁石的时候，他的吸铁石的吸力就变成这两块吸铁石吸力的和。举个例子：阿泰一开始手里有一块吸力是10的吸铁石，桌子上有吸力为：9， 13， 19的吸铁石。一开始，阿泰只能吸起吸力为9的吸铁石，这样他的吸铁石吸力变成19。然后，他可以吸起13的吸铁石（但是吸不起吸力为19的吸铁石）变成32。最后，他就可以吸起吸力为19的吸铁石了。
你的任务就是通过最少的步骤：造出吸铁石或者拿走吸铁石让阿泰能把桌子上已有的吸铁石全吸起来。
具体做法：
你可以加一块任意吸力大小的吸铁石到桌子上或者你可以从桌子上拿走一块任意大小吸力的吸铁石。
举个例子：假设阿泰现在手上吸铁石的吸力大小是10，桌子上有9，20，25，100吸力的吸铁石。阿泰现在没法全把他们吸上来。但是第一步：增加一块吸力为3的吸铁石第二步：拿走那块吸力为100的吸铁石，仅需这2步就可以帮助阿泰吸起所有吸铁石。所以答案是2。

Input

第一行T，表示输入数据的组数。
每一组数据第一行是一个整数A表示阿泰手里吸铁石吸力的大小，另一个整数N是桌子上吸铁石的个数。第二行是N个吸铁石的吸力。吸力都是整数。
1 <= T <= 100
1 <= A <= 10^6
1 <= 桌子上吸铁石的吸力 <= 10^6 （阿泰手里的吸铁石吸力可能超过10^6）
1 <= N <= 100

Output

对于每组测试数据，输出一行："Case #x: y"。x表示第几组测试数据，y表示最少的能让阿泰把吸铁石全吸起来的步骤。

Sample Input

4
2 2
2 1
2 4
2 1 1 6
10 4
25 20 9 100
1 4
1 1 1 1

Sample Output

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 4

[Submit|Status|Discuss|Add to bookmark]