CT35636

The vaults Exact Tender Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the temple city of Sunspire, Galen records each vaults in a worn leather ledger. The guild wants answers, not guesses. 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: 3601 38 62 649 738 1230 1701 2581 2821 2831 2960 3405 3952 4133 4323 4762 5263 5365 5725 5806 5830 5853 5892 5894 6168 6212 6619 7198 7269 7555 7576 7577 7995 8650 8751 8851 9128 9450 9674 9743
Output: 5

Example 2:

Input: 767 38 1 324 475 840 930 942 1023 1051 1434 1542 1731 1929 2243 2422 2616 2853 2985 3683 4093 4103 4375 4401 4407 4532 4633 5286 5329 5420 6262 6673 6790 6865 6917 8052 9093 9703 9845 9873
Output: 121

Example 3:

Input: 2296 38 406 772 776 886 1110 1192 1242 1273 1519 1546 1567 1752 4128 4222 4247 4274 4656 5071 5204 5891 6258 6287 6480 6844 7233 7285 7472 7811 8051 8589 8686 9080 9304 9397 9409 9560 9965 9976
Output: -1

Constraints:

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

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