CT36677

The Exact Tender Beneath Tranquil Basin

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the lotus ponds of Tranquil Basin, someone must prepare the guildmaster's brief. This year the task falls to Ysolde, armed only with the runs register. 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: 4290 22 1 670 968 998 1339 1532 1714 2471 2790 3030 3412 3967 4224 4474 4847 5133 5738 7010 8082 9018 9082 9698
Output: 21

Example 2:

Input: 3789 22 1 799 878 1106 1614 2456 2470 3020 3889 5141 5190 5472 5668 6012 6078 6123 6909 7385 8621 9587 9659 9793
Output: 53

Example 3:

Input: 7544 22 25 1225 1948 2015 2301 3407 3796 4041 4338 5311 5312 5454 5696 6222 7335 8180 8274 8335 8666 8998 9424 9689
Output: 5

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 Tranquil Basin - MEDIUM Coding Problem | CodeTikki