CT37901

Quin's vaults Exact Tender

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Quin inherited the archive at the cliffside roost of Stormrest along with its curious bookkeeping system for vaults. Time to make sense of it. Task: Coins of n given sizes may be used without limit. Print the minimum number of coins summing exactly to amount, or -1. Input format: First line: amount and n. Second line: n distinct coin sizes. Output format: Print the minimum coin count, or -1. Constraints: 0 <= amount <= 4000; 1 <= n <= 50; 1 <= coin <= 10^4.

Example 1:

Input: 3377 21 31 1336 2282 3075 4051 4325 4365 4405 4479 4766 5119 5694 5887 6424 6480 6671 7973 8047 8379 9048 9082
Output: -1

Example 2:

Input: 2908 21 118 752 1455 1551 1965 2211 2715 3115 4162 4389 4495 5462 5492 5697 5899 6923 7381 7616 8059 8218 8973
Output: -1

Example 3:

Input: 1821 21 1 537 579 1493 1666 2149 2163 2281 2425 2800 3542 3668 4769 5608 6224 6280 6601 6925 9032 9403 9851
Output: 87

Constraints:

0 <= amount <= 4000; 1 <= n <= 50; 1 <= coin <= 10^4.

Loading...
Test Cases:No test cases
No test cases available.
Quin's vaults Exact Tender - MEDIUM Coding Problem | CodeTikki