Header Ads Widget

The first overtake

Rajnish Tripathi 09:25

 Problem:-

In a car race, there are N cars 1,2 ... N where the ith car is moving with a speed of (N - i + 1). All the cars are moving in the same direction.

The current position of the cars is Xi. Determine the time at which the first overtake takes place.

Note: Overtake is defined as the place when a car crosses another car that is ahead of it.

Input format

  • Each test contains multiple test cases.
  • The first line contains the number of test cases T.
  • The first line of each test case contains two space-separated integers N and M representing the number of cars and the length of the circular path.
  • The second line of each test case contains N integers where the ith integer is Xi representing the position of the ith car on the track.

Output format

For each test case, print a single line containing one integer representing the time at which the first overtake takes place.

Constraints

1≤T≤1042≤N≤1051≤M≤1090≤Xi≤109Xi<Xi+1 for (1≤i≤N−1)It is guaranteed that the sum of N over all test cases does not exceed 2⋅105

Sample Input
1
2
1 2
Sample Output
1
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

The first overtake takes place at time t = 1.

Code:-

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    long int n;
    while(t--)
    {
        scanf("%ld",&n);
        long long int a[n],i,m=0,min=10000000007,t,j,flag=0;
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            if(flag==0)
         {
             m=a[i];
             flag=1;
            }
            else
            {
                t=abs(a[i]-m);
                if(min>t)
                min=t;
            }
            m=a[i];
        }
    /*  for(i=1;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                t=abs(a[i]-a[j]);
                if(min>t)
                min=t;
            }
        }*/
        printf("%lld\n",min);
    }
    return 0;
}



Tags: