المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوال ۱۹

سوال ۱۹

دنباله‌ي $a_۱, a_۲...a_m$ از اعداد ۱ تا $n$ را خوب می نامیم اگر به ازای هر $i \lt j$ که $a_i = a_j$ هیچ یک از اعداد ظاهر شده در $a_{i+۱}, a_{i+۲}...a_{j-1}$ خارج از بازه‌ $[a_i, a_{i+1}...a_j]$ ظاهر نشده باشند. در واقع در یک دنباله‌ي خوب ، اعداد ظاهر شده بین دو عدد مساوی نباید در خارج از بازه بینشان ظاهر شده باشند.

به عنوان مثال دنباله ۱,۲,۳,۱,۴,۱ یک دنباله ی خوب است ولی دنباله ی ۱,۲,۳,۱,۴,۲ خوب نیست، چون عدد ۲ هم بین دو تا ۱ ظاهر شده است و هم بیرون آنها. طول بزرگترین دنباله‌ی خوب با اعداد ۱ تا $n$ چند است؟

  1. $۴n$
  2. $۳n$
  3. $۲n-۱$
  4. $۲n$
  5. $۴n-۱$

پاسخ

گزینه‌ی ۲ درست است.

اگر در دنباله یک عدد چهار بار استفاده شود، همان چهار عدد ناقض شرط مسئله هستند (چرا؟).

پس طول دنباله حداکثر $3n$ خواهد بود. در صورتی که از هر عدد سه بار استفاده شود و تمام اعداد یکسان در کنار هم آمده باشند به راحتی دیده می‌شود که شرط مسئله در آن صدق می‌کند:

$$111222…nnn$$


ابزار صفحه