Dewey’s plants

0.6 It is the future, and all plant life on Earth is extinc.
Fortunately, some specimens are preserved in geodesic domes attached to
a spaceship called Valley Forge. The unique inhabitant of the spaceship
is the drone Dewey, who takes care of the plants.

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.

0.4

[image]

[image]

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 10⁷-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.

Problem information

Author: Salvador Roura

Generation: 2026-01-25T11:04:35.422Z

© Jutge.org, 2006–2026.
https://jutge.org
