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

Ural SU contest. Petrozavodsk training camp. Summer 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Космический покер 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
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1678. Космический покер 3