المپدیا

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

ابزار کاربر

ابزار سایت


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

درخت گاوی

ببعی یک جایگشت از اعداد ۰ تا$ ۲^n-1$ را روی تخته یادداشت کرده است. گاوی بعد از دیدن دنباله ی ببعی، تصمیم گرفت تا تخته را تغییر دهد. گاوی یک درخت دودویی کامل کشید (درختی که در آن هر راس یا برگ است و یا دقیقا دو فرزند دارد) . سپس روی برگ $i$-ام درخت، عدد $i$-ام از جایگشت ببعی را یادداشت کرد و بعد از آن جایگشت ببعی را از روی تخته پاک کرد. ببعی بعد از دیدن درخت گاوی، روی هر راس غیر برگ درخت، یک عدد نوشت، به طوری که عدد نوشته شده روی هر راس، برابر با بیشترین عدد یادداشت شده بر روی دو فرزندش باشد. سپس ببعی مجموع همه ی اعداد یادداشت شده روی راس های درخت را محاسبه کرد و آن را $M$ نامید.

به عنوان مثال اگر $n$برابر ۲ و جایگشت ببعی برابر ۱،۰،۳،۲ باشد، آنگاه درخت گاوی به شکل زیر در می آید:

۲- الف (۱۱ نمره) : اگر $n$ برابر با ۳ باشد و بیشترین مقدار و کمترین مقدار ممکن برای $M$ را $m_۱$ و $m_۲$ بنامیم، باقیمانده ی تقسیم $(m_۱*m_۲)^۲$ بر $\Delta$ چند است؟

۲- ب (۱۱ نمره) : اگر $n$ برابر با ۱۲ باشد و بیشترین مقدار و کمترین مقدار ممکن برای $M$ را $m_۱$ و $m_۲$ بنامیم، باقیمانده ی تقسیم$(m_۱*m_۲)^۲$ بر $\Delta$ چند است؟

۲- ج (۱۱ نمره) : اگر $n$ برابر با $۱۰^۶$ باشد و بیشترین مقدار و کمترین مقدار ممکن برای $M$ را $m_۱$ و $m_۲$ بنامیم، باقیمانده ی تقسیم $(m_۱*m_۲)^۲$ بر $\Delta$ چند است؟


ابزار صفحه