Kiểm tra đi từ (0,0) đến (x,y) trong đúng N bước (Python)

Bài toán: Từ gốc (0,0), mỗi bước đi 1 đơn vị lên/xuống/trái/phải. Kiểm tra có thể đến (x,y) trong chính xác n bước không.

Điều kiện cần và đủ

Khoảng cách Manhattan: d = |x| + |y|.
Cần: n ≥ d (đủ bước đi) VÀ (n - d) % 2 == 0 (các bước dư phải đi đi về cặp để hủy nhau).

Triển khai Python

def solve(p, n):
    x, y = p
    d = abs(x) + abs(y)
    return n >= d and (n - d) % 2 == 0

# Test
print(solve((2, 1), 3))   # True: d=3, n=3, n-d=0 even
print(solve((2, 1), 4))   # False: d=3, n=4, n-d=1 odd
print(solve((2, 1), 5))   # True: d=3, n=5, n-d=2 even (đi thêm 1 cặp back-forth)
print(solve((0, 0), 1))   # False: d=0, n=1, n-d=1 odd
print(solve((0, 0), 2))   # True: đi ra quay về

Kết quả

True

Giải thích

• Đi tối thiểu cần |x|+|y| bước (Manhattan distance).
• Các bước dư n - d phải chẵn để có thể đi ra đi vào cặp (ví dụ: phải→trái, lên→xuống).
• Độ phức tạp: O(1) time, O(1) space.