Dewey's plants P51014
Every dome has a unique code made up of uppercase letters. All the codes have the same length. Given two codes x and y, define f(x, y) = ∑i | x[i] − y[i] |. Dewey visits the domes in a probabilistic way. Let Dewey be at dome x. Every noon, Dewey decides to stay in x with probability 1/2. Otherwise, Dewey choses a new dome y with probability proportional to f(x, y).
For example, suppose that the codes are AE, BB, CE and DG, and that Dewey is currently at AE. Since f(AE, BB) = 4, f(AE, CE) = 2 and f(AE, DG) = 5, with sum 11, Dewey stays at AE with probability 1/2, and goes to BB, CE and DG with probabilities 1/2 · (4/11), 1/2 · (2/11) and 1/2 · (5/11), respectively.
Millions of days have passed, and an alien spaceship meets Valley Forge. For every dome, what is the probability that Dewey is there? Assume that Dewey moves from one dome to another in just a few minutes, that Dewey began at the dome with the smallest alphabetical code in the morning, and that the alien spaceship arrives on the evening of the p-th day after Dewey started taking care of the plants (for instance, p = 0 would mean the very same day, so the probability that Dewey is at the initial dome would be 1/2). Curiously, p is exactly the 107-th prime number.
Input
Input consists of several cases, each one with the number of domes n followed by its codes: n strings made up of only uppercase letters, all different and with the same length. You can assume 2 ≤ n ≤ 1000.
Output
For every case, print with four digits after the decimal point the probability that Dewey is at each dome when the aliens arrive. The input cases have no precision issues.
Input
4 AE BB CE DG 2 A B 5 KEY NEW ICE BYE MAP
Output
0.2200 0.3000 0.1800 0.3000 0.5000 0.5000 0.1710 0.1691 0.1746 0.3199 0.1654
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++