Inserting Operators (2)

Interview

Time limit2sMemory limit512 MB

Summary

Insert one of +, -, x, / between each adjacent pair from a limited supply, evaluating left to right with C++14 integer division, and report the largest and smallest results.

Level: Medium6 of 10
Topics: Backtracking, Brute force, Implementation, Recursion
Solved: No attempts yet

Problem

You are given a sequence of $N$ numbers $A_1, A_2, \dots, A_N$ and a supply of operators to insert between adjacent numbers. The operators are addition (+), subtraction (-), multiplication (×) and division (÷) only, and the supply may hold more than $N-1$ of them. Exactly one operator goes between every pair of adjacent numbers, and you do not have to use every operator in the supply.

Putting one operator between each pair of numbers builds one expression. The order of the numbers stays as given.

If the sequence is 1, 2, 3, 4, 5, 6 and the supply is 3 additions, 2 subtractions, 1 multiplication and 1 division, there are 250 possible expressions. Six of them are:

$1+2+3-4 \times 5 \div 6$
$1 \div 2+3+4-5 \times 6$
$1+2 \div 3 \times 4-5+6$
$1 \div 2 \times 3-4+5+6$
$1+2+3+4-5-6$
$1+2+3-4-5 \times 6$

An expression is evaluated from left to right, ignoring operator precedence. Division is integer division that keeps the quotient only, and a negative number divided by a positive number follows the C++14 rule: make the dividend positive, take the quotient, then flip the sign of that quotient back to negative. The six expressions above evaluate like this:

$1+2+3-4 \times 5 \div 6 = 1$
$1 \div 2+3+4-5 \times 6 = 12$
$1+2 \div 3 \times 4-5+6 = 5$
$1 \div 2 \times 3-4+5+6 = 7$
$1+2+3+4-5-6 = -1$
$1+2+3-4-5 \times 6 = -18$

Given the numbers and the supply of operators, write a program that finds the largest and the smallest result over all expressions you can build.

Input

The first line contains the count of numbers $N$ . ( $2 \le N \le 11$ )

The second line contains $A_1, A_2, \dots, A_N$ . ( $1 \le A_i \le 100$ )

The third line contains four integers: the number of additions (+), subtractions (-), multiplications (×) and divisions (÷), in that order. Their sum is at least $N-1$ and at most $4N$ .

Output

Print the largest result on the first line and the smallest result on the second line.

Only inputs where every expression evaluates to a value between -1000000000 and 1000000000 are given. Each intermediate value produced while evaluating from left to right also stays between -1000000000 and 1000000000.

Hint

When the sequence is 1, 2, 3, 4, 5, 6 and the supply is 3 additions, 2 subtractions, 1 multiplication and 1 division, the largest and the smallest results come from these two expressions.

Largest: $1 \div 2+3+4+5 \times 6$
Smallest: $1+2 \div 3-4-5 \times 6$

Examples3

Example 1
Input
```
2
5 6
1 1 1 1
```
Expected output
```
30
-1
```
Example 2
Input
```
3
3 4 5
2 1 2 1
```
Expected output
```
60
-5
```
Example 3
Input
```
6
1 2 3 4 5 6
3 2 1 1
```
Expected output
```
72
-48
```