WC '17 Contest 1 S4 - Change

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Woburn Challenge 2017-18 Round 1 - Senior Division

Your friend is just getting into competitive programming, and is trying to solve the classic "change" problem. You'll give him a target value K (1 \le K \le 10^9) and some distinct coin denominations (each of which is between 1 and K, inclusive), and he'll try to determine whether or not a total of K can be produced using a set of (possibly duplicate) coins having only those denominations. The algorithm he's come up with to do so is greedy - starting from an empty set of coins, it repeatedly adds on the largest possible coin which won't cause the total to exceed K, until it either reaches a total of K, or is unable to add on any more coins and gives up.

You're not sure what coin denominations you'd like to give him, but there are N (0 \le N \le 2\,000) distinct denominations which you definitely don't want to include. The i^{th} of these is D_i (1 \le D_i \le K).

Your friend is convinced that his algorithm is so good that he'll be able to attain a total of K no matter what denominations he's given! This is quite the bold claim. You'd like to prove him wrong by choosing a (possibly empty) set of denominations such that his algorithm will fail to reach a total of K using them. Note that it doesn't matter whether or not a more correct algorithm would succeed, as long as your friend's greedy algorithm fails to achieve a total of K.

Clearly, one option would be to simply give your friend 0 denominations to use. However, that's too easy - you'd like to prove as convincingly as possible that their algorithm is sub-par. As such, you'd like to determine the maximum number of distinct denominations which you can give your friend, such that their algorithm will still fail to reach a total of K using them.

Subtasks

In test cases worth 6/37 of the points, K \le 20.
In test cases worth another 20/37 of the points, K \le 1\,000.

Input Specification

The first line of input consists of two space-separated integers, K and N.
N lines follow, the i^{th} of which consists of a single integer, D_i, for i = 1 \dots N.

Output Specification

Output a single integer, the maximum number of distinct denominations which you can give your friend.

Sample Input 1

7 4
3 7 6 1

Sample Output 1

2

Sample Input 2

4 1
3

Sample Output 2

0

Sample Explanation 2

In the first case, one possibility is to give your friend the set of denominations \{2, 4\}. His algorithm would use a 4 coin followed by a 2 coin, and then give up.

In the second case, you must resort to giving your friend no denominations, as his algorithm would achieve a total of 4 if given any non-empty subset of the denominations \{1, 2, 4\}.


Comments

There are no comments at the moment.