Chương trình Python tìm kích thước xe buýt chứa tất cả nhóm bạn

Giả sử có n nhóm sinh viên chờ xe buýt về nhà. Mỗi nhóm có m sinh viên. Nhóm chỉ lên xe nếu tất cả thành viên đều có chỗ. Nhóm không lên nếu nhóm trước chưa lên hoặc đã đến đích. Cho số nhóm và số người mỗi nhóm, tìm kích thước xe buýt sao cho xe chở hết tất cả nhóm, và mỗi chuyến xe xuất phát không có chỗ trống.

Ví dụ: gr_no = [3, 4, 2, 2, 1, 4, 3, 5], kết quả [12, 24].

• Xe 12 chỗ: chuyến 1 chở nhóm 1-5, chuyến 2 chở nhóm còn lại
• Xe 24 chỗ: chở hết tất cả một chuyến

Giải thuật

1. Hàm factor_ret(n): tìm tất cả ước số của n
2. Tính mảng prefix sum total của gr_no
3. Với mỗi size trong các ước của sum(gr_no):
   • Lọc temp_list = các prefix sum chia hết cho size
   • Kiểm tra temp_list có tạo thành dãy size, 2*size, 3*size... không
   • Nếu có: size là kích thước xe hợp lệ
4. Trả về danh sách kích thước hợp lệ

Ví dụ

from functools import reduce

def solve(gr_no):
    total = [gr_no[0]]
    for i in range(1, len(gr_no)):
        total.append(total[i - 1] + gr_no[i])
    
    b_sizes = []
    for size in factor_ret(sum(gr_no)):
        temp_list = list(filter(lambda x: x % size == 0, total))
        index = 1
        indicator = True
        for point in temp_list:
            if point != size * index:
                indicator = False
                break
            index += 1
        if indicator:
            b_sizes.append(size)
    return b_sizes

def factor_ret(n):
    return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

print(solve([3, 4, 2, 2, 1, 4, 3, 5]))

Input

[3, 4, 2, 2, 1, 4, 3, 5]

Output

[12, 24]