CT35368

Rowena Counts the ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the lantern reef of Glowtide with crates of ledgers, and Rowena the dispatch writer 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: 7858 45 106 195 758 1277 1516 2299 2348 2459 2764 2780 2883 2927 3162 3350 3743 3836 4183 4368 4553 4655 4777 4778 5150 5428 5628 5960 6097 6420 6710 6861 6897 7045 7175 7184 7790 7935 8204 8548 8639 9080 9152 9274 9633 9773 9999
Output: 3

Example 2:

Input: 9960 45 120 1208 1272 1279 1470 1717 2125 2293 2512 2673 2915 3003 3109 3646 3813 4229 4750 4819 4997 5041 5393 5394 5517 5557 5713 5740 5765 6633 7114 7172 7184 7243 7463 7556 7697 7860 7920 8112 8164 8810 9201 9249 9807 9932 9983
Output: 4

Example 3:

Input: 810 45 100 118 415 1234 1678 2075 2272 2432 2478 2802 2989 3158 3487 3722 3812 3840 3990 4490 4498 4722 5046 5074 5226 5377 5948 6312 6444 6521 6555 6577 6596 6641 6924 7023 7129 7429 7906 7992 8251 8432 8709 9615 9704 9738 9837
Output: -1

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Rowena Counts the ledgers - MEDIUM Coding Problem | CodeTikki