20111126

ACM 10161 Ant on a Chessboard

數值排列找規則。
若該數為x的平方數,那
一定是(1, x)或(x, 1),
看x是奇數或偶數。
若該數比平方數大,會有三種情況:
(1) 該數 - 平方數 == x + 1:
那就是在斜角(x + 1, x + 1)
(2) 該數 - 平方數 < x + 1:
(該數 - 平方數, n + 1)或(n + 1, 該數 - 平方數)
看x是奇數或偶數。
(3) 該數 - 平方數 > x + 1:
其中一個為n + 1,
另一個為n + 1 - [該數 - 平方數 - (n + 1)]
n + 1的意思是斜角。
算出與斜角的差值,再用此值與斜角相減。
(即從斜角的座標往前推)
化簡後為
2n + 2 - (該數 - 平方數)

/* ACM 10161 Ant on a Chessboard
 * mythnc
 * 2011/11/26 16:49:42   
 * run time: 0.004
 */
#include <stdio.h>
#include <math.h>

void output(int);

int main(void)
{
    int x;

    while (scanf("%d", &x) && x != 0)
        output(x);

    return 0;
}

/* output: output answer */
void output(int x)
{
    int n, value;

    if (x == 1) {
        printf("1 1\n");
        return;
    }

    n = sqrt(x);
    /* if x is a square number */
    if (n * n == x) {
        if (n % 2 == 1)
            printf("%d %d\n", 1, n);
        else
            printf("%d %d\n", n, 1);
        return;
    }
    /* if x bigger than a square number n */
    value = x - n * n;
    if (value == n + 1)
        printf("%d %d\n", n + 1, n + 1);
    else if (value < n + 1)
        if (n % 2 == 1)
            printf("%d %d\n", value, n + 1);
        else
            printf("%d %d\n", n + 1, value);
    else
        if (n % 2 == 1)
            printf("%d %d\n", n + 1, 2 * n - value + 2);
        else
            printf("%d %d\n", 2 * n - value + 2, n + 1);
}

沒有留言: