| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11224 | Prefix |
|
| 12481 | Frog Jumping |
|
Description
Infix notation: X + Y
- Operators are written in-between their operands. This is the usual way we write expressions. An expression such as
A * ( B + C ) / Dis usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."
Prefix notation (also known as "Polish notation"): + X Y
- Operators are written before their operands. The expressions given above are equivalent to
/ * A + B C D
Now, please write a program to convert the given expressions from prefix to infix.
Input
The first line contains a positive integer N, indicating the number of testcases in this input.
In the following N lines, each line contains a prefix expression.
In each prefix expression, there is a space between numbers and operators, and operators and operators.
Output
Output the infix expression and its answer of each given prefix expression.
Note that
- There is a space between numbers and operators, and operators and operators.
- If the answer is integer, there is no need to print decimal point. Otherwise, you should print only one digit after the decimal point.
- You have to print a '\n' at the end of each ouput.
- Add a pair of parentheses to wrap around each operator and its operands.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There’re N stones on the river. The height of the i-th stone is hi for 1≤i≤N.
Frog Pepe is on the 1-st stone at the beginning and he wants to cross this river with several jumps.
For each jump, Pepe can jump to the (i+1)-th or the (i+2)-th stone from the i-th stone.
The energy cost of jump is |hi−hj|, where j is the stone to land on.
Because Pepe is too lazy to move, can you help Pepe to find out the minimun energy cost as few jumps as possible to cross the river?
Explantation of Sample I/O:
The mininum energy is 40. There’re 3 routes having the same cost:
- Stone 1 -> 2 -> 4 -> 5 -> 6, 4 jumps
- Stone 1 -> 2 -> 4 -> 6, 3 jumps
- Stone 1 -> 3 -> 5 -> 6, 3 jumps.
Choose jumps as few as possible.
Therefore, the output is 40, 3.
Input
An integer N on the first line.
h1,h2...hN on the second line.
- 1≤N≤25
- 1≤hi≤100,000
Output
On the first line, two integers C and J, which mean the minimun energy cost and the number of jumps.
Remember ‘\n’ on the end of line.