Ant on a Chessboard

Ant on a Chessboard

时间: 1ms        内存:64M

描述:

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

提示:

参考答案(内存最优[760]):

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

参考答案(时间最优[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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注