Поле чудес - 2
(Время: 1 сек. Память: 32 Мб Сложность: 76%)
Всем известно сверхпопулярное теле-шоу «Поле чудес».
В игре принимают участие n человек. Их цель - отгадать загаданное слово. Изначально известна только длина слова, а буквы на специальном табло закрыты черными прямоугольниками. В свой ход игрок называет одну букву. Если эта буква встречается в слове, то все ее вхождения открываются, и игрок делает еще один ход. Если в слове нет такой буквы, то ход передается следующему игроку. От последнего игрока ход передается первому. Выигрывает тот игрок, который отгадывает последнюю букву.
Пусть, например, загадано секретное слово «CONTEST». Изначально игроки видят только «-------». Если первый игрок скажет 'E', то она открывается, и теперь табло выглядит как «----E--». Первый игрок делает еще один ход - пусть, например, он называет 'A'. В слове нет такой буквы, поэтому ход передается следующему игроку. Если тот скажет 'T', то игроки увидят «---TE-T», и так далее.
Пашин друг собирается поучаствовать в игре. Павлу интересно: каковы шансы на победу его друга. Паша оценил интеллектуальный потенциал каждого из игроков qt. Вероятность того, что игрок t правильно отгадает букву в ситуации, когда еще не были названы i букв, неизвестны еще j разных букв слова, и на табло осталось k закрытых букв, вычисляется по следующей формуле:
Здесь мы будем считать, что 00 = 1.
Вероятности угадывания каждой из все еще неизвестных букв слова одинаковы. По заданным n, очереди хода друга Павла r, загаданному слову и значениям интеллектуального потенциала игроков, определите вероятность того, что Пашин друг победит в игре.
Входные данные
Первая строка входного файла INPUT.TXT содержит n и r (2 ≤ n ≤ 10, 1 ≤ r ≤ n). На второй строке записано загаданное слово. Оно состоит из больших букв английского алфавита, и его длина не превосходит 12. Третья строка содержит n вещественных чисел - значения интеллектуального потенциала игроков (0 ≤ qt ≤ 0.99).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - вероятность победы друга Павла. Ответ должен быть дан с точностью, не хуже, чем 10-8.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 1
CONTEST
0.7 0.2 0.1 | 0.4648222937 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
