سوال ۳
دنباله‌ی $\left<a_1, a_2, \ldots, a_{1392}\right>$ شامل ۱۳۹۲ عدد متمایز داده شده است. یک جادوگر قادر است در یک چشم بر هم زدن ۶۹۶ عدد متوالی از این دنباله را به‌طور صعودی مرتب کرده و بر روی مکان‌های همان ۶۹۶ عدد از کوچک به بزرگ (صعودی) بگذارد. می‌خواهیم با تعدادی درخواست از جادوگر اعداد را از کوچک به بزرگ مرتب کنیم. هر درخواست بدین شکل است که از جادوگر می‌خواهیم از عدد $i$ام تا عدد $i+695$ام که در مجموع ۶۹۶ عدد می‌شوند را مرتب کند (عدد $i$ می‌تواند حداقل ۱ و حداکثر ۶۹۷ باشد). با حداقل چندبار درخواست از جادوگر می‌توان اعضای دنباله را مرتب کرد؟
- ۳
- ۴
- ۶
- ۱۳۹۲
- $\lceil \log_2 1392 \rceil$
پاسخ
گزینه‌ی (۳) درست است.
فرض کنید بزرگترین عدد در خانه اول و کوچکترین عدد در خانه ۱۳۹۲ ام باشد. هر کدام از این دو عدد برای انکه به مکان مطلوب خود برسند نیاز به سه درخواست دارند. فقط یک درخواست است که هر دو عدد فوق را شامل می‌شود. بنابراین حداقل 5 درخواست برای انکه کوچکترین و بزرگترین عدد به مکان مطلوب خود برسند نیاز داریم. با ۶ بار می‌توان بدین شکل اعداد را مرتب کرد. ابتدا نیمه اول و نیمه دوم را با دو درخواست مرتب می‌کنیم. سپس نیمه وسط (از عدد ۳۴۹ام تا ۱۰۴۴ام) را مرتب می‌کنیم. مجدد با دو درخواست دیگر نیمه اول و دوم را مرتب کرده و نهایتا نیمه وسط را مرتب می‌کنیم. برای اثبات درستی الگوریتم فوق فرض کنید در ابتدا برای $i<j$ داشته باشیم $a_i > a_j$. می‌توان با حالت گیری نشان داد در یکی از درخواست‌ها حتما این دو عدد جابه‌جا می‌شوند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
