Chương trình tìm số lượng bóng tối đa trong một hộp bằng Python

Giả sử có nhà máy bóng với n bóng được đánh số từ l đến r (tính cả hai đầu) và có vô hạn hộp đánh số từ 1 đến vô cùng. Mỗi bóng được đặt vào hộp có số bằng tổng các chữ số của số bóng. (Ví dụ: bóng số 123 → hộp số 1+2+3=6). Cho hai giá trị l và r, ta phải tìm số bóng trong hộp chứa nhiều bóng nhất.

Ví dụ: l = 15, r = 25, kết quả là 2 vì hộp 6 và 7 đều chứa 2 bóng (số 15,24 vào hộp 6; số 16,25 vào hộp 7).

Giải thuật

1. dict := new map
2. For i từ l đến r:
   • total := 0
   • Với mỗi chữ số j của i: total += j
   • Nếu total chưa có trong dict: dict[total] := 0
   • dict[total]++
3. Trả về giá trị lớn nhất trong dict

Ví dụ (Python)

def solve(l, r):
    dict = {}
    for i in range(l, r + 1):
        total = 0
        for j in str(i):
            total += int(j)
        if total not in dict:
            dict[total] = 0
        dict[total] += 1
    return max(dict.values())

l = 15
r = 25
print(solve(l, r))

Input

15, 25

Output

2