Type Here to Get Search Results !

Single Lane Highway | TCS Codevita 9 Solution Zone 2 2020 | CodingHumans

CodingHumans 15 August 1
Single Lane Highway

 Problem Description

 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.

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

 1

Examples

 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:
( Python )

from itertools import permutations
import math 
# def get_count(d):

#     c=0

#     for i in d:

#     c+=1 

#     return c 

n=int(input())

l=list(map(int,input().split()))

cc=[]

# d1=permutations(l,n-1)

# d2=permutations(l,n)

# cc.append(get_count(d1))

# cc.append(get_count(d2))

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]))

If any queries You can mail to codinghumanshelp@gmail.com or comment down below
Tags

You May Like

Post a Comment

1 Comments

* Please Don't Spam Here. All the Comments are Reviewed by Admin.

Top Post Ad

Below Post Ad