المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۱:سوال ۱۶

سوال ۱۶

یک دنباله از رقم‌های ‎۰‎ و ‎۱‎ را یک رشته می‌نامیم. رشته‌ی ‎$A$‎ را زیررشته‌ی ‎$B$‎ گوییم اگر ‎$A$‎ از حذف تعدادی (صفر یا بیش‌تر) از رقم‌های ابتدایی و انتهایی ‎$B$‎ به‌دست آید. مثلاً هر کدام از رشته‌های۱۰۱٬۰۱۱٬۰۱۱۰۱ و ‎۱۱۰‎ زیررشته‌ی ‎۰۱۱۰۱‎ هستند. اگر ‎$S$‎ یک رشته به‌طول حداکثر ‎۶‎ باشد، منظور از ‎$A_S$‎ مجموعه‌ی رشته‌های به‌طول ‎۶‎ است که ‎$S$‎ زیررشته‌ی آن‌ها نباشد. به‌ازای کدام‌یک از گزینه‌های زیر به‌عنوان ‎‎‎ ‎،$A_S \cup A_T$‎،$T$‎ ،‎$S$‎ $2^6$ عضو دارد؟ ‎

  1. ۰۱۰۱‎ و ‎۱۱۱
  2. ۱۰۱‎ و ‎۱۱۱
  3. ۱۱۰۱۱‎ و ‎۱۰۱۱۰
  4. ۰۱۰۱‎ و ‎۱۱۱۰
  5. ‎۲»، ‎«۱»‎» و ‎«۳»‎

پاسخ

گزینه (؟) درست است.

گزینه‌ای مطلوب است که به ازای دو رشته‌ی موجود در آن یک رشته‌ی ۶ حرفی یافت نشود که هر دو رشته‌ی داده شده زیر رشته‌ی آن باشند. به ازای ۰۱۰۱ و ۱۱۱ موجود در گزینه‌ی ۱ رشته‌ی ۰۱۰۱۱۱ و به ازای ۱۰۱ و ۱۱۱ موجود در گزینه‌ی ۲ رشته‌ی ۱۰۱۱۱۱ و به ازای ۱۱۰۱۱ و ۱۰۱۱۰ موجود در گزینه‌ی ۳ رشته‌ی ۱۱۰۱۱۰ موجود هستند٬ بنابراین گزینه‌های مطلوب نمی‌باشند٬ به‌ازای ۰۱۰۱ و ۱۱۱۰ موجود در گزینه‌ی ۴ هیچ رشته‌ی ۶ حرفی که هر دوتای آن‌ها زیر رشته‌ی آن باشند یافت نمی‌شود.


ابزار صفحه