Chương trình kiểm tra có thể biến danh sách 1 thành target bằng cách cập nhật bằng tổng hiện tại bằng Python

Cho danh sách target. Ban đầu X cùng độ dài toàn 1. Mỗi phép toán: chọn chỉ số i, gán X[i] = sum(X). Kiểm tra có thể biến X thành target hay không.

Ví dụ: target=[5,9,3] → True (1,1,1 → 1,1,3 → 5,1,3 → 5,9,3).

Giải thuật

• Nếu target chỉ 1 phần tử: trả về True nếu phần tử đó là 1.
• Dùng max-heap (lưu giá trị âm) chứa các phần tử target.
• Lặp: lấy phần tử lớn nhất x, tính d = sum - x.
• x2 = x % d (nếu d>1 else 1). Cập nhật sum += x2 - x.
• Nếu x == x2 dừng. Push x2 vào heap.
• Kết thúc: tất cả phần tử trong heap phải là -1 (tức 1).

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        if len(nums) == 1:
            return nums == [1]
        from heapq import heapify, heappop, heappush
        q = [-x for x in nums]
        heapify(q)
        s = sum(nums)
        ok = True
        while ok:
            x = -heappop(q)
            d = s - x
            x2 = x % d if d > 1 else 1
            s += x2 - x
            ok = x != x2
            x = x2
            heappush(q, -x)
        return all(x == -1 for x in q)

ob = Solution()
target = [5, 9, 3]
print(ob.solve(target))

Đầu vào

[5, 9, 3]

Đầu ra

True