Chương trình kiểm tra có thể ăn kẹo yêu thích vào ngày yêu thích trong Python

Cho mảng candiesCount (số kẹo loại i) và mảng queries (mỗi query: [favoriteType, favoriteDay, dailyCap]). Quy tắc: ăn từ ngày 0; phải ăn hết loại i-1 mới được ăn loại i; mỗi ngày ăn ≥ 1 kẹo cho đến khi hết. Trả về mảng boolean cho từng query.

Ví dụ: candiesCount=[7,4,5,3,8], queries=[[0,2,2],[4,2,4],[2,13,100]] → [True, False, True].

Giải thuật (Tiền tố tổng)

1. Tính mảng tiền tố sumcandy với sumcandy[i] = tổng kẹo loại 0..i.
2. Thêm 0 vào cuối sumcandy để xử lý truy vấn loại 0.
3. Với mỗi query (typ, day, cap):
   • Sớm nhất có thể ăn loại typ là ngày sumcandy[typ-1] (sau khi ăn hết loại trước).
   • Muộn nhất là ngày sumcandy[typ] - 1 (trước khi hết loại này).
   • Kiểm tra: day+1 > sumcandy[typ] (quá muộn) HOẶC (day+1)*cap <= sumcandy[typ-1] (quá sớm/vượt cap) → False.
   • Ngược lại → True.

Ví dụ minh họa

def solve(candiesCount, queries):
    sumcandy = [candiesCount[0]]
    index = 1
    while index < len(candiesCount):
        sumcandy.append(sumcandy[index-1] + candiesCount[index])
        index += 1
    sumcandy.append(0)
    res = []
    for each in queries:
        typ, day, cap = each[0], each[1], each[2]
        if day+1 > sumcandy[typ] or (day+1)*cap <= sumcandy[typ-1]:
            res.append(False)
        else:
            res.append(True)
    return res

candiesCount = [7,4,5,3,8]
queries = [[0,2,2],[4,2,4],[2,13,100]]
print(solve(candiesCount, queries))

Đầu vào

[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]

Đầu ra

[True, False, True]