Метание камней по воде
Вы бросаете камни по озеру. Чтобы камень прыгал, вы бросаете его горизонтально, с самой плоской стороной вниз и параллельно озеру, и вращаете его, когда он покидает вашу руку. Камень будет скользить по поверхности воды и подниматься в воздух на некоторое расстояние, затем снова скользить, повторяя это, пока не войдет в воду. Вращение камня удерживает его плоским, пока он летит по воздуху, и его направление остается относительно постоянным. Путь, который камень проходит, прыгая по озеру, довольно необычен из-за несовершенных поверхностей камня и озера. Прыжки камня (расстояния, на которые камень прыгает) в среднем становятся меньше, по мере того как камень удаляется, вероятно, из-за сопротивления воды и воздуха. Однако иногда камень проходит дальше, чем предыдущие прыжки. Также, когда камень попадает на одну из множества кувшинок на озере, он сразу же тонет после скольжения по кувшинке. Интересно, что количество прыжков камня кажется относительно постоянным (если только он не попадает на кувшинку).
Будучи увлеченным компьютерным ученым, вы разрабатываете функцию, определяющую вероятность того, что камень, прыгающий по воде, избежит всех кувшинок. У функции два входных параметра: узор кувшинок (pads) на озере в направлении вашего броска и максимальное расстояние (maxDist), на которое камень может прыгнуть после первого удара о воду.
pads будет вводиться в виде строки. Каждый символ в строке будет представлять собой участок озера: '.' обозначает открытую воду, а 'X' обозначает кувшинку. Предположим, что озеро продолжается бесконечно вправо от узора, повторяя узор снова и снова. Например, узор ".X.X.." соответствует озеру .X.X...X.X...X.X.., которое продолжается бесконечно вправо. Вы бросаете камень с левой стороны озера направо и нацеливаете его так, чтобы камень ударился о первый участок озера (первый символ в pads, который всегда гарантированно является открытой водой). Также предположим, что горизонтальное направление камня не меняется (т.е. горизонтальное движение камня всегда вдоль узора кувшинок).
maxDist определяет, с какой силой вы бросаете камень. Вы предполагаете, что для первого прыжка максимальное расстояние, на которое он может прыгнуть, составляет maxDist участков озера. После каждого прыжка максимальное расстояние уменьшается на единицу, что дает максимальное расстояние maxDist - N участков для прыжка N (N начинается с 0). Камень погружается в ледяную воду, когда N равно maxDist или когда камень попадает на кувшинку. Чтобы учесть хаотичные узоры прыжков, вы предполагаете, что камень имеет равные шансы прыгнуть на любое целое расстояние от 1 до maxDist - N включительно для прыжка N (для упрощения задачи предположим, что камень всегда приземляется в середине участка).
Ваше возвращаемое значение должно быть вероятностью от 0 до 100, что представляет собой процентную вероятность того, что камень не попадет на кувшинки.
Входные данные
Первая строка содержит строку pads. Она будет содержать от 1 до 50 символов включительно и будет состоять только из символов '.' и 'X'.
Вторая строка содержит maxDist. Она будет от 2 до 100 включительно.
Выходные данные
Выведите одно значение — вероятность от 0 до 100. Ваш ответ будет считаться правильным, если он будет в пределах 10^{-9} относительной или абсолютной ошибки от правильного ответа.