Soluție HackerRank pentru Lazy Sorting, subdomeniul Probability, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Lazy Sorting
  • Domeniu: Probability
  • Limbaj: Python 3

Challenge: Lazy Sorting

Subdomeniu: Probability (probability)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464726194

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/lazy-sorting/problem

Cerință

Logan is cleaning his apartment. In particular, he must sort his old favorite sequence, P, of N positive integers in nondecreasing order. He's tired from a long day, so he invented an easy way (in his opinion) to do this job. His algorithm can be described by the following pseudocode:

while isNotSorted(P) do {
WaitOneMinute();
RandomShuffle(P)
}

Can you determine the expected number of minutes that Logan will spend waiting for P to be sorted?

Input Format

The first line contains a single integer, N, denoting the size of permutation P.
The second line contains N space-separated integers describing the respective elements in the sequence's current order, P_0, P_1, …, P_N-1.

Output Format

Print the expected number of minutes Logan must wait for P to be sorted, correct to 6 decimal places.

Constraints

- 2 ≤ N ≤ 18
- 1 ≤ P_i ≤ 100

Cod sursă

#!/bin/python3

import math
import os
import random
import re
import sys

def solve(P):

    if P == sorted(P):
        return 0
        
    counts = [P.count(i) for i in list(set(P))]
    n_perm_w_repetitions = int(math.factorial(len(P))/math.factorial(counts[0]))
    for c in counts[1:]:
        n_perm_w_repetitions = int(n_perm_w_repetitions/math.factorial(c))
    ev = n_perm_w_repetitions
    return "%.6f" % round(ev)
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    P_count = int(input().strip())

    P = list(map(int, input().rstrip().split()))

    result = solve(P)

    fptr.write(str(result) + '\n')

    fptr.close()
HackerRank Probability – Lazy Sorting