CT35453

The Exact Tender of the Pearl runs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the lily shoals of Padmore, Ravi the clerk keeps careful count of the runs. balance the workshop's books, every figure matters. 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: 2334 25 1 468 866 985 1186 1264 2207 2451 3024 3461 3686 4323 4920 5074 5151 6060 6758 7119 7306 7441 8539 8556 8819 9179 9422
Output: 18

Example 2:

Input: 1985 25 1 1081 1290 1389 1651 1740 2565 3008 3097 4123 4280 4800 5629 5669 5943 6070 6074 6118 6173 6728 6937 6973 7209 7434 9738
Output: 246

Example 3:

Input: 3099 25 1 832 962 1148 1209 1458 1595 2602 2948 3092 3425 3442 3639 3651 3949 5080 5524 6348 6718 6924 7297 7331 9298 9559 9646
Output: 8

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Exact Tender of the Pearl runs - MEDIUM Coding Problem | CodeTikki