Chương trình kiểm tra k trạm giám sát đủ theo dõi các điểm trong Python

Mô tả bài toán

Cảm biến giám sát bán kính r (bình phương j = r^2). Các điểm cần giám sát là các điểm nguyên trên đường tròn. Có k trạm thấp năng lượng, mỗi trạm giám sát một điểm. Kiểm tra k trạm có đủ giám sát tất cả điểm trên đường tròn không.

Ví dụ

j = 4 (bán kính 2), k = 3 -> False (có 4 điểm: (0,2),(0,-2),(2,0),(-2,0), cần 4 trạm).

Giải thuật

1. Tính số điểm nguyên trên đường tròn bán kính sqrt(j): duyệt i từ 0 đến sqrt(j), nếu j - i^2 là số chính phương thì đếm.
2. Tổng điểm = count * 4 (đối xứng 4 góc phần tư).
3. Nếu k >= tổng điểm -> True, ngược lại False.

Triển khai Python

square_set = set([z ** 2 for z in range(44722)])

def solve(j, k):
    i = 0
    res = 0
    while i < (j ** 0.5):
        if j - i ** 2 in square_set:
            res += 1
        i += 1
    res *= 4
    if k >= res:
        return True
    else:
        return False

print(solve(4, 3))

Đầu vào

4, 3

Đầu ra

False