المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۷:سوال ۱۳

Necklace

دنباله‌ای از رشته‌های دودویی در یک ردیف پشت سر هم نوشته شده است. پریسا می‌خواهد یک زیردنباله(یک زیردنباله $S$ ازدنباله‌ی $P$، دنباله‌ای است که از حذف تعدادی از عناصر $P$ و حفظ ترتیب سایر عناصر به‌دست می‌آید. دقت کنید که پریسا می‌خواهد زیردنباله‌ای از دنباله‌ی رشته‌ها را انتخاب کند و نه زیر‌دنباله‌ای از ارقام این رشته‌ها. یعنی قرار است تعدادی از این رشته‌ها را با حفظ ترتیب و بدون تغییر ارقام، انتخاب کند.) از دنباله‌ی رشته‌ها را انتخاب کرده و به همان ترتیب به هم بچسباند تا یک رشته‌ی دودویی دراز ساخته شود. سپس دو انتهای این رشته‌ی دراز را نیز به هم بچسباند تا یک «گردن‌بند دودویی» به‌دست آورد. پریسا مجاز به تغییر، چرخش و یا جابه‌جایی گردن‌بندها و بیت‌های درونشان نیست.

از آن‌جا که پریسا علاقه‌ی زیادی به تقارن دارد. میزان «زیبایی» هر بیت $b$ در یک گردن‌بند دودویی را طول طولانی‌ترین رشته‌ی دودویی‌ای تعریف می‌کند که در دو طرف $b$ (در دو جهت مخالف) آمده و یکسان باشد.

برای مثال زیبایی بیت $\underline{0}$ در رشته‌ی $...1011\underline{0}1100…$ برابر ۳ است، چرا که رشته‌ی $110$ در دو طرف آن و در جهت‌های مخالف ظاهر شده است. یعنی اگر از دو طرف آن بیت و در جهت‌های مخالف حرکت کنیم، تا سه رقم، هر دو طرف یکسان‌اند، ولی در چهارمین رقم اختلاف پیش می‌آید. رشته‌ی به طول ۴ در سمت راست آن بیت، $1100$ است که با رشته‌ی به طول ۴ در سمت چپ آن(یعنی $1101$) برابر نمی‌باشد. (دقت کنید که رشته‌ی سمت چپ را از راست به چپ می‌خوانیم.)

از سوی دیگر، چون پریسا معتقد است که مغز انسان در تشخیص الگوهای متقارن طولانی دچار خطا می‌شود، زیبایی‌ هیچ بیتی را بیش‌تر از ۴ نمی‌گیرد! (در صورتی که طول طولانی‌ترین رشته که در طرفین یک بیت و در جهت‌های مخالف قرار دارد. بیش از ۴ باشد، زیبایی آن بیت را ۴ تعریف می‌کنیم.)

با این وصف، واضح است که زیبایی هر بیت یک گردن‌بند $n$بیتی حداقل صفر و حداکثر ۴ است. دقت کنید که دو رشته‌ی طرفین یک بیت ممکن است در انتها به هم رسیده و اشتراک داشته باشند. به عبارت دیگر ممکن است زیبایی یک بیت بیش از $\lfloor \frac{n-1}{2} \rfloor$ باشد. (این اتفاق در گردن‌بند‌های کوچک رخ می‌دهد.)

در شک مقابل یک گردن‌بند ۱۲-بیتی نشان داده شده و زیبایی هر یک از بیت‌های آن (در کنار بیت) آمده است. دقت کنید که طول بلند‌ترین دنباله‌ای که در طرفین بیت بالایی (در جهت‌های مخالف) ظاهر شده، فی‌الواقع بی‌نهایت است که طبق اعتقاد پریسا (درباره‌‌ی مغز انسان!) ۴ فرض گرفته می‌شود به همین صورت، زیبایی هر بیت یک گردن‌بند ۳۰-بیتی متناوب (که بیت‌های آن یکی در میان صفر و یک باشد) برابر ۴ است.

نهایتا پریسا زیبایی یک گردن‌بند را مجموع زیبایی بیت‌های آن تعریف می‌کند. برای مثال، زیبایی گردن‌بند شکل مقابل ۱۴ است.

برنامه‌ای بنویسید که:

  • $n$رشته‌ی دودویی را از ورودی بخواند.
  • زیباترین گردن‌بندی که پریسا می‌تواند با یک زیردنباله از این رشته‌ها بسازد را پیدا کند.
  • زیبایی آن گردن‌بند را در خروجی بنویسید.

ورودی

  • در سطر اول ورودی، عدد $n$ قرار دارد.
  • در سطر دوم ورودی، $n$ رشته‌ی دودویی آمده است که با فاصله از هم جدا شده‌اند.(طول هر یک از رشته‌های ورودی حداقل ۱ و حداکثر ۸ است و $1\leq n \leq 100$)

خروجی

در تنها سطر خروجی میزان زیبایی زیباترین گردن‌بند را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۱۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5
01 10 01100 0110 01101
14
1
1
4

ابزار صفحه