المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۲۲

سوال ۲۲

افراد با شماره‌های ۱ تا ۶ به ترتیب دور میز دایره‌ای شکل و در جهت ساعت‌گرد نشسته‌اند و هریک ورقه‌ای دارند که بر روی آن یک عدد نوشته شده است (عدد فرد شماره‌ي $i$ را $A[i]$ می‌نامیم). الگوریتم زیر را ۱۳۸۸ مرحله تکرار می‌کنیم:

۱) هر فرد با شماره‌ی فرد ورقه‌اش را با نفر کناری‌اش (در جهت ساعت‌گرد) مقایسه می‌کند. خود عدد کوچک‌تر و نفر کناری‌اش عدد بزرگ‌تر را برمی‌دارد.

۲) هر فرد با شماره‌ی زوج ورقه‌اش را با نفر کناری‌اش (در جهت ساعت‌گرد) مقایسه می‌کند. خود عدد کوچک‌تر و نفر کناری‌اش عدد بزرگ‌تر را برمی‌دارد.

اگر $A[1..6] = \langle 2, 4, 5, 6, 8, 9 \rangle$ باشد٬ بعد از اجرای ۱ مرحله $A[1..6] = \langle 9, 5, 4, 8, 6, 2 \rangle$ خواهد بود. بعد از اجرای ۱۳۸۸ مرحله ورقه‌ای که عدد ۲ روی آن نوشته شده است در دست کدام فرد خواهد بود؟

  1. شماره‌ی ۱
  2. شماره‌ی ۲
  3. شماره‌ی ۴
  4. شماره‌ی ۵
  5. شماره‌ی ۶

پاسخ

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

می‌دانیم عدد ۲ کوچک‌ترین عدد در بین اعداد است، در نتیجه همواره عنصر کوچک‌تر است. بدین ترتیب از مرحله‌ی اول به بعد همواره در جایگاه‌های زوج باقی خواهد ماند و همواره دو خانه نسبت به قبل عقب‌تر خواهد رفت. در مرحله‌ی اول در خانه‌ی ششم قرار دارد و باتوجه به اینکه ۱۳۸۸ باقی‌مانده‌اش بر ۳ برابر با ۲ است در آخرین مرحله در خانه‌ی چهارم قرار می‌گیرد (هر سه مرحله به جایگاه قبلیش برمی‌گردد).


ابزار صفحه