2015
05-23

# Numbers Game

The objective of the numbers game is to use the basic arithmetic operations (+, -, * and /) and a number of given integers (4 to 7 integers) to get as close as possible to a given target integer. Each of the operations can be used multiple times, but each of the integers can be used at-most once. A player wins if he/she manages to calculate the closest possible value to the target integer. For example, the closest possible value to a target of 20 using the integers {2,3,5} can be achieved by the expression (2+5) * 3. Your task is to write a program to calculate the answer for each game. Note that “/” stands for integer division (examples are: 5/4 equals 1, 8/9 equals 0.)

The input consists of many games. The description for each game is given on two lines. The first line contains two integers T and N, separated by a single space, that represent the target integer and the number of given integers. -700,000 <= T <= 700,000 and 4 <= N <= 7. The second line contains N integers separated by single spaces. All integers have values between -1,000,000 and 1,000,000 inclusive. Two zeros on a line by themselves, separated by a single space, terminate the input.

The input consists of many games. The description for each game is given on two lines. The first line contains two integers T and N, separated by a single space, that represent the target integer and the number of given integers. -700,000 <= T <= 700,000 and 4 <= N <= 7. The second line contains N integers separated by single spaces. All integers have values between -1,000,000 and 1,000,000 inclusive. Two zeros on a line by themselves, separated by a single space, terminate the input.

30 5
1 2 3 4 5
10000 5
11 2 3 7 5
0 0

30
2310