<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

385. Highlander
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Football judge is a very important profession. To make stern but fair decisions during the match all judges must be in good shape. For this purpose they regularly have special judge trainings. One of the most popular trainings is a game called "Highlander". The rules of this game are quite simple. Initially, each judge receives one red card with the name of some other judge (no judge gets the card with his own name, and all the cards are different). Then, the game starts. Judges can run anywhere on the football field. The purpose is to catch the judge whose name is written on the card and show the card to him. When judge A catches judge B, judge B loses and doesn't play anymore, and A gets all his cards. Then the game continues. The game ends when the distribution of the cards reaches such a state that it is impossible to catch anybody because no judge has the card with the name of another judge who is still playing. The winner is the judge who gets the most number of cards. If several players get the same maximal amount of cards, they are all considered to be winners.

It is clear that after the distribution of cards some judges have no chance to win. Your task is to determine the expected number of judges that have a theoretical chance to win. All transpositions of cards where no judge gets the card with his name are considered equiprobable.

Input
Input file contains exactly one integer number n — the number of judges in the game (2 ≤ n ≤ 100).

Output
Output should contain one real number with relative or absolute error 10-9 — the answer to the problem.

Example(s)
sample input
sample output
2
2.00

<|response|>
1. Abridged problem statement

We have n judges and deal out a random assignment of "red cards" so that each judge holds exactly one card naming another judge, no one holds a card with their own name, and all cards are distinct. Equivalently, we have a random derangement (permutation without fixed points) of size n, whose cycle decomposition contains only cycles of length ≥ 2. In the game, each cycle collapses into one survivor who eventually collects all cards in that cycle. The winners are exactly the judges in the largest initial cycle(s), and if there are multiple cycles of that maximal length, all members of those cycles have a chance to win.

Compute the expected number of judges who have a theoretical chance to win, over the uniform distribution of derangements of size n.

2. Key observations

- A derangement of n elements can be decomposed into disjoint cycles, each of length at least 2.
- In the chase-game, each initial cycle yields exactly one survivor, and that survivor ends up holding all cards originally in the cycle.
- The "theoretical chance to win" goes to every judge in any cycle whose length equals the maximum cycle length in that particular derangement. If the largest cycle length is \(L\) and there are \(m\) cycles of length \(L\), then exactly \(m\times L\) judges have a chance in that outcome.
- We need the expectation of \(m\times L\) under the uniform derangement distribution of size n.

3. Full solution approach

a) Define a DP array
  Let
    dp[l][M][k]
  = the probability that a random partial derangement of size l (elements labeled 1…l) has no cycle longer than M, and has exactly k cycles of length M.
  We forbid cycles of length 1, so every cycle in the DP has length ≥ 2.

b) Base cases
  For any \(M\), the empty permutation (l=0) has zero cycles of any size and therefore
    dp[0][M][0] = 1.

c) Transitions
  To build a derangement of size l>0, look at the cycle containing element 1. Suppose that cycle has size s, where 2 ≤ s ≤ min(M, l). There are combinatorial arguments showing that each choice of cycle size s contributes exactly 1/l to the probability mass. Removing those s elements leaves a derangement of size l–s with the same constraints on M. If s=M, we increase the count of M-cycles by 1. Thus:
    for s from 2 to min(M, l):
      let prev_k = k – (s==M ? 1 : 0)
      dp[l][M][k] += dp[l–s][M][prev_k] / l

d) Normalization
  The DP as defined counts permutations with no 1-cycles, but it also counts all permutations that consist of cycles of length ≥2, not only derangements. In fact that is exactly the definition of a derangement. Therefore the total probability mass in
    Z = sum over M=2..n, k=1..⌊n/M⌋ of dp[n][M][k]
  equals 1 (since every derangement must have maximum cycle length ≥2 and at least one cycle of that length). We include this step for clarity; you can verify Z≈1 numerically.

e) Compute the expected value
  The quantity of interest is
    E[m×L] = sum over M=2..n, k=1..⌊n/M⌋ of [ dp[n][M][k] * (k×M) ].
  If Z were not exactly 1 (due to floating-point rounding), we would divide by Z. Finally output this expectation with 9 decimal digits.

f) Complexity
  There are O(n³) DP transitions (l = 1..n, M = 1..n, k up to ⌊l/M⌋, and s up to M), which is feasible for n ≤ 100.

4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;

void read() { cin >> n; }

void solve() {
    // Let's consider judge i has card p[i], or in other words we have a
    // permutation p[1], ..., p[n]. We can notice that in the end of the game,
    // each cycles in this permutation will be compressed into a single judge.
    // Then a judge can win if and only if it's part of a largest cycle. In
    // other words we are looking for E[positions i which are part of a largest
    // cycle], over all permutations of length n. One important constraint is
    // that we can't have cycles of length 1 - this is because a person can't
    // start with its own card. We will do this by counting all permutations but
    // never allowing size of a cycle = 1, and then re-normalizing the
    // probabilities.
    //
    // To solve this we can try dp[length][max_cycle_length][cnt], representing
    // the probability to have a permutation of given length that has cnt cycles
    // of max_cycle_length, and no cycles larger than max_cycle_length. This is
    // O(n^2 log n) states, because cnt * max_cycle_length <= length and the
    // harmonic sequence. The trick to avoid over-counting is to always select
    // the cycle of p[1] in the transitions.
    //
    // The transitions are O(n), so the total complexity is O(n^3 log n) which
    // is fast enough for n <= 100.

    vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(n + 1));
    for(int length = 0; length <= n; length++) {
        for(int max_cycle_length = 1; max_cycle_length <= n;
            max_cycle_length++) {
            int max_cnt = length / max_cycle_length;
            dp[length][max_cycle_length].assign(max_cnt + 1, 0);
        }
    }

    for(int i = 1; i <= n; i++) {
        dp[0][i][0] = 1;
    }

    for(int length = 1; length <= n; length++) {
        for(int max_cycle_length = 1; max_cycle_length <= n;
            max_cycle_length++) {
            int max_cnt = length / max_cycle_length;
            for(int cnt = 0; cnt <= max_cnt; cnt++) {
                // Look at cycle of p[1], and select the size.
                // There are C(length - 1, size - 1) ways to select the other
                // nodes in this cycle, and then we have (size-1)! permutations
                // that are valid. There are also length! permutations but
                // 1/(length-size)! is already present in dp[length - size].
                //
                // Therefore the transition probability will be:
                //
                //     (size - 1)! * C(length - 1, size - 1) / (length! /
                //     (length-size)!)
                //  =
                //     (size - 1)! * (length - 1)! * (length - size)! / ( (size
                //     - 1)! * (length - 1 - size + 1)! * length!)
                //  =
                //     1 / length

                for(int size = 2; size <= min(max_cycle_length, length);
                    size++) {
                    int new_cnt = size == max_cycle_length ? cnt - 1 : cnt;

                    if(new_cnt >= 0 &&
                       new_cnt <
                           (int)dp[length - size][max_cycle_length].size()) {
                        dp[length][max_cycle_length][cnt] +=
                            dp[length - size][max_cycle_length][new_cnt] /
                            length;
                    }
                }
            }
        }
    }

    // We didn't allow cycle length equal to 1.0, so we need to renormalize.
    double Z = 0;
    for(int max_cycle_length = 2; max_cycle_length <= n; max_cycle_length++) {
        int max_cnt = n / max_cycle_length;
        for(int cnt = 1; cnt <= max_cnt; cnt++) {
            Z += dp[n][max_cycle_length][cnt];
        }
    }

    double ans = 0;
    for(int max_cycle_length = 2; max_cycle_length <= n; max_cycle_length++) {
        int max_cnt = n / max_cycle_length;
        for(int cnt = 1; cnt <= max_cnt; cnt++) {
            ans += dp[n][max_cycle_length][cnt] / Z * cnt * max_cycle_length;
        }
    }

    cout << setprecision(9) << fixed << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

/*
2 3 1 -> 3             -> 3 / 2
3 1 2 -> 3             -> 3 / 2

Total = 2.5
*/
```

5. Python implementation with detailed comments

```python
import sys
def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])

    # dp[l][M][k] = probability of a derangement of size l
    # with no cycle > M, and exactly k cycles of size M
    dp = [ [ [] for _ in range(n+1) ] for __ in range(n+1) ]
    # Pre-allocate inner lists by max possible k = floor(l/M)
    for l in range(n+1):
        for M in range(1, n+1):
            maxCnt = l // M
            dp[l][M] = [0.0] * (maxCnt+1)

    # Base case: empty set has 1 way, zero cycles
    for M in range(1, n+1):
        dp[0][M][0] = 1.0

    # Build DP for lengths 1..n
    for l in range(1, n+1):
        for M in range(1, n+1):
            maxCnt = l // M
            for k in range(maxCnt+1):
                # Choose the cycle size s containing '1'
                # must be in [2..min(M,l)]
                for s in range(2, min(M, l)+1):
                    prev_k = k - (1 if s == M else 0)
                    if prev_k < 0:
                        continue
                    # We add probability mass 1/l
                    dp[l][M][k] += dp[l-s][M][prev_k] / l

    # Sum up total mass of valid derangements Z
    Z = 0.0
    for M in range(2, n+1):
        for k in range(1, n//M + 1):
            Z += dp[n][M][k]

    # Compute expected total size of largest cycles: E[k * M]
    ans = 0.0
    for M in range(2, n+1):
        for k in range(1, n//M + 1):
            prob = dp[n][M][k] / Z
            ans += prob * (k * M)

    # Print with 9 decimal places
    print(f"{ans:.9f}")

if __name__ == "__main__":
    main()
```

Explanation of major steps:
- We never allow 1-cycles, matching the problem's derangement constraint.
- The key trick is to always "grow" the DP by deciding the cycle of a distinguished element (here, element 1), so that we do not overcount permutations.
- Each choice of cycle size contributes a factor 1/l to the probability, coming from the ratio of counting cycle-choices to the total number of permutations of l elements.
- Finally, we collect the cases where the maximum cycle length is M and there are k such cycles, and accumulate k×M weighted by its probability.
