المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

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

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

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


ابزار صفحه