 # Chef and Number | CodeChef

Author :- divyesh196
Tester :- divyesh196
Editorialist :- divyesh196

Difficulty :- Medium

Prerequisites :- BFS

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;
}
}``````