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.
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.
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).
input
7 1 1 2 3 3 2 7 1 1 10 5 5 10000 10000
output
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.