🔗 UVA-10161 Ant on a Chessboard

tags: `數學(Math)`

範例程式碼已於 UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

p10161

一隻螞蟻在一個可以視為無窮大的棋盤上行走，每秒鐘移動一格。給定時間 $N$ ，要求計算螞蟻在棋盤上的位置。

LuckyCat 的中文翻譯

約束條件

$1 \leq N \leq 2 \cdot 10^9$

思路

注意到約束中 $N$ 的大小，顯然使用模擬整個行走過程的方法是不可行的，需要利用數學公式來直接計算螞蟻在給定時間 $N$ 所在的位置。

我們可以將路徑分層，第 $1$ 層為 $[1]$ ，第 $2$ 層為 $[2, 3, 4]$ ，第 $3$ 層為 $[5, 6, 7, 8, 9]$ ，以此類推。可以發現，前 $m$ 層共有 $m^2$ 個格子，可以根據所在的層數 $m$ 和是該層從大到小數的第 $no$ 個格子來計算螞蟻的位置。

具體步驟如下：

首先計算所在的層數，即 $m = \lceil \sqrt{N} \rceil$ 。
確定是該層的第幾個格子，即 $no = m \times m - N + 1$ $n o = m \times m - N + 1$ 。 (由大到小數)
- 若 $m$ 為奇數，則從左上至右下
- 若 $m$ 為偶數，則從右下至左上
計算格子座標：根據 $no$ $n o$ 的值和 $m$ $m$ 的奇偶性確定 $(x, y)$ $(x, y)$ 座標：
- 如果 $no < m$ $n o < m$ ，根據 $m$ $m$ 的奇偶性分配 $x$ $x$ 和 $y$ $y$ 。
  - 若 $m$ 為奇數，則 $(x, y) = (no, m)$ 。
  - 若 $m$ 為偶數，則 $(x, y) = (m, no)$ 。
- 如果 $no > m$ $n o > m$ ，根據 $m$ $m$ 的奇偶性分配 $x$ $x$ 和 $y$ $y$ 。
  - 若 $m$ 為奇數，則 $(x, y) = (m, m - (no - m)) = (m, 2m - no)$ 。
  - 若 $m$ 為偶數，則 $(x, y) = (m - (no - m), m) = (2m - no, m)$ 。
- 如果 $no = m$ $n o = m$ ，則 $x$ $x$ 和 $y$ $y$ 均為 $m$ $m$ ，即 $(x, y) = (m, m)$ $(x, y) = (m, m)$ 。
  - 可以分配到上面兩種情況中的任意一種，不影響結果。

複雜度分析

時間複雜度： $O(1)$
空間複雜度： $O(1)$

from math import ceil, sqrt

while True:
    n = int(input())
    if n == 0:
        break
    m = ceil(sqrt(n))
    no = m * m - n + 1 # 在第 m 層，且是這層的第 no 個 (由大到小)
    if no < m:
        (x, y) = (no, m) if m & 1 else (m, no)
    elif no > m:
        (x, y)= (m, m - (no-m)) if m & 1 else (m - (no-m), m)
    else: # no == m
        x, y = m, m
    print(x, y)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    LL n, m, no, x, y;
    while (cin >> n) {
        if (n == 0) break;
        m = sqrt(n);
        if (m * m < n) m += 1;
        no = m * m - n + 1;
        if (no < m) {
            x = (m & 1) ? no : m;
            y = (m & 1) ? m : no;
        } else if (no > m) {
            x = (m & 1) ? m : m - (no - m);
            y = (m & 1) ? m - (no - m) : m;
        } else {
            x = m; y = m;
        }
        cout << x << ' ' << y << endl;
    }
    return 0;
}