Single Lane Highway Codevita 9 Solution

Single Lane Highway Codevita 9 Solution

Certain number of cars are passing a single lane road. Speeds of all cars vary. It is easy to see, that depending on the speeds of the cars various groups will be formed.

Being a single lane road passing/overtaking is not allowed. Given speeds of cars, calculate how many groups can be formed if all possible permutations are taken into account. Refer example1 for better understanding.

Also Read: TCS CodeVita Season 10

Print number of groups divided by the number of permutations.

Constraints

0 <= N < 10 ^ 5 

0 <= speed of individual vehicle < 10 ^ 9 

Input

First line contains an integer N, which denotes the number of vehicles

Second line contains N space separated integers which denotes the speed of individual vehicle.

Output

Print number of groups divided by the number of permutations rounded upto 6 decimal places.

Time Limit 

Example 1

Input

3

10 20 30

Output

1.833333

Explanation:

So all possible permutations are:

{10 20 30}

{10 30 20}

{20} {10 30}

{20 30} {10}

{30} {10 20}

{30 20} {10}

So here there are total 6 permutations, and total number of groups are 11.

So, output is 11/6 = 1.833333

Example 2

Input

4

56 78 13 92

Output

2.083333

Explanation:

So here there are total 24 permutations,

For example:

{56 78 13 92}

{92} {13 78 56}

{56} {13 92 78}

{78 92} {13 56}

So on and so forth. The total number of groups are 50.

So, the output is 50/24 = 2.083333″

Solution

Program Python:

from itertools import permutations
import math 
n=int(input())
l=list(map(int,input().split()))
cc=[]
s1=math.factorial(n)//math.factorial(n-(n))
s2=math.factorial(n)//math.factorial(n-(n-1))
cc.append(s1)
cc.append(s2)

if(n%2==0):
    t=sum(cc)+2
else:
    t=sum(cc)-1 
print("%.6f"%(t/cc[-1]))

Codevita Season 9 All Questions Solutions

Leave a Comment