المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۳

یک جدول $۱ \times ۷$ خالی داریم که به خانه‌های آن از سمت چپ به راست، شماره‌های ۰ تا ۶ را نسبت داده‌ایم. می‌خواهیم عناصر $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$ به جدول٬ خانه ۶ خالی بوده است و لزومی نداشت که به خانه‌ی دیگر برود.

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

الف: $$a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e \longrightarrow f \longrightarrow g$$

ج: $$a \longrightarrow c \longrightarrow e \longrightarrow g \longrightarrow b \longrightarrow d \longrightarrow f$$

د: $$a \longrightarrow d \longrightarrow e \longrightarrow f \longrightarrow c \longrightarrow g \longrightarrow b$$


ابزار صفحه