Python प्रोग्राम - ब्लैकलिस्टेड स्टेप से बचते हुए गेंद के निचले स्तर तक गिरने के तरीकों की गिनती

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

उदाहरण

इनपुट: h = 5, blacklist = [2, 1]

आउटपुट: 2

व्याख्या: राउंड 0 पर, पहले एक कदम चलें (5 से 4), फिर अगले राउंड में 4 से 0। एक और संभावित तरीका: राउंड 0 पर दो कदम चलें (5 से 3), फिर अगले राउंड में 3 से 0।

एल्गोरिदम (डायनामिक प्रोग्रामिंग)

1. blacklist को सेट में बदलें
2. यदि 0 या h ब्लैकलिस्ट में है: 0 लौटाएं
3. dp := आकार h+1 की सूची, प्रत्येक इंडेक्स पर [0, 0] स्टोर करें
4. dp[0] := [1, 1]
5. m := 10^9 + 7
6. i 1 से h तक:
   • प्रत्येक x in [1, 2, 3, 4] के लिए:
     • यदि i - x >= 0 और i - x ब्लैकलिस्ट में नहीं:
       • यदि x != 3: dp[i][0] += dp[i - x][1]
       • यदि x != 2: dp[i][1] += dp[i - x][0]
   • dp[i][0] %= m, dp[i][1] %= m
7. dp[h][0] लौटाएं

Python कार्यान्वयन

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))  # आउटपुट: 2

इनपुट/आउटपुट

Input: 5, [2, 1]
Output: 2