Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

4- الف (8 نمره) : اگر n=10 باشد، باقیمانده‌ی A3 بر Δ چند است؟

پاسخ

4880

4- ب (7 نمره) : اگر n=103 باشد، باقیمانده‌ی A3 بر Δ چند است؟

پاسخ

7143

4- ج (7 نمره) : اگر n=106 باشد، باقیمانده‌ی A3 بر Δ چند است؟

پاسخ

4079

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

پاسخ

4650


ابزار صفحه