AT_abc231_e.[ABC231E] Minimal payments

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 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 \geq X$ ，你需要用最少的硬币表示 $Y$ 元和 $Y-X$ 元，求这两者所用硬币数之和的最小值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $X$ $A_1$ $\ldots$ $A_N$

输出格式

输出答案。

输入输出样例

输入#1
```
3 87
1 10 100
```
输出#1
```
5
```
输入#2
```
2 49
1 7
```
输出#2
```
7
```

输入#3

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

输出#3

说明/提示

限制条件

输入中的所有值均为整数。
$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}$

样例解释 1

用 $1$ 枚 $100$ 元硬币支付，然后用 $1$ 枚 $10$ 元硬币和 $3$ 枚 $1$ 元硬币找零，总共需要 $5$ 枚硬币。

样例解释 2

直接用 $7$ 枚 $7$ 元硬币支付是最优的。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页