المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۹:سوال ۴

سوال ۴

یک بوته در مبدأ صفحه‌ی مختصات کاشته شده است. به نقاط با مختصات صحیح صفحه، نقاط شبکه‌ای گوییم. در هر ثانیه از هر نقطه‌ی شبکه‌ای بوته که رشدی از آن صورت نگرفته، سه شاخه به طول واحد در جهت‌های راست، بالا و چپ شروع به رشد می‌کنند. در صورتی که در آن جهت شاخه‌ای از قبل موجود باشد، شاخه‌ی جدیدی رشد نمی‌کند. هم‌چنین اگر دو شاخه‌ی در حال رشد به یک نقطه برسند، یکی از آن‌ها به طور تصادفی می‌شکند. اگر هم شاخه‌ی در حال رشد به نقطه‌ای برسد که قبلاً در آن نقطه شاخه‌ای وجود داشته، می‌شکند. برای مثال پس از یک ثانیه بوته به شکل زیر در می‌آید:

در ثانیه‌ی دوم از هر کدام از نقاط شبکه‌ای جدید ($A$، $B$ و $C$)، شاخه‌ها شروع به رشد می‌کنند. با توجه به این که شاخه‌ی سمت چپ $A$ و شاخه‌ی سمت راست $C$ از قبل موجود است، این دو شاخه رشد نخواهند کرد. هم‌چنین شاخه‌ی بالای $A$ و شاخه‌ی سمت راست $B$ به یک نقطه می‌رسند، پس یکی از آن‌ها باید به تصادف بشکند (همین امر برای شاخه‌ی بالای $C$ و شاخه‌ی چپ $B$ صادق است). برای مثال یکی از حالات بوته پس از ثانیه‌ی دوم در شکل زیر قابل مشاهده است:

پس از ۴ ثانیه، شکل بوته چند حالت مختلف می‌تواند داشته باشد؟

  1. $128$
  2. $4096$
  3. $36$
  4. $32768$
  5. $\binom{12}{6}$

پاسخ

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


ابزار صفحه