Internet Problem Solving Contest

IPSC 2016

Problem G – Greatest number

Little Peter loves playing at the junkyard. Today he found and brought home a broken scientific calculator. He did his best repairing it, but the calculator is still not in its best shape. Here is what still works:

Peter likes big numbers. For each of the expressions in his calculator find the largest number he can produce after pressing the equals sign.

Problem description

You are given a string S that contains a valid arithmetic expression. Remove any (possibly none, but not all) characters from S so that the resulting string T is again a valid arithmetic expression and the value of T is as large as possible.

Valid expressions are defined as follows:

During the evaluation, the standard operator precedence applies:

There are no other unary or binary operations except for the ones mentioned above. In particular, there is no division and no exponentiation.

Note that the definition allows multiple unary pluses and minuses to follow each other. For example, 1*(2+3*-+-4) is a valid expression that is evaluated as follows: − + −4 is 4, 3 × 4 is 12, 2 + 12 is 14, and 1 × 14 is 14.

Also note that unnecessary leading zeros are not allowed. For example, 4-007 is not a valid expression.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Every test case contains a single line containing a valid arithmetic expression S.

In the easy subproblem G1, t = 100 and the length of each expression is between 1 and 16, inclusive.

In the hard subproblem G2, t = 1000 and the length of each expression is between 1 and 1000, inclusive.

Output specification

For each test case, output one line with a valid arithmetic expression T such that T is a subsequence of S and such that T has the maximum possible value. If there are multiple solutions, print any of them.