ZeroJudge 解題筆記：e128. 新北100-1貪食蛇

作者：王一哲
日期：2025年9月17日


ZeroJudge 題目連結：e128. 新北100-1貪食蛇

解題想法

這題要找位置的數學規律，如果模擬移動的過程一定會超時。

Python 程式碼

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

import math, sys

def find_position(t):  # 輸入目前的時刻計算位置
    if t == 1: return (1, 1)  # 特例，t 等於 1，回傳 (1, 1) 並結束函式
    
    ring = math.floor(math.sqrt(t))  # 已走完的圈數
    #ring = math.isqrt(t)    # 已走完的圈數，Python 3.8 之後才有 math.isqrt
    
    t -= ring * ring  # t 扣掉已走完的圈數平方，換成位移量
    if t == 0:  # 如果 t 等於 0，剛好在這圈結束的位置
        if ring%2: return (1, ring)  # 如果是奇數圈，回傳 (1, ring) 並結束函式
        else: return (ring, 1)  # 如果是偶數圈，回傳 (ring, 1) 並結束函式
    else: ring += 1  # 其它狀況，圈數加 1
    
    x, y = 0, 0  # 座標 (x, y)
    if ring%2:  # 奇數圈
        if t > ring:  # 在底部向左移動
            x = 2*ring - t  
            y = ring
        else:  # 在右側向下移動
            x = ring
            y = t
    else:  # 偶數圈
        if t > ring:  # 在右側向上移動
            x = ring
            y = 2*ring - t
        else:  # 在底部向右移動
            x = t
            y = ring
    
    return (x, y)

for line in sys.stdin:
    t = int(line)
    if t == 0: break
    print(*find_position(t))

C++ 程式碼

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

#include <cstdio>
#include <cmath>
using namespace std;

void find_position(int);

int main () {
    int t;
    while(scanf("%d", &t) != EOF && t != 0) find_position(t);
    return 0;
}

void find_position(int t) {  // 輸入目前的時刻計算位置
    if (t == 1) {  // 特例，t 等於 1，印出 1 1 並結束函式
        printf("1 1\n");
        return;
    }
    
    int ring = int(sqrt(t));  // 已走完的圈數
    t -= ring * ring;  // t 扣掉已走完的圈數平方，換成位移量
    if (t == 0) {  // 如果 t 等於 0，剛好在這圈結束的位置
        if (ring%2) {  // 如果是奇數圈，印出 1 ring
            printf("1 %d\n", ring);
            return; 
        } else {  // 如果是偶數圈，印出 ring 1
            printf("%d 1\n", ring);
        }
        return;  // 結束函式
    } else {  // 其它狀況，圈數加 1
        ring++;
    } 
    
    if (ring%2) {  // 奇數圈
        if (t > ring) {  // 在底部向左移動
            printf("%d %d\n", 2*ring - t, ring);  
        } else {  // 在右側向下移動
            printf("%d %d\n", ring, t);
        }
    } else {  // 偶數圈
        if (t > ring) {  // 在右側向上移動
            printf("%d %d\n", ring, 2*ring - t);
        } else {  // 在底部向右移動
            printf("%d %d\n", t, ring);
        }
    }
}