প্রোগ্রাম রঙিন শীর্ষবিন্দুর উপসেটের সংখ্যা খুঁজে পায় যা পাইথনে প্রদত্ত শর্ত পূরণ করে

ধরুন আমাদের একটি অ্যারে রঙ আছে, একটি নিয়মিত এন-গনের জন্য রং প্রতিনিধিত্ব করে। এখানে এই n-gon এর প্রতিটি শীর্ষবিন্দু প্রদত্ত অ্যারেতে উপস্থিত n ভিন্ন রঙের একটি দিয়ে এলোমেলোভাবে রঙিন ছিল। আমাদের বহুভুজ শীর্ষবিন্দুর বিশেষ উপসেটের সংখ্যা খুঁজে বের করতে হবে, যেমন এই উপসেটগুলি এই শর্তগুলি পূরণ করে -

• সাবসেটের আকার কমপক্ষে দুটি হতে হবে।
• যদি আমরা বহুভুজ থেকে উপসেটে উপস্থিত শীর্ষবিন্দুগুলি সরিয়ে ফেলি (সেই শীর্ষবিন্দুগুলির সংলগ্ন প্রান্তগুলিও সরানো হবে), তবে অবশিষ্ট শীর্ষবিন্দু এবং প্রান্তগুলি কিছু অবিচ্ছিন্ন পথ তৈরি করে।
• এই পাথগুলির কোনটিতে একই রঙের দুটি শীর্ষবিন্দু থাকা উচিত নয়৷
৷

আমাদের এই জাতীয় উপসেটের সংখ্যা গণনা করতে হবে। যদি উত্তরটি খুব বড় হয়, তাহলে ফলাফল মোড 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুট রঙের মত হয় =[1,2,3,4], তাহলে আউটপুট হবে 11।

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

• গণনা :=একটি খালি মানচিত্র যেখানে সমস্ত মান একটি খালি তালিকা হবে৷
৷
• n :=রঙের আকার
• আমি 0 থেকে রঙের আকার - 1 রেঞ্জের জন্য, কর
  • গণনার শেষে i ঢোকান[colors[i]]
• উত্তর :=0
• 2 থেকে n রেঞ্জের i জন্য, করুন
  • উত্তর :=উত্তর + nCr(n, i)
• গণনার সমস্ত কীগুলির তালিকায় প্রতিটি i-এর জন্য, করুন
  • l0 :=গণনা[i]
  • n0 :=l0 এর আকার
  • যদি n0> 1 হয়, তাহলে
    • আমি 0 থেকে n0-2 রেঞ্জের জন্য, কর
      i+1 থেকে n0 - 1 রেঞ্জে j-এর জন্য
      • করুন
        • d1 :=l0[j] -l0[i]
        • d2 :=l0[i] -l0[j] + n
        • যদি d1 <=n-3 বা d2<=n-3, তাহলে
          • উত্তর :=উত্তর - ১
• উত্তর ফেরত দিন

উদাহরণ

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

from collections import defaultdict
from math import factorial

def nCr(n, i):
   if n==1:
      return 1
   return factorial(n)//factorial(i)//factorial(n-i)

def solve(colors):
   count = defaultdict(list)
   n = len(colors)

   for i in range(len(colors)):
      count[colors[i]].append(i)
   answer = 0

   for i in range(2, n+1):
      answer += nCr(n, i)

   for i in count.keys():
      l0 = count[i]
      n0 = len(l0)

      if n0 > 1:
         for i in range(n0-1):
            for j in range(i+1, n0):
               d1 = l0[j] -l0[i]
               d2 = l0[i] -l0[j] + n
               if d1 <= n-3 or d2<= n-3:
                  answer -=1

   return answer

colors = [1,2,3,4]
print(solve(colors))

ইনপুট

[1,2,3,4]

আউটপুট

11