পাইথনে সর্বাধিক গড় পাস অনুপাত খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের ক্লাসের একটি তালিকা আছে যেখানে ক্লাস[i] প্রতিনিধিত্ব করে [pass_i, total_i] যথাক্রমে ith ক্লাসের পরীক্ষায় উত্তীর্ণ ছাত্রের সংখ্যা এবং th ক্লাসের মোট ছাত্রদের সংখ্যাকে প্রতিনিধিত্ব করে। আমরা অতিরিক্ত আরেকটি মান আছে. এটি অতিরিক্ত সংখ্যক মেধাবী ছাত্রদের নির্দেশ করে যারা তাদের নির্ধারিত যেকোন ক্লাসের পরীক্ষায় উত্তীর্ণ হওয়ার নিশ্চয়তা দেয়। আমাদের প্রত্যেকটি অতিরিক্ত শিক্ষার্থীকে একটি ক্লাসে এমনভাবে বরাদ্দ করতে হবে যাতে সমস্ত ক্লাসে পাস করা শিক্ষার্থীর গড় সংখ্যা সর্বাধিক হয়। একটি ক্লাসের পাসের অনুপাত সেই ক্লাসের ছাত্রদের সংখ্যা দ্বারা নির্ধারিত হয় যেটি ক্লাসের মোট শিক্ষার্থীর সংখ্যা দিয়ে ভাগ করে পাস করবে। এবং গড় পাসের অনুপাত হল ক্লাসের সংখ্যা দ্বারা ভাগ করা সমস্ত শ্রেণীর পাসের অনুপাতের সমষ্টি। অতিরিক্ত ছাত্র বরাদ্দ করার পর আমাদের সর্বোচ্চ সম্ভাব্য গড় পাসের অনুপাত খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট ক্লাস =[[2,3],[4,6],[3,3]], অতিরিক্ত =3 এর মত হয়, তাহলে আউটপুট হবে 0.83809, কারণ প্রথম শ্রেণীতে দুইজন অতিরিক্ত শিক্ষার্থী এবং একজন যোগ করুন। অনুপাত সর্বাধিক করতে দ্বিতীয় শ্রেণীতে অতিরিক্ত শিক্ষার্থী, তাই এখন গড় হল (4/5 + 5/7 + 3/3)/3 =0.83809৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• h :=ক্লাসে প্রতিটি জোড়ার (a, b) জন্য (a/b-(a + 1)/(b + 1), a, b) টিপলের একটি তালিকা

• heapify h

• অতিরিক্ত যখন শূন্য নয়, করুন

  • (v, a, b) :=h এর উপরে, এবং h

    থেকে মুছে দিন

  • (a, b) :=(a + 1, b + 1)

  • (-(a + 1) /(b + 1) + a / b, a, b) স্তূপে ঢোকান

  • অতিরিক্ত :=অতিরিক্ত - 1

• h

  এর সমস্ত টিপল থেকে গড় ফেরত

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

ইমপোর্ট heapqdef সমাধান(শ্রেণী, অতিরিক্ত):h =[(a / b - (a + 1) / (b + 1), a, b) a এর জন্য, b ক্লাসে] heapq.heapify(h) যখন অতিরিক্ত:v, a, b =heapq.heappop(h) a, b =a + 1, b + 1 heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a , b)) অতিরিক্ত -=1 রিটার্ন যোগফল (a / b এর জন্য v, a, b in h) / len(h) ক্লাস =[[2,3],[4,6],[3,3]]অতিরিক্ত =3প্রিন্ট(সমাধান (ক্লাস, অতিরিক্ত))

ইনপুট

আউটপুট

0