المپدیا

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

ابزار کاربر

ابزار سایت


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

سوز سرما

هادی به تازگی یک شرکت تاسیس کرده است و قصد دارد ساختمانی برای آن بسازد. با توجه به این‌که هادی می‌خواهد ظاهر ساختمان منحصر به فرد باشد، از معمار خواسته است تا آن را به شکل یک برف‌دانه‌ی کخ بسازد.

برف‌دانه‌های کخ به صورت بازگشتی قابل محاسبه هستند. مثلث متساوی الاضلاع اولین برف‌دانه‌ی کخ است. برای ایجاد $i$ امین برف‌دانه‌ی کخ، برف‌دانه‌ی $i - 1$ ام را در نظر می‌گیریم و هر ضلع آن را به سه قسمت تقسیم می‌کنیم. سپس روی قسمت میانی هر ضلع یک مثلث متساوی‌الاضلاع می‌سازیم که راس سوم آن به خارج شکل اشاره کند. در نهایت قسمت میانی را حذف می‌کنیم.

هادی راس‌های برف‌دانه‌ها را شماره‌گذاری کرده است. او ابتدا به راس‌های اولین برف‌دانه‌ی کخ(مثلث) با شروع از راس دلخواه و با حرکت در جهت ساعت‌گرد، اعداد ۱ تا ۳ را نسبت داده است. حال برای شماره‌گذاری برف‌دانه‌ی $i$ ام، راس‌هایی را که در برف‌دانه‌ی $i - 1$ ام نیز وجود داشتند، با همان شماره‌ی قبلی شماره‌گذاری کرده است. سپس با شروع از راس شماره‌ی یک به صورت ساعت‌گرد، روی رئوس حرکت کرده و با رسیدن به هر راس جدید اولین عدد طبیعی تخصیص داده نشده را به آن تخصیص داده است.

فاصله‌ی بین دو راس $i$ و $j$ در برف‌دانه‌ی $n$ ام را برابر با کمترین تعداد اضلاعی تعریف کرده است که برای رسیدن از راس $i$ به راس $j$ باید پیموده شوند و با $d(n, i, j)$ نشان داده می‌شود. برای مثال $d(1, 1, 3) = 1$ و $d(2, 1, 3) = 4$.

هادی می‌خواهد یکی از برف‌دانه‌ها را برای معماری ساختمان شرکت انتخاب کند. برای این‌کار او در هر برف‌دانه، برخی از راس‌ها را، که از نظرش مهم‌تر از بقیه هستند، انتخاب کرده است و براساس آن‌ها زیبایی معماری را ارزیابی می‌کند. به طور دقیق‌تر، فرض کنید $S_n$ دنباله‌ی شماره‌ی راس‌های مهم در برف‌دانه‌ی $n$ ام باشد و $i$ امین عضو این دنباله را با $S_{n, i}$ نشان دهیم. هادی از شما می‌خواهد $f(n, S_n)$ را محاسبه کنید که به شکل زیر تعریف می‌شود:

\[ f(n, S_n) = \sum_{i=1}^{|S_n|}\sum_{j = i + 1}^{|S_n|}{S_{n, i} \times S_{n, j} \times d(n, S_{n, i}, S_{n, j})} \]

شما برای کمک به هادی باید به سوالات زیر پاسخ دهید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 229939$ محاسبه شده‌اند.

$1$- الف ($11$ نمره) : باقی‌مانده‌ی $f(4, \{1,3, 8, 13, 34, 89\} )^5$ (به توان پنج توجه کنید) بر $\Delta$ چند است؟

پاسخ

166647

$1$- ب ($11$ نمره) : باقی‌مانده‌ی $f(10, \{3^0, 3^1, 3^2, \ldots, 3^{12} \} )$ بر $\Delta$ چند است؟

پاسخ

111986

$1$- ج ($11$ نمره) : باقی‌مانده‌ی $f(28, \{5^0, 5^1, 5^2, \ldots, 5^{23}\} )$ بر $\Delta$ چند است؟

پاسخ

219885


ابزار صفحه