<|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;

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

    int n;
    cin >> n;

    // dp[l][M][k]: probability that a derangement of size l
    // has no cycle > M, and exactly k cycles of length M.
    // We forbid cycles of length 1.
    vector<vector<vector<double>>> dp(
        n+1,
        vector<vector<double>>(n+1)
    );
    // Pre-allocate the k dimension: k can go up to floor(l/M).
    for(int l = 0; l <= n; ++l){
        for(int M = 1; M <= n; ++M){
            int maxK = l / M;
            dp[l][M].assign(maxK+1, 0.0);
        }
    }

    // Base case: empty permutation has zero cycles of any size.
    for(int M = 1; M <= n; ++M){
        dp[0][M][0] = 1.0;
    }

    // Build DP for l = 1..n
    for(int l = 1; l <= n; ++l){
        for(int M = 1; M <= n; ++M){
            int maxK = l / M;
            for(int k = 0; k <= maxK; ++k){
                // Choose the size s of the cycle containing element 1
                // s ranges from 2 to min(M, l).  Each choice contributes 1/l.
                for(int s = 2; s <= min(M, l); ++s){
                    int prevK = k - (s == M ? 1 : 0);
                    if(prevK < 0) continue;
                    // dp[l-s][M][prevK] must exist
                    dp[l][M][k] += dp[l-s][M][prevK] / double(l);
                }
            }
        }
    }

    // Compute expected total size of largest cycles: E[k * M].
    // In exact arithmetic Z = 1, but we accumulate it to guard against rounding.
    double Z = 0.0;
    double answer = 0.0;
    for(int M = 2; M <= n; ++M){
        int maxK = n / M;
        for(int k = 1; k <= maxK; ++k){
            double prob = dp[n][M][k];
            Z += prob;
            answer += prob * (k * M);
        }
    }

    // If Z deviates from 1 due to roundoff, renormalize.
    answer /= Z;

    cout << fixed << setprecision(9) << answer << "\n";
    return 0;
}
```

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 that a derangement of size l
    # has no cycle longer than M, and exactly k cycles of length M.
    dp = [
        [None] * (n+1)
        for _ in range(n+1)
    ]
    # Pre-allocate k dimension for each (l, M)
    for l in range(n+1):
        for M in range(1, n+1):
            max_k = l // M
            dp[l][M] = [0.0] * (max_k + 1)

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

    # Fill DP for l = 1..n
    for l in range(1, n+1):
        for M in range(1, n+1):
            max_k = l // M
            for k in range(max_k+1):
                # Cycle containing element 1 has size s 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
                    dp[l][M][k] += dp[l-s][M][prev_k] / l

    # Sum probabilities and weighted contributions
    Z = 0.0
    answer = 0.0
    for M in range(2, n+1):
        for k in range(1, n//M + 1):
            p = dp[n][M][k]
            Z += p
            answer += p * (k * M)

    # Renormalize if needed and print
    answer /= Z
    print(f"{answer:.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.