102314: [AtCoder]ABC231 E - Minimal payments
Description
Score : $500$ points
Problem Statement
There are $N$ kinds of coins used in the Kingdom of Atcoder: $A_1$-yen, $A_2$-yen, $\ldots$, $A_N$-yen coins.
Here, $1=A_1 < \ldots < A_N$ holds, and $A_{i+1}$ is a multiple of $A_i$ for every $1\leq i \leq N-1$.
When paying for a product worth $X$ yen using just these coins, what is the minimum total number of coins used in payment and returned as change?
Accurately, when $Y$ is an integer at least $X$, find the minimum sum of the number of coins needed to represent exactly $Y$ yen and the number of coins needed to represent exactly $Y-X$ yen.
Constraints
- All values in input are integers.
- $1 \leq N \leq 60$
- $1=A_1 < \ldots <A_N \leq 10^{18}$
- $A_{i+1}$ is a multiple of $A_i$ for every $1\leq i \leq N-1$.
- $1\leq X \leq 10^{18}$
Input
Input is given from Standard Input in the following format:
$N$ $X$ $A_1$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
3 87 1 10 100
Sample Output 1
5
If we pay with one $100$-yen coin and receive one $10$-yen coin and three $1$-yen coins as the change, the total number of coins will be $5$.
Sample Input 2
2 49 1 7
Sample Output 2
7
It is optimal to pay with seven $7$-yen coins.
Sample Input 3
10 123456789012345678 1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000
Sample Output 3
233
Input
题意翻译
现有 $n$ 种硬币。 每个硬币的面额为 $A_1,A_2,...,A_n$ 。 现在,你想买价值为 $x$ 元钱的物品。 求你用出的硬币个数和商家找回的硬币个数的总和的最小值是多少。Output
分数:500分
问题描述
在Atcoder王国中,有N种硬币:A1日元硬币,A2日元硬币,...,AN日元硬币。
这里,1=A1 < ... < AN成立,并且对于每一个1≤i≤N-1,Ai+1是Ai的倍数。
当使用这些硬币支付价值为X日元的商品时,支付和找零所需的硬币总数的最小值是多少?
准确地说,当Y是至少为X的整数时,找出表示Y日元所需的硬币数量和表示Y-X日元所需的硬币数量的最小和。
约束条件
- 输入中的所有值都是整数。
- 1≤N≤60
- 1=A1 < ... < AN≤1018
- 对于每一个1≤i≤N-1,Ai+1是Ai的倍数。
- 1≤X≤1018
输入
输入将以标准输入的以下格式给出:
$N$ $X$ $A_1$ $\ldots$ $A_N$
输出
打印答案。
样例输入1
3 87 1 10 100
样例输出1
5
如果我们支付一个100日元硬币并收到一个10日元硬币和三个1日元硬币作为找零,硬币的总数量将是5。
样例输入2
2 49 1 7
样例输出2
7
使用七个7日元硬币支付是最佳选择。
样例输入3
10 123456789012345678 1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000
样例输出3
233