P9412 「NnOI R1-T1」购物

小 R 是一个喜欢购物的女孩子，她生活在欧艾国中。 欧艾国共有 $n$ 种面值的硬币，它们的面值分别为 $1=a_1 < a_2 < a_3 < \cdots < a_n$，且满足 $a_{i+1}$ 是 $a_i$ 的倍数。欧艾国只有硬币一种付款方式。 欧艾国的商店不支持找零，她在购物时必须支付与价格完全相等的硬币。对于同样的价格，可以有不同的支付方式。例如，如果欧艾国硬币的面值为 $1$ 元和 $5$ 元，那么支付 $7$ 元有两种方式：支付 $7$ 枚 $1$ 元硬币，或者支付 $1$ 枚 $5$ 元硬币和 $2$ 枚 $1$ 元硬币。 由于硬币的质量大致相同，她不希望携带的硬币太重，因此每次购物都会携带符合要求的尽量少的硬币。她发现了一个神奇的现象：有的时候多买 $1$ 元的商品可以使她少带很多硬币。 你能求出最小的 $m$，使得买 $m$ 元的商品需要的硬币数比买 $m-1$ 元的商品需要的硬币数更少吗？

无

无

### 样例解释 对于样例 $1$，购买 $1\sim 5$ 元的商品分别需要 $1\sim 5$ 枚 $1$ 元硬币，购买 $6$ 元的商品只需要 $1$ 枚 $6$ 元硬币。 对于样例 $2$，购买 $1$ 元或 $2$ 元的商品都需要 $1$ 枚硬币，并不满足需要的硬币数更少的要求。 ### 数据范围 对于 $100\%$ 的数据，$1\le n\le 10$，$1=a_1 < a_2 < a_3 < \cdots < a_n\le 10^9$，且满足 $a_{i+1}$ 是 $a_i$ 的倍数。 **提示：本题开启捆绑测试。** 本题共 $4$ 个子任务。 | 子任务编号 | $ n \le $ | 特殊性质 | 分数 | |:-:|:-:|:-:|:-:| | $ 1 $ | $ 2 $ | 无 | 20 | | $ 2 $ | $ 10 $ | 保证 $a_i\le 10^3$ | 20 | | $ 3 $ | $ 10 $ | 保证有解 | 30 | | $ 4 $ | $ 10 $ | 无 | 30 | ### 题目来源 | 项目 | 人员 | |:-:|:-:| | idea | rui_er | | std | rui_er | | data | rui_er | | check | Kevin0501 | | solution | rui_er |