支付账单的最少纸币数

Question

假设纸币的面额跟随无穷远的超膨胀序列：$1, $2, $5, $10, $20, $50, $100, $200, $500, $1000, $2000, $5000, \cdots 。至少需要多少张纸币才能支付一张n账单？

考虑到艾丽斯需要支付$992 给鲍勃。爱丽丝可以用7张钞票$500, $200, $200, $50, $20, $20, $2 来付账，但那需要大量的钞票。我们可以看到一个更好的解决方案是:艾丽斯支付2张纸币( $1000, $2 )，鲍勃给她换了$10 。所以，我们这里只需要三张钞票。

形式定义

钞票遵循无限序列b_i：b_n=10\cdot b_{n-3} 和大写字母b_1=1, b_2=2, b_3=5

当艾丽斯向鲍勃支付$x 时，爱丽丝用面额b_i支付a_i 钞票。a_i \in \mathbb{Z} 和\sum a_ib_i=x

a_i 可能是负的，这意味着鲍勃给爱丽丝这些纸币的变化。

您将计算：f\left(x\right)=\min_{\sum a_ib_i=x} \sum\left|a_i\right|

输入/输出

输入一个非负数，表示要支付的金额。输出所需的最少纸币数目。

规则

• 这是密码-高尔夫：以字节为单位的最短代码赢。
• 您的程序至少应该能够处理输入0 \le n < 100{,}000 。在理论上，您的算法应该适用于任意大的数字。
• 由于这个问题只针对整数s，所以浮点错误是不允许的。

测试案例

Input -> Output
    0 -> 0
    1 -> 1
    2 -> 1
    3 -> 2
    4 -> 2
    5 -> 1
    6 -> 2
    7 -> 2
    8 -> 2
    9 -> 2
   10 -> 1
   11 -> 2
   12 -> 2
   13 -> 3
   14 -> 3
   15 -> 2
   16 -> 3
   17 -> 3
   18 -> 2
   19 -> 2
   20 -> 1
   40 -> 2
   41 -> 3
   42 -> 3
   43 -> 3
   44 -> 3
   45 -> 2
   46 -> 3
   47 -> 3
   48 -> 2
   49 -> 2
   50 -> 1
   90 -> 2
   91 -> 3
   92 -> 3
   93 -> 3
   94 -> 3
   95 -> 2
   96 -> 3
   97 -> 3
   98 -> 2
   99 -> 2
  100 -> 1
  980 -> 2
  981 -> 3
  982 -> 3
  983 -> 4
  984 -> 4
  985 -> 3
  986 -> 4
  987 -> 4
  988 -> 3
  989 -> 3
  990 -> 2
  991 -> 3
  992 -> 3
  993 -> 3
  994 -> 3
  995 -> 2
  996 -> 3
  997 -> 3
  998 -> 2
  999 -> 2
 1000 -> 1
 1341 -> 6
 2531 -> 5
 3301 -> 5
 4624 -> 6
 5207 -> 4
 6389 -> 6
 6628 -> 7
 6933 -> 6
 7625 -> 6
 8899 -> 4
13307 -> 7
23790 -> 5
33160 -> 7
33325 -> 8
40799 -> 5
55641 -> 7
66472 -> 8
77825 -> 6
89869 -> 6
98023 -> 5

Answer 1

R，98字节

f=function(a,b=a%%10,c=a%/%10,e=c(0,1,1,2,2,1,2,2:4))`if`(a<2,a,min(e[b+1]+f(c),rev(e)[b]+f(c+1)))

在网上试试！

Answer 2

视网膜，102个字节

^
;在网上试试！链接包括测试用例。解释：^
;创建一个具有以下值的工作区：( a)如果Alice尚未向Bob支付足够的金额，所使用的注释数量；( b) Alice仍然需要支付Bob的金额；( c)如果Alice支付过高并需要Bob还她，则使用的票据数量；( d) Bob仍然需要向Alice偿还的金额，减去1。{`
)`重复，直到全额付清为止。%0`\d
*将每个未清金额的下一个数字转换为一元。([_;]*)(.*)¶([_;]*)
$1,$3_,$2¶$3,$1_,根据上次是否支付过高的Bob，计算Alice可以使用或多付Bob的两种方法。如果她上次工资过低，她可以支付当前的数字来保持低薪，或者多付一个，而如果她上次多付，鲍勃可以偿还补助款，让爱丽丝多付，或者再多付一次让她少付。+`;_(____|_|)
_;计算支付每个潜在数字所需的额外注释数。%O`_*;
,.*,删除更多的注释。\G_将支付(现在精确)所需的票据数转换为十进制。¶_;
T`d`Rd`.+$
{%0`\d
*
([_;]*)(.*)¶([_;]*)
$1,$3_,$2¶$3,$1_,
+`;_(____|_|)
_;
%O`_*;
)`,.*,

\G_C4链接包括测试用例。解释：A5创建一个具有以下值的工作区：( a)如果Alice尚未向Bob支付足够的金额，所使用的注释数量；( b) Alice仍然需要支付Bob的金额；( c)如果Alice支付过高并需要Bob还她，则使用的票据数量；( d) Bob仍然需要向Alice偿还的金额，减去1。A6重复，直到全额付清为止。A7将每个未清金额的下一个数字转换为一元。A8根据上次是否支付过高的Bob，计算Alice可以使用或多付Bob的两种方法。如果她上次工资过低，她可以支付当前的数字来保持低薪，或者多付一个，而如果她上次多付，鲍勃可以偿还补助款，让爱丽丝多付，或者再多付一次让她少付。A9计算支付每个潜在数字所需的额外注释数。A10删除更多的注释。A11将支付(现在精确)所需的票据数转换为十进制。¶_;
T`d`Rd`.+$

创建一个具有以下值的工作区：( a)如果Alice尚未向Bob支付足够的金额，所使用的注释数量；( b) Alice仍然需要支付Bob的金额；( c)如果Alice支付过高并需要Bob还她，则使用的票据数量；( d) Bob仍然需要向Alice偿还的金额，减去1。

A6

重复，直到全额付清为止。

A7

将每个未清金额的下一个数字转换为一元。

A8

根据上次是否支付过高的Bob，计算Alice可以使用或多付Bob的两种方法。如果她上次工资过低，她可以支付当前的数字来保持低薪，或者多付一个，而如果她上次多付，鲍勃可以偿还补助款，让爱丽丝多付，或者再多付一次让她少付。

A9

计算支付每个潜在数字所需的额外注释数。

A10

删除更多的注释。

A11

将支付(现在精确)所需的票据数转换为十进制。

¶_; T`d`Rd`.+$ {%0`\d * ([_;]*)(.*)¶([_;]*) $1,$3_,$2¶$3,$1_, +`;_(____|_|) _; %O`_*; )`,.*, \G_

C4链接包括测试用例。解释：

A5

创建一个具有以下值的工作区：( a)如果Alice尚未向Bob支付足够的金额，所使用的注释数量；( b) Alice仍然需要支付Bob的金额；( c)如果Alice支付过高并需要Bob还她，则使用的票据数量；( d) Bob仍然需要向Alice偿还的金额，减去1。

A6

重复，直到全额付清为止。

A7

将每个未清金额的下一个数字转换为一元。

A8

根据上次是否支付过高的Bob，计算Alice可以使用或多付Bob的两种方法。如果她上次工资过低，她可以支付当前的数字来保持低薪，或者多付一个，而如果她上次多付，鲍勃可以偿还补助款，让爱丽丝多付，或者再多付一次让她少付。

A9

计算支付每个潜在数字所需的额外注释数。

A10

删除更多的注释。

A11

将支付(现在精确)所需的票据数转换为十进制。

Answer 3

JavaScript (Node.js)，80字节

n=>g=(i=n)=>Math.min(f(i)+f(i+n),i?g(i-1):n);f=n=>n&&(n%10)**29%3571%4+f(n/10|0)

在网上试试！

我知道目前有更好的答案，但这是最后一个问题的答案直接导致的