ধরুন আমরা একটি অনন্য গেম খেলছি এবং আমাদের তিনটি মান আছে n, k, এবং h৷ আমরা 0 পয়েন্ট থেকে শুরু করি, তারপর আমরা 1 এবং h (অন্তর্ভুক্ত) এর মধ্যে এলোমেলোভাবে একটি সংখ্যা নির্বাচন করতে পারি এবং আমরা ততগুলি পয়েন্ট পাব। আমরা যখন ন্যূনতম k পয়েন্ট স্কোর করি তখন আমরা থামি। আমাদের সম্ভাব্যতা খুঁজে বের করতে হবে যে আমাদের n বা কম পয়েন্ট আছে। এখানে যেকোন সংখ্যা এলোমেলোভাবে বাছাই করা যেতে পারে এবং ফলাফলের সকলেরই একই সম্ভাবনা রয়েছে।
সুতরাং, যদি ইনপুট n =2, k =2, h =10 এর মত হয়, তাহলে আউটপুট হবে 0.11।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এই পথ নিতে হবে.
-
যদি পথটি k − 1 এর মত হয়, তাহলে
-
রিটার্ন (সর্বনিম্ন n − k + 1 এবং h) / h
-
-
যদি পথ> n, তারপর
-
রিটার্ন 0
-
-
যদি পথ>=কে, তাহলে
-
রিটার্ন 1
-
-
ফিরুন dp(path + 1) − (dp(path + h + 1) − dp(path + 1)) / h
-
-
প্রধান ফাংশন থেকে, নিম্নলিখিতগুলি করুন -
-
k যদি শূন্য হয়, তাহলে
-
রিটার্ন 1
-
-
যদি n
-
রিটার্ন 0
-
-
dp(0)
ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution: def solve(self, n, k, h): if not k: return 1 if n < k: return 0 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))
ইনপুট
2,2,10
আউটপুট
0.11
