Олимпиадный тренинг

Задача . C. Игра со строками

Задача

Темы: битмаски дп Теория вероятностей *2600

Вы играете в игру со своим другом. Ниже приведено описание этой игры.

Ваш друг придумывает n различных строк одинаковой длины m и сообщает вам все строки. Далее он выбирает случайным образом одну из них. Он выбирает строки равновероятно, то есть вероятность выбора каждой из n строк равна $\text{[math]}$ . Вы хотите угадать, какую из строк выбрал ваш друг.

Для того, чтобы угадать строку, загаданную другом, вам разрешается задавать другу вопросы. Каждый вопрос имеет следующую форму: «Какой символ стоит на позиции pos в загаданной тобой строке?». Строка считается угаданной, когда ответы на заданные вопросы однозначно определяют загаданную строку. После того, как строка становится угаданной, вы прекращаете задавать вопросы.

У вас нет определённой стратегии, поэтому очередным вопросом вы каждый раз равновероятно выбираете одну из еще не названных позиций. Ваша задача — определить математическое ожидание количества вопросов, необходимых для того, чтобы угадать выбранную вашим другом строку.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 50) — количество строк, придуманных вашим другом.

В следующих n строках заданы строки, придуманные вашим другом. Гарантируется, что все строки различны и состоят только из строчных и прописных букв латинского алфавита. Кроме того, длины всех строк одинаковы и лежат в промежутке от 1 до 20 включительно.

Выходные данные

Выведите единственное число — искомое математическое ожидание. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10^- 9.

Примечание

В первом примере придуманные строки различаются только символом в третьей позиции. Поэтому возможны следующие ситуации:

вы угадаете загаданную строку за один вопрос. Вероятность этого события $\text{[math]}$ ;
вы угадаете загаданную строку за два вопроса. Вероятность этого события равна $\text{[math]}$ · $\text{[math]}$ = $\text{[math]}$ (поскольку в таком случае первым вопросом нужно спросить про позицию отличную от трех);
вы угадаете загаданную строку за три вопроса. Вероятность этого события равна $\text{[math]}$ · $\text{[math]}$ · $\text{[math]}$ = $\text{[math]}$ ;

Таким образом искомое математическое ожидание равно $\text{[math]}$

Во втором примере нам максимум может потребоваться два вопроса, поскольку любая пара вопросов определяет строку. Поэтому искомое математическое ожидание равно $\text{[math]}$ .

В третьем примере, независимо от того, про какую позицию мы спросим первым вопросом, мы сразу угадаем загаданную строку.

Примеры

№	Входные данные	Выходные данные
1	2 aab aac	2.000000000000000
2	3 aaA aBa Caa	1.666666666666667
3	3 aca vac wqq	1.000000000000000

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет