المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۶

در مسئله‌ی قبل فرض کنید وقتی در یک مربّع، به تعداد عددی که رویِ آن نوشته شده نخود قرار بگیرد، از پر شدن آن جعبه مطلع می‌شویم. حال با توجه به داشتن این امکان اضافی بگویید، در شکل روبرو حدّاقل چند عمل «تغییر جهت» لازم است، تا جهت اوّلیّه‌ی علامت‌ها هرچه که باشد، بتوانیم به هر مربّع دقیقاً به تعداد عددی که رویش نوشته شده نخود بفرستیم؟

  1. ۷
  2. ۸
  3. ۱۲
  4. ۱۳
  5. ۱۴

پاسخ

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

شروع به انداختن نخودها می‌کنیم تا زمانی که یکی از خانه‌ها پر شود. در این‌صورت جهت پدر آن گره را متوجه می‌شویم. با تغییر جهت آن دایره مربع دیگری شروع به پرشدن می‌کند. پس از این‌که آن خانه نیز پر شود جهت پدر آن را تغییر می‌دهیم تا زمانی که همه مربع‌ها پر شوند. هر دایره نهایتا یک بار تغییر جهت می‌دهد. در نتیجه به تعداد خانه‌های دایره‌ای احتیاج به تغییر داریم. به مثال زیر توجه کنید:

فرض کنید شروع به ریختن نخود می‌کنیم و پس از تعدادی حرکت مربع 15تایی پر می‌شود. جهت دایره 6 را عوض می‌کنیم و خانه 9تایی شروع به پر شدن می‌کند سپس با عوض کردن دایره 7 مربع 6تایی شروع به پر شدن می‌کند. پس از آن دایره شماره 1 را تغییر جهت می‌دهیم و به همین ترتیب تا همه مربع‌ها پر شوند. واضح است که با 7 حرکت همه مربع‌ها پر خواهند شد.


ابزار صفحه