رشته خیلی بزرگ


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

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

ابواسحاق nn نامه، s1,s2,...,sn s_1, s_2, ..., s_n\ از حروف کوچک انگلیسی دریافت کرده و نامه iiام را cic_i واحد دوست دارد.

زیبایی رشته TT برای او به صورت زیر تعریف می‌شود (تابع occurs(s,t)occurs(s, t) تعداد تکرارهای رشته tt در رشته ss را مشخص می‌کند): b(T)=i=1ncioccurs(T,si)Tb(T) = \dfrac{\sum^{n}_{i=1} c_i * occurs(T, s_i)}{|T|}

ابواسحاق که می‌خواهد زیباترین رشته را بسازد، لازم است بیشترین مقدار b(T)b(T) را به ازای همه رشته‌های به طول 1010010^{100} محاسبه کند.

او که پس از جشن بسیار خسته شده از شما می‌خواهد تا این مقدار را برایش محاسبه کنید.

ورودی🔗

در خط اول ورودی nn که نمایانگر تعداد رشته‌ها است آمده است. در خط بعدی nn عدد cic_i آمده‌اند. سپس در nn خط بعدی، در هر خط sis_i می‌آید.

1i=1nsi5001 \le \sum^{n}_{i=1} |s_i| \le 500 1ci1091 \le c_i \le 10^9

خروجی🔗

در تنها خط خروجی مقدار خواسته شده را چاپ کنید. در صورتی که جواب شما yy باشد و جواب واقعی xx باشد؛ جواب شما مورد قبول است اگر شرط xyx106\dfrac{|x-y|}{x} \le 10^{-6} برقرار باشد.

مثال🔗

ورودی نمونه ۱🔗

1
10
aa
Plain text

خروجی نمونه ۱🔗

10.000000
Plain text

در این نمونه به ازای رشته TT که از 1010010^{100} تا کاراکتر a تشکیل شده، مقدار FF برابر با 101010010 - 10^{-100} است که با دقت شش رقم اعشار ۱۰ می‌شود.

ورودی نمونه ۲🔗

4
2 3 4 5
abb
bba
aab
baa
Plain text

خروجی نمونه ۲🔗

3.500000
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.