পাইথনে প্রথম n প্রাকৃতিক সংখ্যার পারমুটেশন থেকে ম্যাজিক সেটের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের প্রথম n প্রাকৃতিক সংখ্যা সহ একটি অ্যারে রয়েছে এবং অ্যারের একটি স্থানান্তর P{p1, p2, ... pn} রয়েছে। আমাদের পরীক্ষা করতে হবে কতগুলি ম্যাজিক সেট রয়েছে। একটি পরিবর্তনকে জাদু সেট বলা হয়, যদি এটি এই কয়েকটি নিয়মকে সন্তুষ্ট করে -

যদি আমাদের k থাকে, তাহলে a[1], a[2], ... a[k] অবস্থানে থাকা উপাদানগুলি তাদের সন্নিহিত উপাদানগুলির থেকে কম [P[a[i] - 1]> P[a] [i]]
আমাদের যদি l থাকে, তাহলে b[1], b[2], ... b[l] অবস্থানে থাকা উপাদানগুলি তাদের সন্নিহিত উপাদানগুলির চেয়ে বড় [P[b[i] - 1] P[b[i] + 1]]

সুতরাং, যদি ইনপুটটি n =4 k =1 l =1 k_vals =[2] l_vals =[3] এর মত হয়, তাহলে আউটপুট 5 হবে কারণ:N =4, a[1] =2 এবং b[1] =3. সুতরাং পাঁচটি স্থানান্তর হল [2,1,4,3], [3,2,4,1], [4,2,3,1], [3,1,4,2], [4 ,1,3,2]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

p :=10^9+7
F :=n+2 আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
কে_ভালে প্রতিটি a-এর জন্য, করুন
- যদি F[a - 1] হয় 1 অথবা F[a + 1] 1 হয়, তাহলে
  - যদি F[a - 1] হয় 1 অথবা F[a + 1] 1 হয়, তাহলে
    - p :=শূন্য
  - F[a] :=1
l_vals-এ প্রতিটি b-এর জন্য, করুন
- যদি F[b] 1 হয় অথবা F[b - 1] হয় -1 অথবা F[b + 1] -1 হয়, তাহলে
  - p :=শূন্য
- F[b] :=-1
যদি p নাল এর মত হয়, তাহলে
- রিটার্ন 0
অন্যথায়,
- A :=n+1 আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
- B :=n+1 আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
- FF :=n+1 আকারের একটি অ্যারে এবং নাল দিয়ে পূরণ করুন
- 1 থেকে n রেঞ্জের জন্য, করুন
  - FF[i] :=F[i] - F[i - 1]
- A[1] :=1
- 2 থেকে n রেঞ্জের i জন্য, করুন
  - করুন
    - যদি FF[i]> 0, তারপর
      - B[j] :=(B[j - 1] + A[j - 1]) mod p
    - অন্যথায় যখন FF[i] <0, তারপর
      - B[j] :=(B[j - 1] + A[i - 1] - A[j - 1]) mod p
    - অন্যথায়,
      - B[j] :=(B[j - 1] + A[i - 1]) mod p
  - এ এবং বি অদলবদল করুন
- প্রত্যাবর্তন A[n]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(n, k, l, k_vals, l_vals):
   p = 10**9+7
   F = [0] * (n + 2)
   for a in k_vals:
      if F[a - 1] == 1 or F[a + 1] == 1:
         p = None
      F[a] = 1
   for b in l_vals:
      if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
         p = None
      F[b] = -1
   if p == None:
      return 0
   else:
      A = [0] * (n + 1)
      B = [0] * (n + 1)
      FF = [None] * (n + 1)
      for i in range(1, n + 1):
         FF[i] = F[i] - F[i - 1]
      A[1] = 1
      for i in range(2, n + 1):
         for j in range(1, i + 1):
            if FF[i] > 0:
               B[j] = (B[j - 1] + A[j - 1]) % p
            elif FF[i] < 0:
               B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p
            else:
               B[j] = (B[j - 1] + A[i - 1]) % p
         A, B = B, A
      return A[n]

n = 4
k = 1
l = 1
k_vals = [2]
l_vals = [3]
print(solve(n, k, l, k_vals, l_vals))

ইনপুট

4, 1, 1, [2], [3]