Acwing 4300. Two operations

Given a positive integer n, We hope you can through a series of operations , Change it to another positive integer m.

There are two kinds of operations ：

1. Multiply the current number by 2

2. Subtract... From the current number 1

requirement , During the transformation , The number is always positive .

Please calculate , The minimum number of operations required .

Input format ：

a line , Two different positive integers n and m.

Output format ：

An integer , Indicates the minimum number of operations required .

Data range ：

front 6 Test points meet 1≤n,m≤10.
All test points meet 1≤n,m≤10000.

sample input 1：

4 6

sample output 1：

2

sample input 2：

10 1

sample output 2：

9

1. greedy

prove ： When n>m when , And m For even when , be /2.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
typedef pair<int,int> PII; 
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
const int mod=1e9+7;
int n,m;
int cnt;
int main()
{
    cin>>n>>m;
    if(n>=m) cout<<n-m<<endl;
    else                      // Back to 
    {
        while(n<m)       //n>=m  It can be converted to the first two cases 
       {
           if(m&1) m++;   // If m It's odd , Can not /2,n*2 The number changed must be even .
           else m/=2;     //  An even number is ok /2.
           cnt++;  
       }
       cout<<cnt+n-m<<endl;  // Switch to the first two cases 
    }
   


   return 0;
}

2. Search for Wide search

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20100;
typedef pair<int,int> PII; 
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
const int mod=1e9+7;
int n,m;
int d[N],q[N];

int main()
{
    cin>>n>>m;
    int hh=0,tt=0;
    memset(d,0x3f,sizeof d); // Initial array , Easy to update 
    d[n]=0;   //  Starting from 0.
    q[0]=n;    // The starting point joins the queue .
    while(hh<=tt)
    {
        int t=q[hh++];      
        int change[]={t-1,t*2}; // Use an array to represent two operations , Convenient operation 
        for(auto i:change)
        {
            if(i>=1&i<N&&d[i]>d[t]+1) // 2*n<2*m  Maximum enumeration to 2e4
            {
                d[i]=d[t]+1;           // If the conditions are met, it will be updated 
                q[++tt]=i;            // Join the queue 

            }
        }
    }
    cout<<d[m]<<endl;
   


   return 0;
}