Yashvi notices that there are exactly M*M tiles on her room’s floor forming a square. Getting bored she hops around the grids in a particular pattern. So she begins to walk along the floor according to this way: (you can assume that her speed is one grid per second)
At the first second, she was standing at (1,1). Firstly she went up for a grid, then a grid to the right, a grid downward. After that, she went a grid to the right, then two grids upward, and then two grids to the left…in a word, the path was like a snake.
For example, her first 25 seconds went like this:
(the numbers in the grids stands for the time when she went into the grids)
25 24 23 22 21
10 11 12 13 20
09 08 07 14 19
02 03 06 15 18
01 04 05 16 17
So we see that at the 2nd second she is at (2,1) and at the 24th second she is at (5,2).
Given a time N, your task is to output the grid number(row,column) where Yashvi stands at that time.
The input consists of multiple test cases.
For each test case, input consists of the value of N on a separate line.
Read till EOF.
For each value of time instant N output the corresponding position of Yashvi in (row,column) format.
N < 2000000000
No. of test cases <= 105
Large I/O - Use scanf, printf to avoid TLE.
Problem Setter: Shradha Chhaparia