CT35268

The vaults at Marigold Row

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the saffron fields of Marigold Row, someone must recover the missing manifest. This year the task falls to Yara, armed only with the vaults 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: 8386 16 397 863 967 1212 1384 2349 3428 3963 5812 6859 7145 7213 7231 8274 8990 9085
Output: 8

Example 2:

Input: 8100 16 1 556 1407 2155 2442 2483 3131 4245 4303 4405 4669 7141 7453 7858 8350 9625
Output: 4

Example 3:

Input: 3116 16 970 2688 2827 3264 3367 4059 4224 4320 4592 5779 7228 7374 7524 8399 9157 9565
Output: -1

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The vaults at Marigold Row - MEDIUM Coding Problem | CodeTikki