পাইথনে n বা ততোধিক পয়েন্ট পাওয়ার সম্ভাবনা বের করার প্রোগ্রাম

একটি অনন্য গেম खेलার পরিস্থিতি বিবেচনা করুন যেখানে তিনটি মান আছে: n, k, এবং h। আমরা 0 পয়েন্ট থেকে শুরু করি। প্রতিটি বারে আমরা 1 থেকে h (সহিত) পর্যন্ত যেকোনো একটি সংখ্যা যাদুকরীভাবে বেছে নিই এবং ততটুকু পয়েন্ট পাই। আমরা খেলা বন্ধ করিเมื่อ আমাদের পয়েন্ট কমপক্ষে k হয়ে যায়। আমাদের বের করতে হবে যে আমাদের n বা ততোধিক পয়েন্ট থাকার সম্ভাবনা কত। এখানে প্রতিটি সংখ্যা বেছে নেওয়ার সম্ভাবনা সমান।

উদাহরণস্বরূপ, যদি ইনপুট হয় n = 2, k = 2, h = 10, তবে আউটপুট হবে 0.11।

সমাধানের পদ্ধতি

এই সমস্যাটি ডাইনামিক প্রোগ্রামিং (DP) এবং মেমোইজেশন (memoization) ব্যবহার করে সমাধান করা যায়। মূল চাবিকাঠি হল প্রতিটি অবস্থা (state) এর জন্য সম্ভাবনা ক্যাশ (cache) করে রাখা যাতে একই υποসমস্যা বারবার সমাধান করতে না হয়।

এলগরিদমের ধাপসমূহ:

1. একটি dp() ফাংশন সংজ্ঞায়িত করুন যা গ্রহণ করবে path (বর্তমান পয়েন্ট)।
2. বেস কেসসমূহ:
   • যদি path == k - 1 হয়, তবে রিটার্ন করুন min(n - k + 1, h) / h।
   • যদি n হয়, তবে রিটার্ন করুন 0।
   • যদি path >= k হয়, তবে রিটার্ন করুন 1।
3. রিকারেন্স রিলেশন: return dp(path + 1) - (dp(path + h + 1) - dp(path + 1)) / h।
4. মূল ফাংশন থেকে:
   • যদি k == 0 হয়, তবে রিটার্ন করুন 1।
   • যদি n < k হয়, তবে রিটার্ন করুন 0।
   • অন্যথায় dp(0) রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, n, k, h):
        if not k:
            return 1
        if n < k:
            return 0
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(path):
            if path == k - 1:
                return min(n - k + 1, h) / h
            if path > n:
                return 0
            if path >= k:
                return 1
            return dp(path + 1) - (dp(path + h + 1) - dp(path + 1)) / h
        
        return dp(0)

ob = Solution()
print(ob.solve(2, 2, 10))  # আউটপুট: 0.11

ইনপুট ও আউটপুট

ইনপুট: 2, 2, 10
আউটপুট: 0.11