ZeroJudge 解題筆記：c048. 10161 - Ant on a Chessboard

作者：王一哲
日期：2026年2月8日


ZeroJudge 題目連結：c048. 10161 - Ant on a Chessboard

解題想法

觀察位置的規律，第 1 格在左下角，第 4 格在邊長 $2 \times 2$ 正方形右下角，第 9 格在邊長 $3 \times 3$ 正方形左上角，第 16 格在邊長 $4 \times 4$ 正方形右下角，第 25 格在邊長 $5 \times 5$ 正方形左下角，第 36 格在邊長 $6 \times 6$ 正方形右下角。可以先建表，再用二分搜尋法找 n 在第幾列。也可以直接開根號，向上取整數。

Python 程式碼

使用時間約為 29 ms，記憶體約為 5.2 MB，通過測試。

import sys, bisect

maxn = 44722  # 平方為 2000057284，超出題目上限 2000000000
nums = [i*i for i in range(maxn+1)]  # i 平方的數字，開頭放 0，用二分搜尋法時比較方便
for line in sys.stdin:
    n = int(line)  # 時間 n
    if n == 0: break
    m = bisect.bisect_left(nums, n)  # n 在 nums 之中的棋盤的第 m 列
    b = nums[m] - n  # n 是 nums 第 m 列往回數 b 格
    if m%2 == 1:  # 如果 m 是奇數，先向上，再向左
        if b < m: print(b+1, m)  # 倒過來向右數
        else: print(m, m+m-b-1)  # 倒過來向下數
    else:  # 如果 m 是偶數，先向右，再向下
        if b < m: print(m, b+1)  # 倒過來向上數
        else: print(m+m-b-1, m)  # 倒過來向左數

使用時間約為 20 ms，記憶體約為 3.4 MB，通過測試。

import sys, math

for line in sys.stdin:
    n = int(line)  # 時間 n
    if n == 0: break
    m = math.ceil(math.sqrt(n))  # n 在 nums 之中的棋盤的第 m 列
    b = m*m - n  # n 是 nums 第 m 列往回數 b 格
    if m%2 == 1:  # 如果 m 是奇數，先向上，再向左
        if b < m: print(b+1, m)  # 倒過來向右數
        else: print(m, m+m-b-1)  # 倒過來向下數
    else:  # 如果 m 是偶數，先向右，再向下
        if b < m: print(m, b+1)  # 倒過來向上數
        else: print(m+m-b-1, m)  # 倒過來向左數

C++ 程式碼

使用時間約為 2 ms，記憶體約為 128 kB，通過測試。

#include <cstdio>
#include <cmath>

int main() {
    int n;  // 時間 n
    while(scanf("%d", &n) != EOF) {
        if (n == 0) break;
        int m = ceil(sqrt(n));  // n 在 nums 之中的棋盤的第 m 列
        int b = m*m - n;  // n 是 nums 第 m 列往回數 b 格
        if (m%2 == 1) {  // 如果 m 是奇數，先向上，再向左
            if (b < m) printf("%d %d\n", b+1, m);  // 倒過來向右數
            else printf("%d %d\n", m, m+m-b-1);  // 倒過來向下數
        } else {  // 如果 m 是偶數，先向右，再向下
            if (b < m) printf("%d %d\n", m, b+1);  // 倒過來向上數
            else printf("%d %d\n", m+m-b-1, m);  // 倒過來向左數
        }
    }
    return 0;
}