eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Хеш-таблица

Хеш-таблица

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Недавно Вася узнал про новую структуру данных: хеш-таблицу с открытой адресацией. Хеш-таблица с открытой адресацией состоит из N ячеек, пронумерованных от 1 до N . Каждая из них может быть или свободна, или хранить какое-то значение. При вставке нового значения от него вычисляется хеш — случайное число от 1 до N (назовём егоh) — после чего, если ячейка под номером h свободна, то значение записывается в нее. Иначе, если ячейка h + 1 свободна, то значение вставляется в неё, иначе проверяются ячейки h + 2, h + 3 и так далее. Если поиск дошёл до N-й ячейки, и она тоже занята, поиск продолжается с ячейки под номером 1. Таким образом, пока в таблице есть свободные места, значение так или иначе будет добавлено.

Каждая проверка ячейки, которая оказалась занята, называется коллизией. Например, если значение, хеш которого равен h, оказалось записанным в ячейку h+2, то при его вставке произошли две коллизии. Коллизии замедляют работу хеш-таблицы, поэтому Вася решил узнать, сколько коллизий будет в среднем, если в пустую хеш-таблицу вставить M различных значений. А вычислять, как всегда, вам.

Ограничения

1 ≤ N ≤ 100

0 ≤ M ≤ N

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
5 1
Вихідні дані #1
0.000000000
Автор Евгений Капун
Джерело Зимняя школа по программированию 2014, Харьков