日期: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))