Jan 1, 2022

Crash Code Part-1 (Single Lane Highway)

Trying to solve old coding questions, because reasons

BLZR

PersonalCode

412 Words | Reading Time: 1 Minute, 52 Seconds

01-01-2022 12:00 AM UTC

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

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

Solve

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
const int MOD = (int)(1e9 + 7);
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define T int tt; cin>>tt; while(tt--)
ll gcd(ll a,ll b){while(b){ll t=a;a=b;b=t%b;}return a;}          
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
ll modmult(ll a,ll b){ll res=0;a%=MOD;while(b){if(b&1)res=(res+a)%MOD;a=(a<<1)%MOD;b>>=1;}return res;}
ll modexpo(ll a,ll b){ll res=1;a%=MOD;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
int main()
{
    fastio;
   
     ll n,m;
    cin>>n>>m;
    ll road[n];
    for(ll i=0;i<m;i++){int a; cin>>a; road[a-1]=-1;} // -1 to denote start position of a car
    cin>>m;
    for(ll i=0;i<m;i++){int a; cin>>a; road[a-1]=-9;} // -9 to denote end position of a car

        int start=0,finish=0,max=0;
    for(ll i=0;i<n;i++)
    {  if(road[i]==-1)
    {
    int gap=(i-finish); if (gap>max && gap>1)max=gap; start=i; continue;
    }
    if(road[i]==-9)
    {
    finish=i;
    }

    }
        cout<<max-1<<endl;

     
    return 0;
}

See Also