पायथन में अधिकतम औसत पास अनुपात ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास कक्षाओं की एक सूची है जहां classes[i] [pass_i, total_i] दर्शाता है जो क्रमशः 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/b - (a+1)/(b+1), a, b) जैसे टुपल्स की सूची
h को हीपिफाई करें
जब तक extra शून्येतर है, करें
- (v, a, b) := h का शीर्ष, और इसे 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