Minimal payments

题目描述

王国 Atcoder 使用有 $N$ 种硬币：面值为 $A_1$ 日元、$A_2$ 日元、$\ldots$、$A_N$ 日元的硬币。
这里满足 1=A_1 < \ldots < A_N，且对每个 $1\leq i \leq N-1$ 都有 $A_{i+1}$ 是 $A_i$ 的倍数。 当仅使用这些硬币支付价值为 $X$ 日元的商品时，支付和找零所使用的硬币总数最少是多少？ 更准确地说，对于任意整数且不小于 $X$ 的 $Y$，求表示恰好 $Y$ 日元所需硬币个数与表示恰好 $Y-X$ 日元所需硬币个数之和的最小值。

输入格式

从标准输入按以下格式给出输入： $N$ $X$ $A_1$ $\ldots$ $A_N$

输出格式

输出答案。

3 87
1 10 100

5

2 49
1 7

7

10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

233

提示

输入中的所有数值均为整数。 $1 \leq N \leq 60$ 1=A_1 < \ldots <A_N \leq 10^{18} 对每个 $1\leq i \leq N-1$ 都有 $A_{i+1}$ 是 $A_i$ 的倍数。 $1\leq X \leq 10^{18}$如果我们用一枚 $100$ 日元的硬币支付，并收到一枚 $10$ 日元硬币和三枚 $1$ 日元硬币作为找零，则硬币总数为 $5$。
用七枚 $7$ 日元硬币支付是最优的。

标签: AtCoder|abc231E

来源

AtCoder|abc231E