Задачи
Хеш-таблица
Хеш-таблица
Недавно Вася узнал про новую структуру данных: хеш-таблицу с открытой адресацией. Хеш-таблица с открытой адресацией состоит из \textit{N }ячеек, пронумерованных от 1 до \textit{N }. Каждая из них может быть или свободна, или хранить какое-то значение. При вставке нового значения от него вычисляется хеш --- случайное число от 1 до \textit{N }(назовём его\textit{h}) --- после чего, если ячейка под номером \textit{h }свободна, то значение записывается в нее. Иначе, если ячейка \textit{h }+ 1 свободна, то значение вставляется в неё, иначе проверяются ячейки \textit{h }+ 2, \textit{h }+ 3 и так далее. Если поиск дошёл до \textit{N}-й ячейки, и она тоже занята, поиск продолжается с ячейки под номером 1. Таким образом, пока в таблице есть свободные места, значение так или иначе будет добавлено.
Каждая проверка ячейки, которая оказалась занята, называется коллизией. Например, если значение, хеш которого равен \textit{h}, оказалось записанным в ячейку \textit{h}+2, то при его вставке произошли две коллизии. Коллизии замедляют работу хеш-таблицы, поэтому Вася решил узнать, сколько коллизий будет в среднем, если в пустую хеш-таблицу вставить \textit{M }различных значений. А вычислять, как всегда, вам.
\subsection{Ограничения}1 \textit{≤ N ≤ }100
0 \textit{≤ M ≤ N}
\InputFile
Первая строка входного файла содержит два целых числа: \textit{N }и \textit{M }.
\OutputFile
Выведите единственное число --- среднее количество коллизий. Выведите ответ с абсолютной или относи- тельной погрешностью не более 10^\{−7\}.
Входные данные #1
5 1
Выходные данные #1
0.000000000