Author :- divyesh196
Tester :- divyesh196
Editorialist :- divyesh196
Difficulty :- Medium
Prerequisites :- BFS
Problem :- CodeChef: Practical coding for everyone
Solution
Use BFS , as start from current state x, and move to 3 levels x-1,x+1,x/y and
increase level as level+1. When x==1, print level.
Time Complexity :- O(V+E)
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define pb push_back
using namespace std;
ll i,j;
struct cell
{
ll x,y;
};
typedef pair<ll,ll>p;
ll solve(ll x, ll y)
{
set
s;
s.clear();
queue<cell>q; // Store current state and level
q.push({x,0}); // Push initial state and level=0
s.insert(mk(x,0));
cell pick; // pick variable of type struct
while(!q.empty())
{
pick = q.front();
q.pop();
if(pick.x==1) // if current state == destination state
return pick.y; // print level
p k1 = mk(pick.x-1,pick.y+1);
if(s.find(k1)==s.end())
{
q.push({pick.x-1,pick.y+1}); // push current_state-1,current_level+1
}
p k2 = mk(pick.x+1,pick.y+1);
if(s.find(k2)==s.end())
{
q.push({pick.x+1, pick.y+1}); // push current_state+1, current_level+1
}
if(pick.x % y==0)
{
p k3 = mk(pick.x/y,pick.y+1);
if(s.find(k3)==s.end())
{
q.push({pick.x/y, pick.y+1}); // push current_state/y, current_level+1
}
}
}
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll x,y;
cin>>x>>y;
cout<<solve(x,y)<<endl;
}
}