Phân Phối Kẹo Cho Mọi Người (Distribute Candies) Trong Python

Phân phối candies cái kẹo cho n người theo quy tắc:

1. Vòng 1: người 1 được 1, người 2 được 2, ..., người n được n
2. Vòng 2: người 1 được n+1, người 2 được n+2, ..., người n được 2n
3. Lặp lại cho đến khi hết kẹo. Người cuối nhận tất cả kẹo còn lại.

Ví dụ: candies=7, n=3 → [2,2,3] (1→[1,0,0], 2→[1,2,0], 3→[1,2,3], 4→[2,2,3] hết).

Thuật toán

1. Khởi tạo mảng kết quả res size n toàn 0
2. i = 0 (chỉ số kẹo hiện tại, 0-indexed)
3. Khi candies > 0:
   • give = min(candies, i + 1)
   • res[i % n] += give
   • candies -= give
   • i += 1
4. Trả về res

Ví dụ (Python)

class Solution(object):
    def distributeCandies(self, candies, num_people):
        res = [0] * num_people
        i = 0
        while candies > 0:
            give = min(candies, i + 1)
            res[i % num_people] += give
            candies -= give
            i += 1
        return res

ob1 = Solution()
print(ob1.distributeCandies(8, 3))  # [3, 2, 3]
print(ob1.distributeCandies(7, 3))  # [2, 2, 3]
print(ob1.distributeCandies(10, 3)) # [5, 2, 3]

Tối ưu toán học (O(√candies))

import math

def distributeCandies(candies, num_people):
    res = [0] * num_people
    # Tìm vòng hoàn chỉnh cuối cùng k: k(k+1)/2 ≤ candies
    k = int((math.sqrt(1 + 8*candies) - 1) / 2)
    
    # Phân phối k vòng hoàn chỉnh
    full_rounds = k // num_people
    for i in range(num_people):
        # Tổng cấp số nhân: (i+1) + (i+1+n) + ... 
        first = i + 1
        terms = full_rounds
        if terms > 0:
            last = first + (terms - 1) * num_people
            res[i] = terms * (first + last) // 2
    
    # Phân phối kẹo còn lại
    remaining = candies - k * (k + 1) // 2
    next_person = k % num_people
    next_candy = k + 1
    
    while remaining > 0:
        give = min(remaining, next_candy)
        res[next_person] += give
        remaining -= give
        next_person = (next_person + 1) % num_people
        next_candy += 1
    
    return res

Độ phức tạp

• Mô phỏng: O(√candies) thời gian, O(n) không gian
• Toán học: O(n) thời gian, O(n) không gian

Đầu vào / Đầu ra

Input:  candies = 8, num_people = 3
Output: [3, 2, 3]