মনে করুন আমাদের একটি সংখ্যা n আছে। আমাদের এমন একটি সিকোয়েন্স খুঁজে বের করতে হবে যা নিচের সকল নিয়ম মেনে চলে:
সিকোয়েন্সে ১ শুধুমাত্র একবার থাকবে।
২ থেকে n পর্যন্ত প্রতিটি সংখ্যা সিকোয়েন্সে দুবার থাকবে।
২ থেকে n পর্যন্ত প্রতিটি i এর জন্য, i-এর দুটি আভাসের মধ্যে দূরত্ব ঠিক i হবে।
সিকোয়েন্সে দুটি সংখ্যা a[i] এবং a[j]-এর মধ্যবর্তী দূরত্ব হলো |j - i|। আমাদের লেক্সিকোগ্রাফিক্যালি সবচেয়ে বড় সিকোয়েন্সটি খুঁজে বের করতে হবে।
যেমন, ইনপুট n = 4 হলে, আউটপুট হবে [4, 2, 3, 2, 4, 3, 1]
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:
- একটি backtrack() ফাংশন ডিফাইন করুন। এটি elems, res, start := 0 প্যারামিটার নেবে।
- যদি elems-এর সাইজ <= 0 হয়, তবে
- True রিটার্ন করুন
- যদি start >= res-এর সাইজ হয়, তবে
- False রিটার্ন করুন
- যদি res[start] -1 না হয়, তবে
- backtrack(elems, res, start + 1) রিটার্ন করুন
- i = 0 থেকে elems-এর সাইজ - 1 পর্যন্ত লুপ চালান
- num := elems[i]
- dist := 0 যদি num == 1 হয়, অন্যথায় num
- যদি (start + dist) < res-এর সাইজ এবং res[start + dist] == -1 হয়, তবে
- res[start] := num
- res[start + dist] := num
- elems থেকে i-তম এলিমেন্ট ডিলিট করুন
- যদি backtrack(elems, res, start) false হয়, তবে
- res[start] := -1
- res[start + dist] := -1
- elems-এ i পজিশনে num ইনসার্ট করুন
- নেক্সট ইটারেশনে যান
- অন্যথায়,
- True রিটার্ন করুন
- মেইন মেথড থেকে নিচের কাজগুলো করুন
- elems := n থেকে ১ পর্যন্ত নেমে আসানোর লিস্ট
- res := n*2-1 সাইজের একটি লিস্ট -1 দিয়ে ফিল করে
- backtrack(elems, res) কল করুন
- res রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:
def backtrack(elems, res, start = 0): if len(elems) <= 0: return True if start >= len(res): return False if res[start] != -1: return backtrack(elems, res, start + 1) for i in range(len(elems)): num = elems[i] dist = 0 if num == 1 else num if (start + dist) < len(res) and res[start + dist] == -1: res[start] = num res[start + dist] = num elems.pop(i) if not backtrack(elems, res, start): res[start] = -1 res[start + dist] = -1 elems.insert(i, num) continue else: return True def solve(n): elems = [ i for i in range(n,0,-1)] res = [ -1 for i in range(n*2 - 1)] backtrack(elems, res) return res n = 4 print(solve(n))
ইনপুট
4
আউটপুট
[4, 2, 3, 2, 4, 3, 1]
