Coin Change

Points: 7

Time limit: 1.0s

Memory limit: 16M

Author:

Problem type

Given a value of $x$ ~x~ cents, and an infinite supply of coins of $n$ ~n~ denominations, followed by their denominations, find the least amount of coins required to make change for $x$ ~x~.

Input Specification

Line $1$ ~1~: $x$ ~x~, an integer between $1$ ~1~ and $10\,000$ ~10\,000~.
Line $2$ ~2~: $n$ ~n~, the number of different denominations.
Line $3 \dots 3+n$ ~3 \dots 3+n~: the denominations of the coins.

Output Specification

An integer, on a single line - the least coins required to make change for $x$ ~x~.

Sample Input

Sample Output

Comments

-1

Viv_CCGS commented on Dec. 3, 2023, 3:18 a.m.

When I submit in PyPy3, I get IR (failed initialising), but the same code runs in Python 3, though I do get a TLE. What is happening?

0

volcano commented on Dec. 3, 2023, 10:07 p.m. ← edited →

PyPy is faster than CPython, but uses more memory. Since the memory limit is 16MB, PyPy3 is not suitable (or necessary) for this problem.

Your TLE solution is recursive, and is slower than your iterative AC solution.

0

Viv_CCGS commented on Dec. 4, 2023, 11:28 a.m.

Thank you!

9

John commented on March 24, 2022, 5:46 p.m.

My algorithm was wrong and yet I got 100% AC...?

8

Nils_Emmenegger commented on June 17, 2021, 11:31 p.m. ← edited →

The maximum value of $n$ ~n~ is $86$ ~86~.

5

OneYearOld commented on Dec. 11, 2020, 6:19 p.m.

According to the problem author, it is always possible to make change for x.