CT37508

Topaz ledgers Exact Tender

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the cinnabar mines of Vermilion, Librarian studies rows of ledgers entries. One clean number will settle the guild's oldest argument. 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: 4630 50 66 94 105 196 211 377 397 577 637 1097 1143 1164 1355 1417 1486 1821 2050 2478 2507 2675 3092 3294 3366 3478 3513 3742 4169 4519 4814 4960 5199 5421 5940 6102 6206 6593 6736 6975 6991 7670 7712 8319 8394 8790 9175 9204 9298 9364 9817 9886
Output: 3

Example 2:

Input: 2302 50 1 2 429 518 545 892 945 1544 1548 1779 2138 2306 2325 2940 3261 3275 3317 3409 3500 3525 3552 4366 4846 4946 4953 5018 5517 5527 5785 5924 5980 6015 6378 6773 6789 6943 7026 7097 7390 8164 8196 8224 8229 8275 8311 8849 9156 9238 9647 9686
Output: 3

Example 3:

Input: 6717 50 660 883 1211 1226 1339 1408 1438 1447 1712 2549 2552 2619 2795 2808 2840 3094 3221 3538 3814 3834 3876 4053 4352 4472 4685 4753 5183 5273 5480 5729 5961 6105 6180 6486 6796 7097 7311 7418 7474 7875 7920 7994 8229 8485 8638 8945 9149 9504 9770 9940
Output: 3

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.