# Ant on a Chessboard

Ant on a Chessboard

One day, an ant named Alice came upon an M x M chessboard. She wanted to explore all the cells of the board. So she began to walk along the board by peeling off a corner of the board.

Alice started at square (1, 1). First, she went up for a step, then a step to the right, and a step downward. After that, she went a step to the right, then two steps upward, and then two grids to the left. In each round, she added one new row and one new column to the corner she had explored.

For example, her first 25 steps went like this, where the numbers in each square denote on which step she visited it.

 25 24 23 22 21 10 11 12 13 20 9 8 7 14 19 2 3 6 15 18 1 4 5 16 17

Her 8th step put her on square (2, 3), while her 20th step put her on square (5, 4). Your task is to decide where she was at a given time, assuming the chessboard is large enough to accept all movements.

The input file will contain several lines, each with an integer N denoting the step number where 1<=N<=2x 109. The file will terminate with a line that contains the number 0.

For each input situation, print a line with two numbers (x,y) denoting the column and the row number, respectively. There must be a single space between them.

``````8
20
25
0

``````

``````2 3
5 4
1 5

``````

``````#include<stdio.h>
#include<math.h>
int main()
{
int n,s,x,y,k,m;
while(scanf("%d",&m)!=EOF)
{
if(!m)
break;
else
{
k=(int)sqrt(m);
n=m-k*k;
s=k+1;
if(m==1||m==9||m==25)
{
x=1;y=k;
}
else
if(m==4||m==16)
{
x=k;y=1;
}
else
if(m>=2&&m<=3||m>=10&&m<=15)
{
if(n<=s)
{
y=s;
x=n;
}
else
{
y=2*s-n;
x=s;
}
}
else
if(m>=5&&m<=8||m>=17&&m<=24)
{
if(n>s)
{
x=2*s-n;
y=s;
}
else
{
x=s;
y=n;
}
}
printf("%d %d\n",x,y);
}
}
return 0;
}
``````

``````#include<stdio.h>
#include<math.h>
int main()
{
int n,s,x,y,k,m;
while(scanf("%d",&m)!=EOF)
{
if(!m)
break;
else
{
k=(int)sqrt(m);
n=m-k*k;
s=k+1;
if(m==1||m==9||m==25)
{
x=1;y=k;
}
else
if(m==4||m==16)
{
x=k;y=1;
}
else
if(m>=2&&m<=3||m>=10&&m<=15)
{
if(n<=s)
{
y=s;
x=n;
}
else
{
y=2*s-n;
x=s;
}
}
else
if(m>=5&&m<=8||m>=17&&m<=24)
{
if(n>s)
{
x=2*s-n;
y=s;
}
else
{
x=s;
y=n;
}
}
printf("%d %d\n",x,y);
}
}
return 0;
}
``````