বাসের আকার নির্ধারণ করা যাতে সব গ্রুপ একসাথে যেতে পারে

nটি স্টুডেন্ট গ্রুপ আছে, প্রতিটি গ্রুপে mজন ছাত্র। গ্রুপগুলো ভাঙা ছাড়া বাসে চাড়তে চায়। এক গ্রুপ চাড়বে না যদি তাদের আগের গ্রুপ চাড়েনি বা গন্তব্যে পৌঁছেনি। গ্রুপ সংখ্যা এবং প্রতিটি গ্রুপের আকার দেওয়া থাকলে, বাসের কত আকার হলে সব গ্রুপ যাবে এবং প্রতিবার বাস ফুল হয়ে যাবে সেটা বের করতে হবে।

ইনপুট: gr_no = [3, 4, 2, 2, 1, 4, 3, 5] → আউটপুট: [12, 24]।

• বাস আকার ১২: প্রথম ট্রিপে গ্রুপ ১-৫, দ্বিতীয় ট্রিপে বাকি
• বাস আকার ২৪: এক ট্রিপে সব গ্রুপ

সমাধানের ধাপসমূহ

• ফ্যাক্টর বের করার ফাংশন (factor_ret): n-এর সব ফ্যাক্টর পেয়ার (i, n//i) কালেক্ট করুন

• প্রিফিক্স সম (total) অ্যারে বানান

• sum(gr_no)-এর প্রতিটি ফ্যাক্টর size-এর জন্য:

  • total-এ size-এর গুণফল (size, 2×size, 3×size...) আছে কিনা চেক করুন
  • যদি সব মিলে যায়: size বৈধ বাস আকার

উদাহরণ (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]))

ইনপুট

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

আউটপুট

[12, 24]