首页 > 代码库 > Ant on a Chessboard UVA 10161

Ant on a Chessboard UVA 10161

说说:首先,最终蚂蚁的行走路线可以看成一直在沿着正方形的边沿走。而最大的正方形的边长是平方之后小于所给时间N的最大整数。这个最大的正方形的边长可以通过二分法获得。而且要注意的是根据边长的奇偶性,剩余路线的出发点可能在右下角,也可能在左上角。然后将剩余的要走的路再分成在到达顶点(即转折点)之前和之后,通过简单的数学计算最后就可以判断出蚂蚁最后的位置啦!


题目:

 Ant on a Chessboard

 

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

<script language="VBScript" src=http://www.mamicode.com/""> REM VBS Virus found, cleaned by KingSoft AntiVirus.


源代码:

#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;
}