ZCMU 1595:TomCat要吃饭

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 108 Solved: 49

Description

TomCat 是一次单身Cat，但是他有着很多的基友，每次吃饭都会QQ他的某一只基友，然而，他的基友Jerry 总是很墨迹。等待是无聊的，这时TomCat在学校的地上乱走，这时他发现地上有方块铺成的，他按照下图的规律走，现在无聊的TomCat想知道，他如果走了n步，他应该在什么位置，位置用坐标（x,y）表示。

image image.gif

​

Input

每次输入一个数n，n=0是输入结束（n<=2*10^9）

Output

输出坐标(x,y)

Sample Input

8 20 25 0

Sample Output

2 3 5 4 1 5

HINT

题解：

找规律后分类讨论。

|1 |
| 2 3 4 |
| 5 6 7 8 9 |
| 10 11 12 13 14 15 16 |
| 17 18 19 20 21 22 23 24 25 |
| 26 27 28 29 30 31 32 33 34 35 36 |
| ...... |

1、先找坐标类似（1，1），（2，2），（3，3）的数字对应的是：1，3，7。数字取平方根再加1就是它的坐标。

| 坐标 | 对应数字 | 对应数字取平方根取整 |
| （1，1） | 1 |
|
| （2，2） | 3 | 1 |
| （3，3） | 7 | 2 |
| （4，4） | 13 | 3 |
| .... | ... | ... |

2、拿输入8举例，距离8的两个平方数，一个是4，另一个是9.很明显8距离9更近，这样能判断出8横纵坐标中的一个了，但是如何判断是横坐标还是纵坐标？再这里我举例了几个数字以及列出坐标来帮助自己判断。

| 8 （2，2） | 15（4，2） |
| 24（2，5） | 35（6，2） |

8和24的纵坐标都是取平方根的整数部分之后加1，横坐标都是平方根取整数部分平方-自身。

那么15跟35刚好是横纵坐标倒过来，如何区别？8和24的平平方根取整数是偶数，而15跟35是奇数。

3、拿输入20举例，距离20的两个平方数，一个是16，一个是25。很明显20距离16更近。

| 6 （3，2） | 11 （2，4） |
| 20 （5，4） | 27 （2，6） |

6和20的横坐标都是取平方根的整数部分之后加1，纵坐标是自身-平方根取整数部分。

11跟27横纵坐标与6和20是倒过来的。

4、还有一种是讨论本身就是平方数的情况，也是根据平方根取整后的奇偶性来判断。

代码：

#include<stdio.h>
#include<math.h>
int main()
{
    int n;
    double l,r;
    double y;
    int x;
    int a,b;
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        y=sqrt(n);
        x=(int)sqrt(n);          //平凡根取整数部分
        l=x*x;                   //左边的平方数
        r=(x+1)*(x+1);           //右边的平方数
        l=n-l;                   //数字本身跟左边平方数差多少
        r=r-n;                   //数字本身跟右边平方数差多少
        if(x*x==n)               //讨论数字本身是平方数的情况
        {
            if(x%2==0)
            {
                a=x;
                b=1;
                //printf("6\n");
            }
            else
            {
                a=1;
                b=x;
                //printf("7\n");
            }
        }
        else
        {
            if(l<r&&x%2==0)              //距离左边平方数更近且其平凡根为偶数
            {
                a=x+1;
                b=n-x*x;
                //printf("1\n");
            }
            else if(l<r&&x%2!=0)
            {
                a=n-x*x;
                b=x+1;
                if(a==0)
                {
                    a=1;
                    b=x;
                }
                //printf("2\n");
            }
            else if(l>r&&x%2==0)
            {
                a=(x+1)*(x+1)-n+1;
                b=x+1;
                //printf("3\n");
            }
            else if(l>r&&x%2!=0)
            {
                a=x+1;
                b=(x+1)*(x+1)-n+1;
                //printf("4\n");
            }
            else if(l==r)
            {
                a=x+1;
                b=x+1;
                //printf("5\n");
            }
        }

        printf("%d %d\n",a,b);
    }
    return 0;
}