المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۰

۲۴ نفر با شماره‌های ۱ تا ۲۴ در یک ردیف کنار هم ایستاده‌اند (شماره‌ی فرد سمت چپ ۱ است). در دست هر کدام یک عدد کارت قرار دارد که روی آن‌ یکی از دو شماره‌ی ۰ یا ۱ نوشته‌ شده است. شماره‌ی روی کارت‌ها از چپ به راست به‌ صورت زیر است:

تعدادی سوت (با شماره‌های ۲،۱،… ) زده می‌شود. به‌ محض شنیدن سوت شماره‌ی $s$، نفر شماره‌ی $i$ ($ 1 \le i \le 24$) دقیقاً به‌ صورت زیر عمل می‌کند:

• اگر $s$ فرد باشد: اگر $i$ فرد است، او کارت خود را به نفر بعدی (شماره‌ی $1+i$) و اگر $i$ زوج است کارت خود را به نفر قبلی (شماره‌ی $1-i$) نشان می‌دهد.

• اگر $s$ زوج باشد: اگر $i$ زوج است، او کارت خود را به نفر بعدی در صورت وجود (شماره‌ی $1+i$) و اگر $i$ فرد است کارت خود را به نفر قبلی در صورت وجود (شماره‌ی $1-i$) نشان می‌دهد.

• دو نفر که کارت‌های خود را به هم نشان می‌دهند، اگر سمت راستی مقدار ۰ و سمت چپی مقدار ۱ داشته باشند، این دو نفر کارت‌های خود را باهم عوض می‌کنند.

دقیقاً پس از چندمین سوت کارت‌ها به‌ صورت مرتب ۱۱…۰۰۱۱…۰۰ درمی‌آید؟

  1. ۱۶
  2. ۱۲
  3. ۸
  4. ۷
  5. ۱۵

پاسخ

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

بعد از سوت $i$ام شماره روی کارت‌ها به شکلی در می‌آید که در جدول زیر نمایش داده شده‌اند:


ابزار صفحه