المپدیا

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

ابزار کاربر

ابزار سایت


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

درخت سازی

هادی بلد است از روی یک رشته‌ی دودویی یک درخت دودویی ریشه‌دار بسازد. برای این منظور او ابتدا یک راس ریشه می‌گیرد و روی آن می‌ماند، سپس یک‌به‌یک بیت‌های رشته را می‌خواند. اگر بیت خوانده شده برابر با صفر بود، به فرزند سمت چپ راس کنونی می‌رود در غیر این صورت به فرزند سمت راست راس کنونی. ا گر زمانی هادی بخواهد به راسی برود که وجود ندارد، ابتدا آن راس را می‌سازد، اما به جای رفتن به آن راس، ادامه‌ی کار را از ریشه پی می‌گیرد. برای مثال رشته‌ی $0001101101$‌ یک درخت کامل ۷ راسی (شامل ریشه) می‌سازد.

فرض کنید رشته‌ی باینری اعداد $1389$ تا $2010$ (شامل خود این دو عدد) را بدون فاصله پشت سر هم نوشته‌ایم. سپس این رشته را به هادی داده‌ایم تا درختش را بسازد. اگر این درخت $N$ تا راس و $L$ تا برگ داشته باشد، در این صورت مقدار باقی‌مانده‌ی $(N\times L)^2$ بر $\Delta$ چند است؟


ابزار صفحه