পাইথনে কনটেস্টে সর্বোচ্চ এক্সপেক্টেড পয়েন্ট বের করা (অপ্টিমাল Стра্যাটেজি)

এক প্রোগ্রামিং কনটেস্টে একাধিক প্রজেক্ট আছে কিন্তু একটি সমাধান করলেই কনটেস্ট শেষ। প্রতিটি প্রজেক্ট i-র জন্য points[i] পয়েন্ট এবং chances[i]% সম্ভাবনা আছে। আমরা সর্বোচ্চ kটি প্রজেক্ট চেষ্টা করতে পারি (একটি দুবারা না)। অপ্টিমাল Стра্যাটেজি ফলো করে এক্সপেক্টেড পয়েন্ট (নিকটতম পূর্ণসংখ্যায় রাউন্ড করে) বের করতে হবে।

উদাহরণ: points=[600,400,1000], chances=[10,90,5], k=2 → আউটপুট 392।

সমাধানের ধাপসমূহ (DP + গ্রিডি সর্টিং)

chances[i] /= 100.0 করে প্রোবাবিলিটি বানান।
প্রজেক্টগুলো points ডিসেন্ডিং অর্ডারে সর্ট করুন (সর্বোচ্চ পয়েন্টের প্রজেক্ট আগে চেষ্টা করা 베হাতার)।
dp(i, k) ফাংশন: i-তম প্রজেক্ট থেকে শুরু করে k টি চেষ্টা বাকি থাকলে এক্সপেক্টেড পয়েন্ট।
রিকারেন্স: ev = p * points[j]। যদি k==1: max(ev, dp(i+1, k))। অন্যথায়: max(dp(i+1, k-1)*(1-p) + ev, dp(i+1, k))।
int(dp(0, 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