This problem asks to find the minimum number of coins required for the payment. Some of you may have wondered what is the optimal strategy.

While this problem can be solved with a DP (Dynamic Programming), with appropriate observation it can be solved faster.

Solution 1. Determine the number of cheaper coins first

Actually in this problem the number of coins can be determined in the increasing order of coin values.

First, we consider how many \(1!\)-yen coin is required. Since all of \(2!,3!,\dots,10!\) is divisible by \(2! = 2\), the number of \(1!\)-yen coins used is \(2 n + r\), where \(r\) is the remainder of \(P\) by \(2!\). (Otherwise, the remainder of \(P\) and the amount of payment divided by \(2\) does not match.)

Moreover, if two or more \(1!\)-yen coins are payed, the two \(1!\)-yen coins can be substituted by a \(2!\)-yen coin so that the number of total coins is less, so it is not optimal. Therefore, we can see that the number of \(1!\)-yen coins used is \(r\).

Similar discussions can be applied for \(2!\)-yen coins to \(10!\)-yen coins, so we can now see that the number of coins can be determined in the increasing order of values of coins. Therefore, the problem can be solved by the algorithm described above. Here is an implementation.

• C++

#include <iostream>
using namespace std;

int factorial(int i) { return i ? factorial(i - 1) * i : 1; }

int main() {
  int P;
  cin >> P;

  int answer = 0;
  for (int i = 1; i <= 10; i++) {
    int divisor = factorial(i + 1);
    int residue = P % divisor;
    answer += residue / factorial(i);
    P -= residue;
  }

  cout << answer << "\n";
}

• Python

from math import factorial

P = int(input())
answer = 0

for i in range(1, 11):
  divisor = factorial(i + 1)
  residue = P % divisor
  answer += residue // factorial(i)
  P -= residue

print(answer)

Solution 1. Determine the number of expensive coins first

Alternatively, one can greedily decide the number of coins in the decreasing order of values of coins to accomplish the minimum number of coins.

We will first explain the reason in an intuitive manner. In a daily life, assume that you have many 50-yen, 100-yen, and 500-yen coins. If you are to pay a 850-yen item, you would first use a 500-yen coin, then three 100-yen coins, and finally a 50-yen coin. The algorithm is based on the intuition that “it seems optimal to use as valuable coin as possible.

In fact, such a greedy algorithm can be applied for this problem as well. We will justify by a strict proof. Let us define an “appropriate payment” as such that:

• for \(1 \leq n \leq 10\), \(n!\)-yen coin is used at most \(n\) times.

  • (Proof) We will proof by contradiction. If the condition is not satisfied, then there exists \(m\) such that \(m!\)-yen coins are used at least \((m+1)\) times. However, one can substitute these \((m+1)\) number of \(m!\)-yen coin with a \((m+1)!\)-yen coin to decrease the number of coins, which is a contradiction.

Then the following fact is derived:

• For a payment of \(n!\) yen or more, if the payment is optimal, then a coin worth \(n!\) yen or more is used.

  • (Proof) We will show the contraposition by contradiction. If only \((n-1)!\)-yen coins are used, then the maximum price affordable is \(1! \times 1 + 2! \times 2 + \dots + (n-1)! \times (n-1) = n! - 1\) yen, which is a contradiction.

By this fact, we can justify the algorithm where “if one should pay more than \(n!\) yen, then one use a \(n!\)-yen coin” in the decreasing order from \(n=10\) to \(n=1\).

When implementing, one can inspect in the decreasing order of values from \(10!\)-yen coin to \(1!\)-yen coin with a for statement. Implementation examples by C++ and Python is shown as follows.

• C++

#include <iostream>
using namespace std;

int fac[20];

int main() {
  fac[0] = 1;
  for (int i = 1; i <= 10; i++) {
    fac[i] = fac[i - 1] * i;
  }

  int P, answer = 0;
  cin >> P;

  for (int i = 10; i >= 1; i--) {
    while (P >= fac[i]) {
      answer++;
      P -= fac[i];
    }
  }

  cout << answer << endl;
}

• Python

from math import factorial

P = int(input())
answer = 0
for i in range(10, 0, -1):
  while factorial(i) <= P:
    answer += 1
    P -= factorial(i)
print(answer)