मान लीजिए हमारे पास n पंक्तियों और m स्तंभों वाला एक ग्रिड है। अमल और बिमल उस ग्रिड पर एक गेम खेल रहे हैं। गेम का नियम इस प्रकार है:
अमल शीर्ष पंक्ति में कहीं सफेद कमल टाइल रखता है और बिमल नीचे की पंक्ति में कहीं कैटरपिलर टाइल रखता है। अमल गेम शुरू करता है और वे बारी-बारी से खेलते हैं। अमल अपनी टाइल को वर्तमान सेल के ग्रिड के अंदर 8 आसन्न सेल में से किसी में भी ले जा सकता है, लेकिन बिमल की कैटरपिलर टाइल केवल ग्रिड के अंदर बाएं या दाएं जा सकती है, या उसी स्थिति में रह सकती है। अमल का लक्ष्य कम से कम चालों में बिमल को पकड़ना है, जबकि बिमल (कैटरपिलर टाइल के साथ) यथासंभव लंबे समय तक जीवित रहना चाहता है। यदि वे अपने कमल और कैटरपिलर को रखने के लिए दो स्तंभों को रैंडमली चुनते हैं, तो हमें अमल द्वारा इस गेम को जीतने के लिए आवश्यक अपेक्षित चालों की संख्या ढूंढनी है।
तो, यदि इनपुट n = 5, m = 7 है, तो आउटपुट 4.571428571428571 होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- r := 0
- l के लिए range 0 से m - 1 तक, करें
- temp := n - 1.0
- यदि l >= n, तो
- temp := temp + (l - n + 1) * ((l - 1) / m)
- यदि l < m - n, तो
- temp := temp + (m - n - l) * ((m - l - 2) / m)
- r := r + temp / m
- r वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def solve(n, m): r = 0 for l in range(m): temp = n - 1.0 if l >= n: temp += (l - n + 1) * ((l - 1) / m) if l < m - n: temp += (m - n - l) * ((m - l - 2) / m) r += temp / m return r n = 5 m = 7 print(solve(n, m))
इनपुट
5, 7
आउटपुट
4.571428571428571