কম্পিউটার

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


ধরুন আমাদের একটি অ্যারে রঙ আছে, একটি নিয়মিত এন-গনের জন্য রং প্রতিনিধিত্ব করে। এখানে এই 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

  1. পাইথন ব্যবহার করে সমস্ত নোডে পৌঁছানোর জন্য ন্যূনতম সংখ্যক শীর্ষবিন্দু খুঁজে বের করার প্রোগ্রাম

  2. পাইথনে প্রদত্ত প্রান্তগুলি অন্তর্ভুক্ত করে এমন অনন্য পাথের সংখ্যা গণনা করার প্রোগ্রাম

  3. পাইথনে মার্জ করার পরে ন্যূনতম সংখ্যার রঙগুলি খুঁজে বের করার প্রোগ্রামটি থাকে

  4. পাইথনে প্রদত্ত সংখ্যার সমস্ত অঙ্কের যোগফল খুঁজে বের করার প্রোগ্রাম