سوال ۱۳
فرض کنید $\langle a_1,a_2,…,a_{14}\rangle$ رشتهای از ارقام ۰ و ۱ باشد. به تعدادی رقم متوالی و برابر، یک زنجیره میگوییم. زنجیرەای که بخشی از یک زنجیرەی بزرگتر نباشد، بلوک نامیده میشود. برای مثال، رشتهی زیر از ۴ بلوک ساخته شده است:
$$\langle 0,0,0,1,1,0,0,1,1,1,1,1,1,1 \rangle$$
الگوریتم زیر را اجرا میکنیم:
- تا زمانی که تعداد بلوکهای رشته بیشتر از یک است، بلوک اول و دوم (از سمت چپ) را در نظر میگیریم و بلوک کوچکتر را حذف میکنیم (اگر اندازەی دو بلوک یکسان بود، بلوکی که شامل ارقام ۰ است، حذف میشود).
برای مثال، رشتهی بالا پس از یک مرحله به رشتهی $\langle 0,0,0,0,0,1,1,1,1,1,1,1 \rangle$ تبدیل میشود. در میان تمام حالات ممکن برای رشتهی ۱۴ رقمی آغازین، کمینهی تعداد ارقام رشتهی نهایی (پس از اجرای کامل الگوریتم مذکور) چیست؟
- ۲
- ۴
- ۶
- ۵
- ۳
راهنمایی
حداقل طول رشته اولیه را با توجه به طول رشته نهایی محاسبه کنید.
راهنمایی
طول بلوکی که در هر مرحله حذف میشود، حداقل یک واحد از طول بلوکی که در مرحله قبل حذف شده بزرگتر است. از این نکته برای محاسبه بازگشتی طول بلوکهایی که حذف میشوند استفاده کنید.
| ▸ سوال قبل | سوال بعد ◂ |