Hints: https://atcoder.jp/contests/arc210/editorial/14585

In this editorial, when we say distribute coins, we mean distributing them to \(M\) people so that the value distributed per person is equal.

[1] Approach

We call a coin with value \(10^i\) coin \(i\).

Suppose the answer is \(10X+Y\) (\(0\leq Y\leq 9\)). A set of coins with value \(10X+Y\) includes at least \(Y\) coins of value \(1\). Therefore, if we can distribute value \(10X+Y\), we can also distribute value \(10X\), so first, we consider finding “the maximum \(X\) such that value \(10X\) can be distributed.”

In this case, coin \(0\) will always be distributed in units of \(10\), so we should:

• “Exchange” coin \(0\) into coin \(1\) as much as possible. That is, repeatedly replace \(10\) coins of coin \(0\) with \(1\) coin of coin \(1\) as much as possible.
• Distribute coins \(1, 2, \ldots, N-1\) to \(M\) people so that the value per person is maximized.

On top of this, we consider maximizing \(Y\). Coins \(1, 2, \ldots, N-1\) cannot be used for this remainder part. Therefore, we should:

• “Exchange” coin \(0\) into coin \(1\) as much as possible. That is, repeatedly replace \(10\) coins of coin \(0\) with \(1\) coin of coin \(1\) as much as possible.
• Distribute coins \(1, 2, \ldots, N-1\) to \(M\) people so that the value per person is maximized. Here, try to leave as many coins \(1\) created by “exchange” as possible.
• Convert the remaining coins \(1\) created by “exchange” back to coin \(0\).
• Distribute coin \(0\) by the maximum number of coins per person.

[2] Implementation using recursive function

Based on the above, here we explain an implementation method using a recursive function (it is also easy to achieve almost the same thing without using a recursive function).

We set up a recursive function \(f(i,k)\) as follows:

• \(f(i, k)\): Starting from a state where we have \(k\) extra coins of coin \(i\) obtained by exchange from coin \((i-1)\), distribute coins \(i, i+1, \ldots, N-1\) by the maximum value per person. Here, among these, try to leave as many coins obtained by exchange as possible.

\(f(i,k)\) can be realized by the following recursive process:

• When \(A_i+k=10a+b\) (\(0\leq b<10\)), exchange \(10a\) coins of coin \(i\) into \(a\) coins of coin \((i+1)\), and execute \(f(i+1,a)\).
• Convert the remaining coins \((i+1)\) from \(f(i+1,a)\) back to coin \(i\) by exchange.
• Distribute coin \(i\) to \(M\) people by as many coins as possible.
• In this series of processes, try to leave as many coins obtained by exchange from coin \((i-1)\) as possible. When \(c\) coins of coin \(i\) remain, we can ensure that \(\min(c,k)\) of them are coins obtained by exchange from coin \((i-1)\).

After that, just implement appropriate termination conditions properly. Also refer to the following sample solution.

• Sample solution: https://atcoder.jp/contests/arc210/submissions/70836012