Hello Codeforces community,
I would like to know how to solve this problem: https://codeforces.com/gym/100371/problem/M. I looked at some submitted code but no clue how they worked, they seem to use some DP in which the state is unknown to me.
It's problem M of 2014 Winter Programming School, Kharkiv, day 1 (E. Kapun). High league contest. If you don't want to download the statement file, I paste it below.
Problem M. Hash-table (High)
Input file: stdin
Output file: stdout
Time limit: 1s
Memory limit: 256 MB
Alex learned about a new data structure: a hash table with open addressing. Hash table with open addressing consists of $$$N$$$ cells numbered from 1 to $$$N$$$. Each of them may be empty, or storing a value.
When you insert a new value, it calculates the hash — random number between $$$1$$$ to $$$N$$$ (let’s call it $$$h$$$) — after which, if the cell under number $$$h$$$ is empty, the value is written into it. Otherwise, if the cell $$$h + 1$$$ is empty, the value is written into it, and otherwise it checks $$$h + 2$$$, $$$h + 3$$$ and so on. If the search has reached $$$N$$$-th cell, and it is not empty too, the search continues with the cell number $$$1$$$. Thus, if there are an empty place somewhere, the value anyway will be added.
For example, if the value is equal to the hash $$$h$$$, the cell turned recorded $$$h + 2$$$ then we can assume, that there were two collisions occurred. Collisions slow down the hash table, so Alex decided to find out how many collisions will be in average, if in a empty hash table insert $$$M$$$ different values. And calculate, as always, to you.
Constraints
$$$1 \leq N \leq 100$$$
$$$0 \leq M \leq N$$$
Input
The single line contains 2 integers: $$$N$$$ and $$$M$$$.
Output
You should print a single number — an average number of collisions. Print the answer with absolute or relative error of less than $$$10^{−7}$$$.
Example
| stdin | stdout |
|---|---|
5 1 | 0.0 |
10 2 | 0.1 |
