P13404 [GCJ 2010 #3] Fence

我们计划建造一段非常长的围栏。我们已经找到了一个合适的地点，现在只需要收集材料。 在本地的五金店，我们可以无限量地购买木板，每块木板有多种不同的长度可选。为了避免浪费，我们希望这些木板的总长度恰好等于我们要建造的围栏长度。 给定围栏的长度以及可用的木板长度，请你计算，为了恰好拼出所需长度，最少需要购买多少块木板？ 注意：围栏会非常长！

输入文件的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。 每组测试数据包含两行。第一行包含用空格分隔的两个整数 $L$ 和 $N$，分别表示围栏的总长度和可购买的不同木板长度的数量。第二行包含 $N$ 个用空格分隔的整数 $B_1, B_2, \ldots, B_N$，表示所有可用的木板长度。

对于每组测试数据，输出一行，格式为 "Case #$x$: $M$"，其中 $x$ 是测试用例编号（从 1 开始），$M$ 的含义如下： - 如果可以购买一块或多块木板，使得它们的总长度恰好等于 $L$，则 $M$ 为所需木板的最小数量。 - 否则，$M$ 应为字符串 "IMPOSSIBLE"。

**样例解释** 在第一个样例中，最优策略是使用 $2$ 块长度为 $23$ 的木板，$5$ 块长度为 $51$ 的木板，以及 $99999997$ 块长度为 $100$ 的木板。当然，你也可以只用 $100000001$ 块长度为 $100$ 的木板来获得大于 $L$ 的总长度，但这是不允许的。 在第二个样例中，只能拼出偶数长度。 **数据范围** - $1 \leq T \leq 50$。 - $10^{10} \leq L \leq 10^{18}$。 - $1 \leq N \leq 100$。 **小数据集（7 分，测试点 1 - 可见）** - $1 \leq B_i \leq 100$。 **大数据集（22 分，测试点 2 - 隐藏）** - $1 \leq B_i \leq 100000$。 由 ChatGPT 4.1 翻译