মনে করুন classes নামক একটি লিস্ট আছে যেখানে classes[i] হলো [pass_i, total_i] যা i-তম ক্লাসে পাস করা ছাত্র সংখ্যা এবং সেটি মোট ছাত্র সংখ্যা বোঝায়। আমাদের আরও একটি মান extra আছে। এটি অতিরিক্ত মেধাবী ছাত্র সংখ্যা যারা যেকোনো ক্লাসে অ্যাসাইন করলে পাস করবেই। আমাদের প্রতিটি অতিরিক্ত ছাত্রকে একটি ক্লাসে এভাবে অ্যাসাইন করতে হবে যাতে সব ক্লাসের গড় পাস অনুপাত সর্বোচ্চ হয়। একটি ক্লাসের পাস রেশিও হলো পাস করা ছাত্র / মোট ছাত্র। এবং গড় পাস রেশিও হলো সব ক্লাসের পাস রেশিওর যোগফল / ক্লাস সংখ্যা। অতিরিক্ত ছাত্র অ্যাসাইন করার পর সর্বোচ্চ সম্ভাব্য গড় পাস রেশিও বের করতে হবে।
যেমন, ইনপুট classes = [[2,3],[4,6],[3,3]], extra = 3 হলে, আউটপুট হবে 0.83809, কারণ প্রথম ক্লাসে দুটি এবং দ্বিতীয় ক্লাসে একটি অতিরিক্ত ছাত্র যোগ করলে রেশিও সর্বোচ্চ হয়, এখন গড় হলো (4/5 + 5/7 + 3/3)/3 = 0.83809।
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:
h := (a/b - (a+1)/(b+1), a, b) টাপলের একটি লিস্ট classes-এ থাকা প্রতিটি (a, b) জোড়ার জন্য
h-কে হিপিফাই করুন
যখন extra নন-জিরো, तब
(v, a, b) := h-এর টপ পপ করুন
(a, b) := (a + 1, b + 1)
(-(a + 1)/(b + 1) + a / b, a, b) হিপে পুশ করুন
extra := extra - 1
h-এ থাকা সকল টাপলের গড় রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:
import heapq def solve(classes, extra): h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes] heapq.heapify(h) while extra: v, a, b = heapq.heappop(h) a, b = a + 1, b + 1 heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b)) extra -= 1 return sum(a / b for v, a, b in h) / len(h) classes = [[2,3],[4,6],[3,3]] extra = 3 print(solve(classes, extra))
ইনপুট
[[2,3],[4,6],[3,3]], 3
আউটপুট
0
