পাইথনে কালো তালিকাভুক্ত পদক্ষেপগুলি এড়িয়ে বল সর্বনিম্ন স্তরে নেমে যাওয়ার উপায় গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি মান 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]
m :=10^9 + 7
আমি 1 থেকে h রেঞ্জের জন্য, কর
- [1, 2, 3, 4]-এ প্রতিটি x এর জন্য, করুন
  - যদি 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
রিটার্ন dp[h, 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]