eolymp
bolt
Try our new interface for solving problems
Məsələlər

Опасная игра

Опасная игра

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Вася попал в серьёзную передрягу. Он задолжал мафии N долларов, и время расплаты почти подошло. Вася хорошо знает, чем грозит несвоевременный возврат долга, поэтому он хочет собрать N долларов любой ценой.

Однако, на данный момент у него есть только M долларов. Приятель, который узнал о проблемах Васи, предложил Васе игру — в этот раз на деньги. У Васи есть K попыток сделать ставку на любую сумму от нуля до той суммы, которая у него есть — не обязательно даже целую. С вероятностью P % Вася получает ставку в двойном объёме, иначе не получает ничего. Васе не важно, сколько денег у него останется в итоге, главное, чтобы было N долларов, чтобы расплатиться. Вася, конечно же, играет оптимально. Узнайте, с какой вероятностью ему повезёт и он расплатится деньгами.

Ограничения

0 ≤ N ≤ 10^9

0 ≤ M ≤ 10^9

1 ≤ K ≤ 12

0 ≤ P ≤ 100

Giriş verilənləri

Первая строка входного файла содержит четыре целых числа: N , M , K и P .

Çıxış verilənləri

Выведите единственное число — вероятность собрать достаточную сумму. Выведите ответ с абсолютной погрешностью не более 10^{−7}.

Nümunə

Giriş verilənləri #1
1000000 750000 1 10
Çıxış verilənləri #1
0.100000000
Müəllif Евгений Капун
Mənbə Зимняя школа по программированию 2014, Харьков