Chef and Gift
All submissions for this problem are available.
Chef likes cooking. But more than that, he likes to give gifts. And now he wants to give his girlfriend an unforgettable gift. But unfortunately he forgot the password to the safe where the money he saved for the gift is kept.
But he knows how to hack the safe. To do this, you need to correctly answer questions asked by the embedded computer. The computer is very strange, and asks special questions, sometimes it can ask about 10000 question (really weird). Because of this, Chef wants you to write a program that will help him to crack the safe.
The questions are different, but there is only one type of question. Several numbers are given and between them one of three characters: *, +, - can be inserted. Note that in this case there is no priority for the operators, that is, if + is the before multiplication, you must first execute the operation of addition, and then multiplication (1 - 2 * 3 must be interpreted as (1 - 2) * 3 = -3 and not -5). The computer asks the minimum possible value of any valid expression.
The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains a positive integer N. The second line contains N space separated integers A1, A2, ..., AN denoting the expression without the operators.
For each test case, output a single line containing the minimal value of given expression.
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 10
- -9 ≤ Ai ≤ 9
Input: 2 3 1 2 3 1 9 Output: -4 9
Example case 1: 1-2-3 = -4
Subtask 1 (15 points): 1 ≤ T ≤ 10
Subtask 2 (10 points): 1 ≤ N ≤ 3
Subtask 3 (20 points): 1 ≤ Ai ≤ 5.
Subtask 4 (35 points): 1 ≤ T ≤ 104
Subtask 5 (20 points): Look at constraints.
|Tags||dynamic-programming, easy, furko, ltime04|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.