পাইথনে একটি সংখ্যার সর্বোচ্চ কম্পোজিট সামন্ড (composite summands) সংখ্যা

একটি সংখ্যা N (1 ≤ N ≤ 10⁹) দেওয়া আছে। N কে সর্বোচ্চ সংখ্যক কম্পোজিট (composite) সংখ্যার যোগফল হিসেবে প্রকাশ করতে হবে। কম্পোজিট সংখ্যা হলো ১ এবং নিজের বাদে অন্য বিভাজক থাকা সংখ্যা (যেমন ৪, ৬, ৮, ৯, ১০...). সম্ভব না হলে -1 ফেরত দিন।

উদাহরণ

ইনপুট: 16

আউটপুট: 4 (কারণ ১৬ = ৪ + ৪ + ৪ + ৪, মোট ৪টি সামন্ড)

সমাধানের পদ্ধতি

ছোট সংখ্যাগুলো (১৬ পর্যন্ত) এর জন্য DP (Dynamic Programming) টেবিল বানানো হয়।
বেস কম্পোজিট সংখ্যা: ৪, ৬, ৯।
বড় সংখ্যা (N ≥ ১৬) এর জন্য: যেনে-cause ৪ সবচেয়ে ছোট কম্পোজিট, তাই (N - 16) / 4 টি ৪ যোগ করলে সর্বোচ্চ সামন্ড পাওয়া যায়।
ফর্মুলা: t = (N - 16) // 4 + 1, উত্তর = t + table[N - 4*t]

পাইথন কোড


max_val = 16

def pre_calc():
    table = [-1] * max_val
    table[0] = 0
    v = [4, 6, 9]
    for i in range(1, max_val):
        for k in range(3):
            j = v[k]
            if i >= j and table[i - j] != -1:
                table[i] = max(table[i], table[i - j] + 1)
    return table

def max_summ(table, n):
    if n < max_val:
        return table[n]
    else:
        t = (n - max_val) // 4 + 1
        return t + table[n - 4 * t]

n = 16
table = pre_calc()
print(max_summ(table, n))