المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۵:سوال ۱۲

Script

معلم محمد به او مشق داده که درس کتاب را از رو بنویسد. هنگامی که محمد دارد مشقش را می‌نویسد، در صورتی که یک کلمه باکلمه‌ای که در سطر قبلی درست بالای آن قرار گرفته یکسان باشد، محمد می‌تواند آن را ننویسد و به جایش یک ایضا در آن مکان قرار دهد؛ در زیر یک ایضا هم می‌تواند ایضا قرار بگیرد، البته در صورتی که دو کلمه‌ای که به جایشان ایضا گذاشتیم یکسان باشند. در هر سطر از دفتر مشق محمد می‌توان به هر تعداد دلخواهی قبل و بعد از هر کلمه یا ایضا، فاصله قرار داد؛ ولی در هر سطر حداکثر $m$ کلمه یا ایضا جا می‌شود.

از آن‌جایی که محمد انسان تنبلی است، دوست دارد که تا حد امکان سریع مشقش را بنویسد؛ به همین دلیل دوست دارد به گونه‌ای متن را بنویسد که از بیش‌ترین تعداد ایضا استفاده کند. آیا می‌توانید به او در این راه کمک کنید؟

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

  • متن مشق محمد و بیش‌ترین تعداد کلماتی که در یک سطر از دفتر محمد جا می‌شود را از ورودی بخواند.
  • روشی از چیدمان کلمات را بیابید که بیش‌ترین تعداد ایضا را داشته باشد.
  • پاسخ را در خروجی بنویسید.

ورودی

در سطر نخست ورودی یک عدد صحیح $n$ نوشته شده است که تعداد کلمات مشق محمد را نشان می‌دهد ($1\leq n\leq 3000$). در سطر دوم یک عدد $m$ نوشته شده که بیش‌ترین تعداد کلمه‌ای است که محمد در یک سطر می‌تواند بنویسد و $1\leq m\leq 40$ است. در هر یک از $n$ سطر بعدی یک کلمه نوشته شده است. طول کلمه‌ها حداکثر ۱۰ حرف است و کلمه‌ها از حروف کوچک الفبای انگلیسی ساخته شده‌اند.

خروجی

در تنها سطر خروجی یک عدد بنویسید که نشان‌دهنده‌ی بیش‌ترین تعداد ایضا است که می‌توان در نوشتن متن به کار برد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4
2
ab
ab
b
ab
2

ابزار صفحه