Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۲:الگوریتم ها:سوال ۳

داده ساختاری برای کار با اعداد

فرض کنید S‌ مجموعه‌ای از اعداد حقیقی بین صفر و n است: S{x|0xn} همچنین Ij برای j=0,,n1 زیرمجموعه‌هایی از S هستند به طوری که Ij={x|jx<j+1} و S=n1j=0Ij. یک داده ساختار برای دخیره‌ی اعداد مجموعه S (و در نتیجه Ijها) پیشنهاد کنید به طوری که بتوان اعمال زیر را با مرتبه‌های خواسته شده انجام داد:

  1. Insert(x): x را به S و نیز به Ij مربوطه اضافه کند( در صورتی که قبلا وجود نداشته باشد.)
  2. Delete(x):x را از S و نیز از Ij حذف کند.
  3. List(j): عناصر موجود در Ij را بنویسید.

داده ساختار شما باید طوری طراحی شود که اعمال ۱ و ۲ حداکثر در O(log(|S|)) و بند ۳ در حداکثر O(|Ij|) انجام شود. داده ساختار و نحوه‌ی انجام اعمال فوق را دقیقا توضیح دهید. احتیاج به الگوریتم نیست.


ابزار صفحه