โปรแกรมหาจำนวนขั้นต่ำไปถึงเป้าหมายด้วย Baby/Giant Steps ใน Python

ให้ Queries Q[i] = [a_i, b_i, d_i] เริ่ม (0,0) ขั้นตอนเดินได้ระยะ Euclidean อย่างน้อย a สูงสุด b หาขั้นต่ำไป (d_i, 0)

ตัวอย่าง: Q=[(2,3,1),(1,2,0),(3,4,11)] → [2,0,3]

ขั้นตอน

1. mmin=min(a,b), mmax=max(a,b)
2. d==0: 0 ขั้น
3. d==mmin หรือ mmax: 1 ขั้น
4. d < mmax: 2 ขั้น (เดินสามเหลี่ยม)
5. มิฉะนั้น: ceil(d/mmax)

ตัวอย่างโค้ด

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))  # Output: [2, 0, 3]

อินพุต

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

เอาต์พุต

[2, 0, 3]