Five, Six, Pick Up Sticks; Seven, Eight, Lay Them Straight

Image by denvie balidoy.

You and your friend are playing a game involving sticks of different lengths. Your opponent picks the sticks you will receive, and a number $n$. He then challenges you to lay some of the sticks down end-to-end in a straight line, so that the total length of all the sticks you’ve laid down is exactly a positive multiple of $n$. Being tired of working so hard at challenges which aren’t solvable, you’ve decided to write a program to at least determine if a challenge can be solved, before you spend a lot of time trying to solve it yourself.


Input consists of up to $100$ challenges, one per line. Each challenge begins with two integers $n$ and $m$, where $2 \le n \le 400$ and $2 \le m \le 100$ is the number of sticks. This is followed by the lengths of the $m$ sticks; each length is an integer in the range $[1,n-1]$. Input ends when $n$ and $m$ are both zero.


For each challenge, print out ‘yes’ if it is possible to solve the challenge, or ‘no’ otherwise. If it’s possible, print out the shortest length of sticks you must lay to solve the challenge.

Sample Input 1 Sample Output 1
5 3 1 2 4
5 2 2 2
5 5 4 4 4 4 4
5 5 4 4 4 4 3
0 0
yes 5
yes 20
yes 15
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Greg Hamerly
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in