Number Spiral

Number Spiral

Ramandeep Singh's photo
Ramandeep Singh
·

2 min read

A number spiral is an infinite grid whose upper-left square has the number 1. Here are the first five layers of the spiral:

Your task is to find out the number in row y and column x.

Input

The first input line contains an integer T: the number of tests.

After this, there are the lines, each containing integers by and xxx.

Output

For each test, print the number in row Y and column x

Constraints

  • 1 <= t <= 10^5

  • 1 <= y,x <= 10^9

Example

Input:

3
2 3
1 1
4 2

Output:

8
1
15

Solution:

To solve this problem, we need to observe that the numbers are in either increasing or decreasing order, so we can solve this problem using that solution observe the pattern in the above image ,

We can see that any cell (x,y) we are searching for lies at the border of the square formed by the k = max(x,y).

Take this example, (x,y) = (2,4)

So for every (x, y) its value is located on the border of the square created by max (x,y).

The Value is located vertically when x > y and horizontally when x <= y, the solution might be obvious to you now we need to sum up the maximum value of the inner square of the square that’s contains the solution with either x or y of the value we are searching for.

#include<bits/stdc++.h>
using namespace std;

int main(){
     int x,y;
     cin >> x >> y;
      int z= max(x,y);
    int k = z*z;
    if(k%2)
    cout << z - ((x-1) + (k-y));
    else
     cout << z - ((x-1) + (k-y)); 

}

That's all for this blog , will see you in the next one.

DSAC++