Chef and Number | CodeChef

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

Difficulty :- Medium

Prerequisites :- BFS

Problem :- https://www.codechef.com/WECO2020/problems/CHENUM

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