Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۳

یک جدول ۱×۷ خالی داریم که به خانه‌های آن از سمت چپ به راست، شماره‌های ۰ تا ۶ را نسبت داده‌ایم. می‌خواهیم عناصر a٬ b تا g را به آن اضافه کنیم و برای هر کدام، یک مکان اولیه مطابق جدول روبه‌رو در نظر گرفته‌ایم.

عناصر مذکور به ترتیب دل‌خواه برای درج به جدول وارد می‌شوند. اگر مکان اولیه‌ی عنصر x برابر k باشد (مثلا برای a این مقدار برابر ۳ است)، به ترتیب مکان‌های k, mod ۷ (k+1), mod ۷ (k+2), تا mod ۷ (k+6), را بررسی می‌کنیم و x را در اولین مکان خالی قرار می‌دهیم. می‌دانیم j mod i باقی‌مانده‌ی تقسیم صحیح عدد i بر عدد j است. به ازای ترتیب‌های مختلف اضافه کردن عناصر g,…, b,a به جدول، کدام‌یک از حالت‌های زیر نمی‌تواند حاصل شود؟

  1. هیچ‌کدام، تمام موارد می‌توانند باشند

پاسخ

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

در مورد گزینه (ب)٬ چون a در مکان ۶ قرار گرفته است معلوم می‌شود که قبل از آن مکان‌های ۴٬۳ و ۵ پر بوده است که یکی از آن‌ها یعنی مکان ۴ توسط f پر شده است٬ بنابراین f قبل از a وارد جدول شده است.

از طرف دیگر مکان اولیه‌ی f خانه ۶ می‌باشد که هنگام ورود به جدول در صورت پر بودن آن خانه به یک خانه دیگر می‌رود. لحظه ورود عنصر f به جدول٬ خانه ۶ خالی بوده است و لزومی نداشت که به خانه‌ی دیگر برود.

ترتیب ورود حروف به جدول در مورد گزینه‌های الف٬ ج و د به ترتیب به شکل زیر می‌تواند باشد:

الف: abcdefg

ج: acegbdf

د: adefcgb


ابزار صفحه