โจทย์
มีกลุ่มนักเรียน n กลุ่ม ขนาด m คนต่อกลุ่ม กลุ่มต้องขึ้นรถร่วมกัน ไม่แยก และต้องขึ้นตามลำดับ หาขนาดรถบัสที่ทำให้ทุกเที่ยวไม่มีที่ว่าง
ตัวอย่าง: gr_no = [3,4,2,2,1,4,3,5] → Output: [12, 24] (รถ 12: เที่ยว1 กลุ่ม1-5, เที่ยว2 กลุ่ม6-8; รถ 24: เที่ยวเดียว)
อัลกอริธึม
- คำนวณ Prefix Sum ของขนาดกลุ่ม
- หาตัวประกอบ (Factors) ของผลรวมทั้งหมด
- ตรวจสอบแต่ละ Factor ว่า Prefix Sum ทุกตัวหาร Factor ลงตัวหรือไม่
โค้ด Python
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])) # Output: [12, 24]
Input / Output
Input: [3, 4, 2, 2, 1, 4, 3, 5]
Output: [12, 24]
