P13288 [GCJ 2013 #1B] Osmos

Osmos 由 Hemisphere Games 开发。Hemisphere Games 未参与 Google Code Jam，也未对本题进行任何背书。

Armin 正在玩一款由 Hemisphere Games 开发的物理益智游戏 Osmos。在这款游戏中，他控制一个“小球”（mote），在空间中移动并吞噬更小的小球。 英文中的 “mote” 意为微粒。在本游戏中，就是一个可以吞噬（或被吞噬）其他物体的东西！本题中的游戏思想与 Osmos 类似，但你无需玩过原作。 当 Armin 的小球吞噬了一个比自己小的小球后，他的小球体积会增加，增长量等于被吞噬小球的体积。此时，他的小球可能能吞噬更多的小球。例如：假设 Armin 的小球初始体积为 $10$，其余小球的体积分别为 $9$、$13$ 和 $19$。开始时，Armin 的小球只能吞噬体积为 $9$ 的小球。吞噬后，他的体积变为 $19$。接着，他只能吞噬体积为 $13$ 的小球。再吞噬后，体积为 $32$。这样，Armin 的小球就可以吞噬最后一个小球了。 注意，只有当另一个小球体积严格小于 Armin 的小球时，他才能吞噬它。如果体积相等，则无法吞噬。 你负责编写用于生成小球的程序，供 Armin 吞噬。程序已经生成了一些不同体积的小球，并生成了 Armin 的小球。不幸的是，给定 Armin 的小球体积和其他小球的体积，有可能无法让 Armin 吞噬所有其他小球。 你需要解决这个问题。你可以进行两种操作，顺序和次数不限：你可以向游戏中添加一个任意正整数体积的小球，或者你可以移除已存在的任意一个小球。请问，最少需要多少次操作才能使 Armin 的小球能够吞噬所有其他小球？ 例如，假设 Armin 的小球体积为 $10$，其余小球体积为 $[9, 20, 25, 100]$。此时无法全部吞噬，但你可以添加一个体积为 $3$ 的小球，并移除体积为 $100$ 的小球，仅需 $2$ 次操作即可使问题变得可解。此时答案为 $2$。

输入的第一行为测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含 Armin 的小球体积 $A$ 和其他小球数量 $N$。第二行包含 $N$ 个整数，表示其他小球的体积。所有小球体积均为整数。

对于每个测试用例，输出一行 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是使问题可解所需的最少操作次数。

**样例说明** 虽然输入文件中给定的小球体积有限，但 Armin 的小球在吞噬其他小球后体积可能会超过输入中的限制。 **限制条件** - $1 \leq T \leq 100$ **小数据集（10 分，测试集 1 - 可见）** - $1 \leq A \leq 100$ - $1 \leq$ 所有小球体积 $\leq 100$ - $1 \leq N \leq 10$ **大数据集（12 分，测试集 2 - 隐藏）** - $1 \leq A \leq 10^6$ - $1 \leq$ 所有小球体积 $\leq 10^6$ - $1 \leq N \leq 100$ 翻译由 ChatGPT-4.1 完成。