पायथन में प्रतियोगिता में प्राप्त अंकों का पता लगाने का प्रोग्राम

मान लीजिए हम एक प्रोग्रामिंग प्रतियोगिता में हैं जहां कई समस्याएं हैं लेकिन प्रतियोगिता तब समाप्त होती है जब हम एक समस्या हल करते हैं। अब यदि हमारे पास points और chances नामक समान लंबाई की दो संख्याओं की सूचियां हैं। इसे समझाने के लिए, यहां i-th समस्या के लिए, हमारे पास chances[i] प्रतिशत संभावना है इसे points[i] अंकों के लिए हल करने की। हमारे पास एक अन्य मान k भी है जो उन समस्याओं की संख्या दर्शाता है जिन्हें हम प्रयास कर सकते हैं। एक ही समस्या को दो बार प्रयास नहीं किया जा सकता।

यदि हम एक इष्टतम रणनीति तैयार करते हैं, तो हमें प्रतियोगिता में प्राप्त होने वाले अंकों की अपेक्षित मूल्य ज्ञात करना होगा, जिसे निकटतम पूर्णांक तक पूर्णांकित किया जाता है। हम i-th समस्या को प्रयास करने की अपेक्षित मूल्य की अपेक्षा कर सकते हैं points[i] * chances[i] / 100.0, और यह उन अंकों की औसत संख्या दर्शाता है जो हमें मिलेंगे।

इसलिए, यदि इनपुट points = [600, 400, 1000], chances = [10, 90, 5], k = 2 जैसा है, तो आउटपुट 392 होगा।

हल करने के चरण

n := points का आकार
i के लिए 0 से n तक की रेंज में, करें chances[i] := chances[i] / 100.0
R := points के अनुसार अवरोही क्रम में व्यवस्थित 0-3
int(dp(0, K)) लौटाएं
dp() फ़ंक्शन परिभाषित करें। यह i, k लेगा
- यदि i, n के समान है, तो 0.0 लौटाएं
- j := R[i]
- p := chances[j]
- ev := p * points[j]
- यदि k, 1 के समान है, तो ev और dp(i + 1, k) का अधिकतम लौटाएं
- dp(i + 1, k - 1) * (1 - p) + ev और dp(i + 1, k) का अधिकतम लौटाएं

उदाहरण

class Solution:
    def solve(self, points, chances, K):
        n = len(points)
        for i in range(n):
            chances[i] /= 100.0
        R = sorted(range(n), key=points.__getitem__, reverse=True)
        def dp(i, k):
            if i == n:
                return 0.0
            j = R[i]
            p = chances[j]
            ev = p * points[j]
            if k == 1:
                return max(ev, dp(i + 1, k))
            return max(dp(i + 1, k - 1) * (1 - p) + ev, dp(i + 1, k))
        return int(dp(0, K))

ob = Solution()
print(ob.solve([600, 400, 1000], [10, 90, 5], 2))

इनपुट

[600, 400, 1000], [10, 90, 5], 2