CT35965

The Exact Tender Beneath Hammerfall

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the anvil district of Hammerfall with crates of vaults, and Envoy the measurer must account for every last one. 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 <= 10000; 1 <= n <= 50; 1 <= coin <= 10^4.

Example 1:

Input: 7340 41 160 370 422 863 1029 1901 2036 2156 2927 2982 3077 3157 3966 4338 4450 4925 5398 5513 5587 5816 5849 5934 6124 6134 6172 6304 6649 6908 6948 6954 6963 7281 7680 8169 8469 8691 9008 9046 9146 9790 9905
Output: 6

Example 2:

Input: 6238 41 103 110 290 321 488 499 946 1425 1737 1880 2262 2324 2439 2572 2722 2993 3465 3647 3710 3765 3956 4049 4083 4486 4688 4775 5231 6535 6594 6595 6628 7604 7756 7813 8080 8131 8310 8366 8577 9666 9867
Output: 5

Example 3:

Input: 7110 41 73 105 107 224 535 559 817 827 1288 1367 1639 2142 2543 2678 2787 3329 3478 3503 3704 3961 3968 4400 4596 4762 4854 5485 5754 5755 6264 6631 6735 8330 8548 8806 8888 8924 9293 9349 9375 9377 9712
Output: 3

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Exact Tender Beneath Hammerfall - MEDIUM Coding Problem | CodeTikki