### Woburn Challenge 2017-18 Round 1 - Senior Division

## Problem 4: Change

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 ≤ `K` ≤ 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 ≤ `N` ≤ 2000) distinct denominations which you definitely don't want to include. The `i`-th of these is `D _{i}` (1 ≤

`D`≤

_{i}`K`).

Your friend is convinced that his so 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 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` ≤ 20.

In test cases worth another 20/37 of the points, `K` ≤ 1000.

### Input Format

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..

`N`.

### Output Format

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}.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** Jan 26, 2018

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

kxoraxeon Feb 19, 2018 - 1:35:18 am UTC Typo