المپدیا

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

ابزار کاربر

ابزار سایت


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

یکی از این دو تا از اون

دینگو یک درخت دودویی کامل با ارتفاع $n$ و $2^n$ برگ دارد. او روی برگ‌های این درخت از سمت چپ به راست به ترتیب اعداد $0$ تا $2^n-1$ را می‌نویسد. دینگو روی بقیه‌ی راس‌ها نیز به این صورت عدد می‌نویسد: عدد یک راس غیر برگ برابر است با عدد فرزند سمت چپ آن بعلاوه‌ی دو برابر عدد فرزند سمت راست آن. نمونه‌ای از نحوه‌ی ساخت این درخت را به ازای $n=3$ در شکل زیر مشاهده می‌کنید. عدد روی ریشه را $A$ می‌نامیم.

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

$4$- الف ($8$ نمره) : اگر $n=10$ باشد، باقیمانده‌ی $A^3$ بر $\Delta$ چند است؟

پاسخ

4880

$4$- ب ($7$ نمره) : اگر $n=10^3$ باشد، باقیمانده‌ی $A^3$ بر $\Delta$ چند است؟

پاسخ

7143

$4$- ج ($7$ نمره) : اگر $n=10^6$ باشد، باقیمانده‌ی $A^3$ بر $\Delta$ چند است؟

پاسخ

4079

$1$- د ($10$ نمره) : اگر دینگو بتواند ترتیب اعداد نوشته شده روی برگ‌ها را عوض کند،‌ به ازای $n=2015$ باقیمانده‌ی بزرگترین مقدار ممکن برای $A$ بر $\Delta$ چند است؟

پاسخ

4650


ابزار صفحه