Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Поле чудес - 2

(Время: 1 сек. Память: 32 Мб Сложность: 62%)

Всем известно сверхпопулярное теле-шоу «Поле чудес».

В игре принимают участие 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.TXTOUTPUT.TXT
13 1
CONTEST
0.7 0.2 0.1
0.4648222937

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

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483