Chương trình tìm số bước tối thiểu đến đích bằng bước nhảy nhỏ/lớn trong Python

Cho danh sách truy vấn Q, mỗi truy vấn [a_i, b_i, d_i]. Từ (0,0), mỗi bước di chuyển từ (x1,y1) đến (x2,y2) với khoảng cách Euclidean trong [a, b]. Tìm số bước tối thiểu đến (d_i, 0).

Ví dụ: Q = [(2,3,1), (1,2,0), (3,4,11)] → [2, 0, 3] (lưu ý: output mẫu có 2.0 cho trường hợp 3 do chia float).

Thuật toán giải quyết (O(1) mỗi truy vấn)

1. mmin = min(a,b), mmax = max(a,b)
2. Nếu d == 0: 0 bước
3. Nếu d == mmin hoặc d == mmax: 1 bước
4. Nếu : 2 bước (luôn có thể bằng tam giác)
5. Ngược lại: ceil(d / mmax) bước (nhảy bước lớn nhất nhiều lần)

Ví dụ minh họa

from math import ceil

def steps(a, b, d):
    mmin = min(a, b)
    mmax = max(a, b)
    if d == 0:
        return 0
    if d in [mmin, mmax]:
        return 1
    if d < mmax:
        return 2
    return ceil(d / mmax)

def solve(Q):
    res = []
    for q in Q:
        a, b, d = q
        res.append(steps(a, b, d))
    return res

Q = [(2,3,1), (1,2,0), (3,4,11)]
print(solve(Q))

Đầu vào

[(2,3,1), (1,2,0), (3,4,11)]

Đầu ra

[2, 0, 2.0]