Header Ad

HackerEarth The Circular jump (Lowe) problem solution

In this HackerEarth The Circular jump (Lowe) problem solution There are N chairs arranged around a circular table. Each chair has a number Num(i) written on it. Any person sitting on a chair i can jump Num(i) number of indices towards left or right, You are sitting on chair X and you have to reach chair Y. Tell the minimum number of jumps required by you. If its impossible to reach then print 1.

Example :- If your sitting on chair 4 and it has number 2 written on it then you can either jump to chair number 2 or chair number 6.


HackerEarth The Circular jump (Lowe) problem solution


HackerEarth The Circular jump (Lowe) problem solution.

#include <bits/stdc++.h>
#define sflld(n) scanf("%lld",&n)
#define sfulld(n) scanf("%llu",&n)
#define sfd(n) scanf("%d",&n)
#define sfld(n) scanf("%ld",&n)
#define sfs(n) scanf("%s",&n)
#define ll long long
#define s(t) int t; while(t--)
#define ull unsigned long long int
#define pflld(n) printf("%lld\n",n)
#define pfd(n) printf("%d\n",n)
#define pfld(n) printf("%ld\n",n)
#define lt 2*idx
#define rt 2*idx+1
#define f(i,k,n) for(i=k;i<n;i++)
#define MAXN 0
#define FD freopen("out.txt", "w", stdout);
#define FC fclose(stdout);
#define P pair<int,int>
using namespace std;

int vis[100005],arr[100005];
queue<pair<int,int> >q;
int main()
{
int t;
sfd(t);
while(t--)
{
int n,i,st,de;
sfd(n);
sfd(st);
sfd(de);
st--;
de--;
memset(vis,0,sizeof(vis));
while(!q.empty())
q.pop();
f(i,0,n)
{
sfd(arr[i]);
arr[i]%=n;
}
vis[st]=1;
q.push(make_pair(st,0));
int ans=-1;
while(!q.empty())
{
P temp=q.front();
q.pop();

if(temp.first==de)
{
ans=temp.second;
break;
}
int nextb=(temp.first-arr[temp.first]+n)%n;
int nextf=(temp.first+arr[temp.first])%n;

if(!vis[nextb])
{
vis[nextb]=1;
q.push(make_pair(nextb,temp.second+1));
}
if(!vis[nextf])
{
vis[nextf]=1;
q.push(make_pair(nextf,temp.second+1));
}
}
pfd(ans);
}
return 0;
}

Post a Comment

0 Comments