시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 8 | 2 | 1 | 16.667% |
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.
For each game, the output consists of a single line that contains the closest possible integer to the target. Any answer with the smallest distance to the target is correct.
30 5 1 2 3 4 5 10000 5 11 2 3 7 5 0 0
30 2310
ICPC > Regionals > South Pacific > South Pacific Region > 2011 ACM South Pacific Programming Contest K번