Take the Sample Input \(1\) as an example, where \(X=87\) and \(A=(1,10,100)\).

\(10\)-or-more-yen coins enable us to exchange only the price of multiple of \(10\), so for the fractional part less than \(10\) yen has to be dealt by \(1\)-yen coins. It is sufficient to consider only the following two cases: “include \(7\) number of \(1\)-yen coins in the payment” or “receive \(3\) number of \(1\)-yen coins as the change.”
The former case boils down to paying \(80\) yen with \(10\)-or-more-yen coins, and the latter to paying \(90\) yen with \(10\)-or-more-yen coins.

As described, the problem can be recursively solved bottom-up.
In the recursive process of solving the problem, only the prices of \(\left\lfloor \frac{X}{A_i}\right\rfloor A_i\) and \(\left\lceil \frac{X}{A_i}\right\rceil A_i\) yen appears, so the complexity is \(O(N)\) by memoization.

Sample code (C++)