[Solution] Optimal Path solution codeforces

Optimal Path solution codeforces – You are given a table 𝑎a of size 𝑛×𝑚n×m. We will consider the table rows numbered from top to bottom from 11 to 𝑛n, and the columns numbered from left to right from 11 to 𝑚m. We will denote a cell that is in the 𝑖i-th row and in the 𝑗j-th column as (𝑖,𝑗)(i,j). In the cell (𝑖,𝑗)(i,j) there is written a number (𝑖1)𝑚+𝑗(i−1)⋅m+j, that is 𝑎𝑖𝑗=(𝑖1)𝑚+𝑗aij=(i−1)⋅m+j.

Table of Contents

[Solution] Optimal Path solution codeforces

A turtle initially stands in the cell (1,1)(1,1) and it wants to come to the cell (𝑛,𝑚)(n,m). From the cell (𝑖,𝑗)(i,j) it can in one step go to one of the cells (𝑖+1,𝑗)(i+1,j) or (𝑖,𝑗+1)(i,j+1), if it exists. A path is a sequence of cells in which for every two adjacent in the sequence cells the following satisfies: the turtle can reach from the first cell to the second cell in one step. A cost of a path is the sum of numbers that are written in the cells of the path.

Optimal Path solution codeforces
For example, with 𝑛=2n=2 and 𝑚=3m=3 the table will look as shown above. The turtle can take the following path: (1,1)(1,2)(1,3)(2,3)(1,1)→(1,2)→(1,3)→(2,3). The cost of such way is equal to 𝑎11+𝑎12+𝑎13+𝑎23=12a11+a12+a13+a23=12. On the other hand, the paths (1,1)(1,2)(2,2)(2,1)(1,1)→(1,2)→(2,2)→(2,1) and (1,1)(1,3)(1,1)→(1,3) are incorrect, because in the first path the turtle can’t make a step (2,2)(2,1)(2,2)→(2,1), and in the second path it can’t make a step (1,1)(1,3)(1,1)→(1,3).

You are asked to tell the turtle a minimal possible cost of a path from the cell (1,1)(1,1) to the cell (𝑛,𝑚)(n,m). Please note that the cells (1,1)(1,1) and (𝑛,𝑚)(n,m) are a part of the way.

[Solution] Optimal Path solution codeforces

The first line contains a single integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases. The description of test cases follows.

A single line of each test case contains two integers 𝑛n and 𝑚m (1𝑛,𝑚1041≤n,m≤104) — the number of rows and columns of the table 𝑎a respectively.

Output

For each test case output a single integer — a minimal possible cost of a path from the cell (1,1)(1,1) to the cell (𝑛,𝑚)(n,m).

Example

input

Copy
7
1 1
2 3
3 2
7 1
1 10
5 5
10000 10000

output

Copy
1
12
13
28
55
85
500099995000

[Solution] Optimal Path solution codeforces

In the first test case the only possible path consists of a single cell (1,1)(1,1).

The path with the minimal cost in the second test case is shown in the statement.

In the fourth and the fifth test cases there is only one path from (1,1)(1,1) to (𝑛,𝑚)(n,m). Both paths visit every cell in the table.

 

For Solution

Click Here

Leave a Comment