मान लीजिए हम एक अनोखा खेल खेल रहे हैं और हमारे पास तीन मान n, k, और h हैं। हम 0 अंकों से शुरू करते हैं, फिर हम 1 और h (सम्मिलित) के बीच बेतरतीब ढंग से एक संख्या चुन सकते हैं और हमें उतने ही अंक मिलेंगे। हम तब रुकते हैं जब हमने न्यूनतम k अंक प्राप्त कर लिए हैं। हमें यह संभावना ज्ञात करनी है कि हमारे पास n या उससे कम अंक हैं। यहां किसी भी संख्या को बेतरतीब ढंग से चुना जा सकता है और परिणामों की सभी संभावनाएं समान हैं।
इसलिए, यदि इनपुट n = 2, k = 2, h = 10 है, तो आउटपुट 0.11 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
dp() नामक एक फ़ंक्शन परिभाषित करें। यह path लेगा।
यदि path k - 1 के समान है, तो:
(n - k + 1 और h का न्यूनतम) / h वापस करें
यदि path > n, तो:
0 वापस करें
यदि path >= k, तो:
1 वापस करें
dp(path + 1) - (dp(path + h + 1) - dp(path + 1)) / h वापस करें
मुख्य फ़ंक्शन से, निम्नलिखित करें:
यदि k शून्य है, तो:
1 वापस करें
यदि n < k, तो:
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
