ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1678. Космический покер 3

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Космический покер. Легендарная игра, первая версия которой появилась ещё в далёком 1284 году Чужой эры. До сих пор её правила известны лишь узкому кругу профессиональных игроков. Однако Вам повезло — разработчики первой в мире программы, играющей в космический покер, обратились к Вам за помощью.
В космический покер играют N инопланетян. В начале раунда каждому из игроков раздают по M карт (назовём их личными). Личные карты игрока неизвестны его соперникам. Затем на стол по очереди выкладываются K общих карт. Общие карты кладут рубашкой вниз, поэтому они видны всем игрокам. Рука игрока состоит из его личных и общих карт — итого M + K карт. Мастей нет, карты различаются лишь достоинством. Всего есть 13 различных достоинств: "2", "3", "4", …, "9", "T", "J", "Q", "K" и "A". Играют бесконечной колодой, в которой вероятность того, что очередная карта будет иметь заданное достоинство, равна 1/13. Комбинации в космическом покере имеют вид (v1, …, vL), где L — количество различных достоинств в комбинации. Рука игрока удовлетворяет комбинации (v1, …, vL), если содержит v1 карт первого достоинства, v2 карт второго достоинства, …, vL карт L-го достоинства. Например, комбинации (2, 2) удовлетворяют руки "2JA2A" и "22233". Комбинации (2, 3) удовлетворяет рука "KQKQKQ", но не удовлетворяет рука "AAAAAA". Все комбинации имеют различную стоимость. В раунде побеждает игрок, рука которого содержит комбинацию наибольшей стоимости среди всех комбинаций на руках всех игроков. Если таких игроков несколько, объявляется ничья.
Зная личные карты первого игрока и частично открытые общие карты, посчитайте вероятность того, что этот игрок окажется единоличным победителем раунда.

Исходные данные

В первой строке через пробел записаны числа N, M и K (2 ≤ N, M ≤ 10; 1 ≤ K ≤ 5). Во второй строке записаны M символов — личные карты первого игрока. В третьей строке записано не более K символов — открытые общие карты. В четвёртой строке записано число C — количество существующих в космическом покере комбинаций (1 ≤ C ≤ 100). Далее в C строках перечислены комбинации в порядке возрастания стоимости. Каждая из них имеет вид L v1 v2vL. Числа L и vi положительны, сумма всех vi не превышает M + K.

Результат

Выведите вероятность победы первого игрока с точностью не менее 10−5.

Примеры

исходные данныерезультат
2 5 2
23456

1
1 2
0.0883526857
2 5 2
23456
78
2
7 1 1 1 1 1 1 1
1 4
0.8407915043
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2008