المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۱۴:عملی:سوال ۹

پرزیدنت

در یک جامعه‌ی متمدن مردم برای اداره‌ی امور مملکت رئیس‌جمهور منتخب خود را برمی‌گزینند. کرومزوم بیست‌و سوم هر انسانی در این جامعه نشان‌دهنده‌ی علایق سیاسی وی می‌باشد و حاوی یک رشته از حروف $a$ تا $z$ می‌باشد. پس از انتخاب رئیس‌جمهور هر کسی به اندازه‌ی شباهت علایق سیاسی خود با وی خوشحال می‌شود و هدف در این جامعه‌ی پیشرفته بیشینه کردن میزان خوش‌حالی افراد است. شباهت علایق سیاسی دو نفر برابر طول بزرگ‌ترین پیشوند کرومزوم ۲۳ آن دو می‌باشد. با داشتن اطلاعات کرومزومی افراد جامعه باید رشته‌ای ارائه کنید که در صورت رئیس‌جمهور شدن فردی با این رشته‌ی کرومزومی مجموع میزان خوش‌حالی افراد بیشینه شود. در این صورت مهندسین ژنتیک، می‌توانند چنین فردی را بسازند تا سکان هدایت جامعه را در دست گیرد.

ورودی

در سطر اول، ابتدا $n$‌تعداد افراد مورد بررسی از جامعه و سپس $m$ طول کرومزوم ۲۳ یک فرد جامعه است. در هر یک از $n$‌سطر بعدی رشته‌ی کرومزمی یک فرد می‌آید.($1\leq n \leq 10^4$ و $1 \leq m \leq 10^3$)

خروجی

در سطر اول میزان خوش‌حالی افراد را بنویسید و در سطر بعد رشته‌ی کرومزمی رئیس‌جمهور منتخب را بنویسید. لزومی ندارد که رئیس‌جمهور از جامعه‌ی نمونه انتخاب شود!!

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4 4
abyz
abcx
abxy
abcd
11
abcx

ابزار صفحه