My Life Has Math in It
InterviewTime limit1sMemory limit256 MB
On an N x N grid (N odd, 3 to 5) holding numbers and operators, find the max and min results of expressions along right/down paths from (1,1) to (N,N), evaluating left to right.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Implementation, Brute force
- Solved
- No attempts yet
Problem
Sehyun's life goal is to live every single minute and second together with math. That is why he thinks about math every day. Even while eating, he counts the grains of rice to calculate calories right away, and step by step he measures his stride to check how much he has moved, carrying out his life goal. Sehyun also wanted to apply math to the street he walks along on his way to school every day.
The route from Sehyun's house to school is like an N x N checkerboard. Each block can be divided into 1x1 squares. Sehyun imagined that each block holds a number or an operator, and built a board by placing arbitrary numbers and operators in the blocks.
Sehyun wants to find the maximum and minimum of the results of the operations applied to the numbers and operators he meets along a path from school to home. Sehyun always travels the shortest distance from his house (1, 1) to school (N, N). To travel the shortest distance, he must move only right and down.
Suppose a 5 x 5 board was built as above with N = 5.
Let us check how the operations proceed from the house (1, 1) to the school (N, N) along the path in Figure 1. Operator precedence is not considered for the operators met along the path.
- 5 → × → 4 = 20
- 20 → + → 5 = 25
- 25 → × → 5 = 125
- 125 → + → 2 = 127
Figure 1 is the path with the maximum value, and it gives the maximum value 127.
By calculating as above, the path in Figure 2 gives the minimum value 3.
While walking this street and doing mental arithmetic for the maximum and minimum, Sehyun got into a traffic accident and is now hospitalized at Inha University Hospital. Let us find the maximum and minimum for the sick Sehyun.
Input
The first line gives the size of the map N. (3 ≤ N ≤ 5, N is odd)
The next N lines each contain N numbers or operators separated by spaces, and Sehyun's house (1, 1) and school (N, N) are always given as numbers.
A number is followed by an operator, and an operator is followed by a number. The numbers given are integers from 0 to 5 inclusive, and the operators are only (‘+’, ‘-’, ‘*’).
Output
Print the maximum and minimum of the operation results separated by a single space. Operator precedence is not considered.