In this HackerEarth The Perfect Road problem solution we have given that, there are N paths numbered from 1 to N, where each path connects the starting point S to the destination point X. The maximum speed limit is speed[i] for the ith path which can be used to reach the destination. Find the path to reach the destination as early as possible. If there are multiple paths from which you can choose, print Many Roads. Also, it is guaranteed that X will always be greater than S.


HackerEarth The Perfect Road problem solution


HackerEarth The Perfect Road problem solution.

#include<iostream>
#include<algorithm>
#include<functional>
#include<utility>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#define MAX LONG_LONG_MAX
#define MIN LONG_LONG_MIN
#define ll long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define INF 1e17
using namespace std;
const int mod=1e+7;
int FindPerfectRoad(int Startpoint,int X,vector<int> s)
{
    double res=999999.000;
    vector<double> ans;
    int answer=0,counter=0,Diff=(X-Startpoint);
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        double TimeReq=(Diff/(double)s[i]);
        ans.push_back(TimeReq);
        if(TimeReq<res)
        {
            res=TimeReq;
            answer=i+1;
        }
    }
    for(int i=0;i<n;i++)
        if(ans[i]==res)
            counter++;
    if(counter==1)
        return answer;
    else
        return -1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,StartPoint,X;
        cin>>StartPoint>>X>>n;
        vector<int> s;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            s.push_back(temp);
        }
        int ans=FindPerfectRoad(StartPoint,X,s);
        if(ans==-1)
            cout<<"Many Roads"<<endl;
        else
            cout<<ans<<endl;
    }
return 0;
}