पायथन में ब्लैकलिस्ट किए गए चरणों से बचकर गेंद को निम्नतम स्तर तक गिराने के तरीकों की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास एक मान h है और संख्याओं की एक सूची है जिसे ब्लैकलिस्ट कहा जाता है। वर्तमान में हम ऊँचाई h पर हैं, और एक छोटी गेंद को 0 की ऊँचाई तक ले जाने के लिए एक खेल खेल रहे हैं। अब, सम राउंड में (0 से शुरू करके) हम गेंद को 1, 2, या 4 सीढ़ियाँ नीचे ले जा सकते हैं। और विषम दौर में, हम गेंद को 1, 3, या 4 सीढ़ियाँ नीचे ले जा सकते हैं। कुछ स्तरों को काली सूची में डाल दिया गया है। इसलिए अगर गेंद वहां पहुंचती है तो वह तुरंत मर जाएगी। हमें गेंद की ऊंचाई 0 पर नीचे जाने के तरीकों की संख्या ज्ञात करनी है। यदि उत्तर बहुत बड़ा है, तो परिणाम को 10^9 + 7 से संशोधित करें।

इसलिए, यदि इनपुट h =5 ब्लैकलिस्ट =[2, 1] जैसा है, तो आउटपुट 2 होगा, क्योंकि राउंड 0 पर, पहले एक कदम (5 से 4) आगे बढ़ें, फिर अगले राउंड में 4 से 0 तक। दूसरा संभावित तरीका राउंड 0 पर हो सकता है, दो कदम (5 से 3) आगे बढ़ें, फिर अगले राउंड 3 से 0 पर जाएं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ब्लैकलिस्ट :=ब्लैकलिस्ट के तत्वों से एक नया सेट
• यदि 0 काली सूची में है या h काली सूची में है, तो
  • वापसी 0
• dp :=आकार h की एक सूची, और उस स्टोर के अंदर प्रत्येक इंडेक्स पर जोड़े [0, 0]
• dp[0] :=[1, 1]
• म :=10^9 + 7
• 1 से h की श्रेणी में i के लिए, करें
  • प्रत्येक x के लिए [1, 2, 3, 4] में, करें
    • यदि i - x>=0 और i - x काली सूची में नहीं है, तो
      • यदि x, 3 के समान नहीं है, तो
        • dp[i, 0] :=dp[i, 0] + dp[i - x, 1]
      • यदि x 2 के समान नहीं है, तो
        • dp[i, 1] :=dp[i, 1] + dp[i - x, 0]
    • dp[i, 0] :=dp[i, 0] mod m
    • dp[i, 1] :=dp[i, 1] mod m
• रिटर्न डीपी[एच, 0]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(h, blacklist):
   blacklist = set(blacklist)
   if 0 in blacklist or h in blacklist:
      return 0
   dp = [[0, 0] for i in range(h + 1)]
   dp[0] = [1, 1]
   m = 10 ** 9 + 7
   for i in range(1, h + 1):
      for x in [1, 2, 3, 4]:
         if i - x >= 0 and i - x not in blacklist:
            if x != 3:
               dp[i][0] += dp[i - x][1]
            if x != 2:
               dp[i][1] += dp[i - x][0]
         dp[i][0] %= m
         dp[i][1] %= m
   return dp[h][0]

h = 5
blacklist = [2, 1]
print(solve(h, blacklist))

इनपुट

5, [2, 1]

आउटपुट

2