CT36059

The Exact Tender at Crowhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the rookery of Crowhaven pays by the answer, and Gail intends to earn it. First: the full register of segments. 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: 9722 39 1 197 298 599 620 1576 1805 1926 2209 2335 2473 2557 2603 3133 3852 4170 4189 4410 4480 4562 4591 4753 5003 5017 5097 5272 5384 5609 6837 7091 7117 7396 8047 8859 8963 8990 9026 9343 9602
Output: 3

Example 2:

Input: 3026 39 1 171 179 391 1444 2304 2452 2684 2986 3194 3586 3603 4200 4216 4610 4726 5058 5266 5408 5615 6242 6482 6492 6717 6940 6954 7146 7377 7717 7767 8222 8661 8858 9102 9313 9518 9587 9641 9931
Output: 3

Example 3:

Input: 8486 39 1 374 464 523 731 1215 2137 2277 2424 2546 2741 2783 2857 3406 3721 3940 4536 4956 5472 5531 5700 5909 6156 6344 6420 6437 6599 6817 6985 7363 7870 7913 8045 8418 8799 9426 9600 9704 9710
Output: 4

Constraints:

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

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