মনে করুন আমাদের কাছে batchSize নামে একটি মান এবং groups নামে একটি অ্যারে আছে যেখানে groups[i] নির্দেশ করে groups[i] কাস্টমারের একটি গ্রুপ দোকানে আসবে। তাই একটি ডোনাট দোকান আছে যা দেয়া batchSize-এ ডোনাট বেক করে। কিন্তু তাদের একটি নিয়ম আছে, তারা একটি ব্যাচের সব ডোনাট সার্ভ করার আগে পরের ব্যাচের কোনো ডোনাট সার্ভ করবে না। এবং প্রতিটি কাস্টমার ঠিক একটি ডোনাট পাবে। যখন একটি গ্রুপ দোকানে ঢুকে, সেই গ্রুপের সব কাস্টমারকে সার্ভ করতে হবে পরের গ্রুপে যাওয়ার আগে। একটি গ্রুপ খুশি হবে যদি তারা সবাই তাজা ডোনাট পায়। (অর্থাৎ গ্রুপের প্রথম কাস্টমার গত গ্রুপ থেকে বাকি থাকা ডোনাট গ্রহণ করবে না)।
আমরা গ্রুপগুলো পুনর্বিন্যাস করতে পারি, এবং অবশেষে সর্বোচ্চ সম্ভাব্য খুশি গ্রুপের সংখ্যা বের করতে হবে।
সুতরাং, যদি ইনপুট হয় batchSize = 4, groups = [2,1,8,4,3], তবে আউটপুট হবে 4 কারণ আমরা এদের এভাবে সাজাতে পারি [8,4,2,3,1] যাতে প্রথম, দ্বিতীয়, তৃতীয় এবং চতুর্থ গ্রুপ খুশি। প্রথম গ্রুপের জন্য দুটি ব্যাচ, দ্বিতীয় গ্রুপের জন্য একটা ব্যাচ, তৃতীয় গ্রুপের জন্য একটা ব্যাচ সার্ভ করে চতুর্থ গ্রুপের জন্য একটা।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
l := groups-এ সব g-এর জন্য (g mod batchSize) ধারণকারী একটি তালিকা
count := l-এ এলিমেন্টের ফ্রিকোয়েন্সি ধারণকারী একটি ম্যাপ
g := 0 থেকে batchSize রেঞ্জে সব i-এর জন্য count[i] ধারণকারী একটি তালিকা
একটি ফাংশন dp() ডিফাইন করুন। এটি sm, t নেবে
যদি t-এর সর্বোচ্চ 0 সমান হয়, তবে
0 রিটার্ন করুন
ans := 0
arr := t
k = 0 থেকে batchSize-1 পর্যন্ত জন্য, করুন
যদি arr[k] == 0 হয়, তবে
পরবর্তী ইটারেশনে যান
arr[k] := arr[k] - 1
ans := ans এবং dp((sm + k) mod batchSize, arr) এর মধ্যে সর্বোচ্চ
arr[k] := arr[k] + 1
ans + (1 যদি sm == 0 অন্যথায় 0) রিটার্ন করুন
মেইন মেথড থেকে dp(0, g) রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
from collections import Counter
def solve(batchSize, groups):
l = [g % batchSize for g in groups]
count = Counter(l)
g = [count[i] for i in range(batchSize)]
def dp(sm, t):
if max(t) == 0:
return 0
ans, arr = 0, list(t)
for k in range(batchSize):
if arr[k] == 0:
continue
arr[k] -= 1
ans = max(ans, dp((sm + k) % batchSize, arr))
arr[k] += 1
return ans + (sm == 0)
return dp(0, g)
batchSize = 4
groups = [2,1,8,4,3]
print(solve(batchSize, groups))
ইনপুট
4, [2,1,8,4,3]
আউটপুট
4
