首页 > 代码库 > Ant on a Chessboard UVA 10161
Ant on a Chessboard UVA 10161
说说：首先，最终蚂蚁的行走路线可以看成一直在沿着正方形的边沿走。而最大的正方形的边长是平方之后小于所给时间N的最大整数。这个最大的正方形的边长可以通过二分法获得。而且要注意的是根据边长的奇偶性，剩余路线的出发点可能在右下角，也可能在左上角。然后将剩余的要走的路再分成在到达顶点（即转折点）之前和之后，通过简单的数学计算最后就可以判断出蚂蚁最后的位置啦！
题目：
Background
One day, an ant called Alice came to an M*M chessboard. She wanted to go around all the grids. So she began to walk along the chessboard according to this way: (you
一天，一只叫做Alice的蚂蚁来到了一个M*M大的棋盘。她想走遍每个网格。所以她开始按照这种方式在棋盘上走
can assume that her speed is one grid per second)
（你可以假设她的速度为一秒钟一格棋盘）
At the first second, Alice 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
在第一秒的时候，Alice站在（1,1）。首先，她向上走一格，然后向右走一格，向下走一格。在这之后，她又向右走一格，然后向上走两格
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:
比如，她开始的25步就是这样走的：
( 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 |
9 | 8 | 7 | 14 | 19 |
2 | 3 | 6 | 15 | 18 |
1 | 4 | 5 | 16 | 17 |
5
4
3
2
1
1 2 3 4 5
At the 8th second , she was at (2,3), and at 20th second, she was at (5,4).
在第八秒的时候，她在（2,3），而在第20秒的时候，她在（5,4）
Your task is to decide where she was at a given time.
你的任务就是给出在给定时间她的位置
(you can assume that M is large enough)
你可以假设M足够大
Input
Input file will contain several lines, and each line contains a number N(1<=N<=2*10^9), which stands for the time. The file will be ended with a line that contains a
输入包含好多行，每行有一个数字N（1<=N<=2*10^9）代表时间。整个输入在碰到N为0时结束
number 0.
Output
For each input situation you should print a line with two numbers (x, y), the column and the row number, there must be only a space between them.
对于每个输入你必须输出两个数字（x,y）,即列号和行号，并且他们之间只有一个空格
Sample Input
8
20
25
0
Sample Output
2 3
5 4
1 5
源代码：
#include <stdio.h>
#include <math.h>
int main(){
int left,right,mid;
int N;
//freopen("data.txt","r",stdin);
while(scanf("%d",&N)&&N){
left=1;
right=(int)sqrt(2000000000)+1;
while(left<=right){//二分查找
mid=(left+right)/2;
if(N==mid*mid)
break;
else if(N<mid*mid)
right=mid-1;
else
left=mid+1;
}
if(N==mid*mid){
if(mid%2)//奇偶的情况略有不同
printf("%d %d\n",1,mid);
else
printf("%d %d\n",mid,1);
continue;
}
if(N<mid*mid)//统一使mid的平方小于N
mid--;
if(mid%2){
if(N<mid*mid+mid+1)//未达转角
printf("%d %d\n",N-mid*mid,mid+1);
else
printf("%d %d\n",mid+1,(mid+1)*(mid+1)-N+1);
}
else{
if(N<mid*mid+mid+1)
printf("%d %d\n",mid+1,N-mid*mid);
else
printf("%d %d\n",(mid+1)*(mid+1)-N+1,mid+1);
}
}
return 0;
}