পাইথনে সবচেয়ে לאלא ব্যবহার করা এলিমেন্টকে শেষে নিয়ে যাওয়া কিউ ডিজাইন করার প্রোগ্রাম

আমাদের একটি কিউ ডিজাইন করতে বলা হয়েছে যা সবচেয়ে gầnে ব্যবহার করা এলিমেন্টকে শেষে নিয়ে যায়। কিউটি ১ থেকে n পর্যন্ত পূর্ণসংখ্যা দিয়ে ইনিশিয়ালাইজ করা হবে। এখন আমাদের একটি ফাংশন বানাতে হবে যাতে যখনই এটি কল করা হবে, ইনপুট হিসেবে দেওয়া পজিশন থেকে মানটি কিউর শেষে নিয়ে যাবে। আমরা ফাংশনটি একাধিকবার কল করব, এবং ফাংশনটি কিউর শেষে বর্তমানে থাকা মানটি রিটার্ন করবে এর মুভিং টাস্ক সম্পাদন করার সময়।

উদাহরণস্বরূপ, কিউটি n = 5 দিয়ে ইনিশিয়ালাইজ করা হয়েছে, অর্থাৎ এতে ১ থেকে ৫ পর্যন্ত মান থাকে। এবং যেসব পজিশনে মুভ করা হবে সেগুলো হলো ৫, ২, ৩, এবং ১, তবে আউটপুট হবে ৫, ২, ৪, ১।

সমাধানের ধাপসমূহ (Sqrt Decomposition)

• i := bisect_right(index, k) - 1 যেখানে k ডেটা[i]-এর ডান পাশে সর্টেড অর্ডার মেনটেইন করতে ইনসার্ট করা যাবে

• x := data[i].pop(k - index[i])

• ii = i+1 থেকে index-এর আকার পর্যন্ত লুপ চালান:

  • index[ii] := index[ii] - 1

• যদি data[-1]-এর আকার >= nn হয়, তবে:

  • data-এর শেষে একটি নতুন লিস্ট যোগ করুন

  • n-কে index-এর শেষে যোগ করুন

• x-কে data-এর শেষে যোগ করুন

• যদি data[i] খালি হয়, তবে:

  • data-এর i-তম এলিমেন্ট মুছে দিন

  • index-এর i-তম এলিমেন্ট মুছে দিন

• x রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

from bisect import bisect_right
from math import sqrt

class TestQueue:
    def __init__(self, n):
        self.n = n
        self.nn = int(sqrt(n))
        self.data = []
        self.index = []
        for i in range(1, n+1):
            ii = (i-1)//self.nn
            if ii == len(self.data):
                self.data.append([])
                self.index.append(i)
            self.data[-1].append(i)
    def solve(self, k):
        i = bisect_right(self.index, k)-1
        x = self.data[i].pop(k - self.index[i])
        for ii in range(i+1, len(self.index)):
            self.index[ii] -= 1
        if len(self.data[-1]) >= self.nn:
            self.data.append([])
            self.index.append(self.n)
        self.data[-1].append(x)
        if not self.data[i]:
            self.data.pop(i)
            self.index.pop(i)
        return x

queue = TestQueue(5)
print(queue.solve(5))
print(queue.solve(2))
print(queue.solve(3))
print(queue.solve(1))

ইনপুট

queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))

আউটপুট

5 2 4 1