• + 1 comment

    To determine the expected number of minutes Logan will spend waiting for the sequence to be sorted, we can analyze the calm probability of the sequence being sorted after each minute.

    Let's assume the size of the permutation is N.

    The probability of the sequence being sorted after the first minute is 1/N!. This is because there are N! possible permutations, and only one of them is sorted.

    Similarly, the probability of the sequence being sorted after the second minute is (N-1)/N!. This is because after the first minute, there are (N-1)! possible permutations remaining, and only one of them is sorted.

    Following this pattern, the probability of the sequence being sorted after the kth minute is (N-k+1)/N!.

    To calculate the expected number of minutes, we need to sum up the probabilities for all possible minutes until the sequence is sorted.

    The expected number of minutes can be calculated as:

    E = 1/N! + 2/N! + 3/N! + ... + M/N!

    To simplify the calculation, we can express the sum in a different form:

    E = (1 + 2 + 3 + ... + M) / N!

    The sum of consecutive integers from 1 to M can be calculated using the formula (M * (M + 1)) / 2.

    Therefore, the expected number of minutes can be calculated as:

    E = (M * (M + 1)) / (2 * N!)

    Now, let's implement this logic in Python:

    import math
    
    def expected_minutes(N, sequence):
        factorial = math.factorial(N)
        M = 0  # Number of minutes spent waiting
        probability_sum = 0  # Sum of probabilities
        
        while not sorted(sequence):
            M += 1
            probability_sum += M / factorial
            random_shuffle(sequence)
        
        return probability_sum
    
    def sorted(sequence):
        return all(sequence[i] <= sequence[i+1] for i in range(len(sequence)-1))
    
    def random_shuffle(sequence):
        random.shuffle(sequence)
    
    # Read input
    N = int(input())
    sequence = list(map(int, input().split()))
    
    # Calculate expected number of minutes
    expected = expected_minutes(N, sequence)
    
    # Print the result with 6 decimal places
    print(f"{expected:.6f}")