首页 > 试题广场 >

数字转换机

[编程题]数字转换机

热度指数：7298 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小Q从牛博士那里获得了一个数字转换机，这台数字转换机必须同时输入两个正数a和b，并且这台数字转换机有一个红色的按钮和一个蓝色的按钮：

当按下了红色按钮，两个数字同时加1。

当按下了蓝色按钮，两个数字同时乘2。

小Q现在手中有四个整数a，b，A，B，他希望将输入的两个整数a和b变成A，B（a对应A，b对应B）。因为牛博士允许小Q使用数字转换机的时间有限，所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。

输入描述:

输入包括一行，一行中有四个正整数a，b，A，B，（1≤a，b，A，B≤10^9）。

输出描述:

如果小Q可以完成转换，输出最少需要按动按钮的次数，否则输出-1。

示例1

输入

100 1000 202 2002

输出

算法知识视频讲解

Java

秋心拆两半

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] arr = br.readLine().split(" ");
int a = Integer.parseInt(arr[0]);
int b = Integer.parseInt(arr[1]);
int A = Integer.parseInt(arr[2]);
int B = Integer.parseInt(arr[3]);
System.out.print(process(a, b, A, B));
}

public static int process(int a, int b, int A, int B){
if(a > A || b > B)
return -1;
if(a == A && b == B){
return 1;
}
int temp1 = 1 + process(a + 1, b + 1, A, B);
int temp2 = 1 + process(a * 2, b * 2, A, B);
int res = Math.min(temp1, temp2);
return res;
}
}

发表于 2019-03-08 22:56:25 回复(5)

天天201903131944503

//a+1时c比a倍数如果不变就a++，否则按第二个按钮
#include<iostream>
using namespace std;

int main()
{
    int a, b, c, d;
    while (cin >> a >> b >> c >> d)
    {
        int num = 0;
        while (a < c)
        {
            num++;
            if (c / a == c / (a + 1))
            {
                a++;
                b++;
            }
            else
            {
                a *= 2;
                b *= 2;
            }
        }
        if (b == d)
            cout << num << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

发表于 2019-04-04 10:33:24 回复(2)

仿佛我的坐骑

a,b,A,B=map(int,input().split())
count=0
if A%a!=B%b:
    print('-1')
else:
    while(A>a):
        if A%2==0 and A//2>a:
            A=A/2
            B=B/2
            if A%2!=B%2:
                break
        else:
            A=A-1
            B=B-1
        count+=1
    if b==B:
        print(count)
    else:
        print('-1')

发表于 2019-04-01 21:54:01 回复(0)

pein531

直接对A和B进行倒推，仅考虑A即可（A为偶数且1!=A/2时除以2，为奇数时减1），同时无脑让B和A一样的操作，最后如果a=A，b=B同时成立，就输出操作数，否则输出-1。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(), A = sc.nextInt(), B = sc.nextInt();
        int count = 0;
        if(a + 1 == A && b + 1 == B){
            // 防止1就是A/2的情况
            A --;
            B --;
            count ++;
        }else{
            // 倒推，如果A是偶数就除以2，否则减1
            while(A > a){
                if(A % 2 == 0){
                    A /= 2;
                    B /= 2;
                }else{
                    A --;
                    B --;
                }
                count ++;
            }
        }
        // 都还原了就输出次数，否则输出-1
        if(A == a && B == b)
            System.out.println(count);
        else
            System.out.println(-1);
    }
}

发表于 2021-02-06 00:09:31 回复(2)

myalpha

import sys

if __name__ == '__main__':
    
    a,b,A,B = list(map(int,sys.stdin.readline().strip().split(" ")))
    
    if(A < a&nbs***bsp;B < b):
        print(-1)
    else:
        count = 0 #保存最终操作次数
        flag  = 1 #判断是不是等比数列标志位
        temp = [a,b,A,B]
        
        for i in range(3): #判断是不是等比数列
            if(temp[i] * 2 !=  temp[i+1]):
                flag = 0
                break
                
        if(flag == 1): 
            while(A != a):
                A = A / 2
                count = count + 1
            print(count)
        else:
            while(a < A and b < B): #因为要尽可能少的操作，所以一上来就先做'*2'操作，即贪心
                if((a * 2 == A) and (b * 2 == B)):#如果与对应的目标值相等直接结束，否则进行'+1'操作
                    a = a * 2
                    b = b * 2
                    count = count + 1
                    break
                else:
                    count = count + 1
                    a = a + 1
                    b = b + 1
            if(a == A and b == B):#如果最终a变成为了A，b变成了B，则返回count,否则说明无法转换
                print(count)
            else:
                print(-1)

编辑于 2020-08-23 13:34:18 回复(0)

懒懒懒虫

链接：https://www.nowcoder.com/questionTerminal/e870b63e149341c8b6441bc9ebf963d6?f=discussion
来源：牛客网

假设一开始时 diff = b-a

无论有多少次加法操作，diff 都不会发生变化；只有乘法操作为让 diff = diff*2

如果可以转换成功，那么必然有 (B-A) = diff * 2 * 2 * 2 * ... * 2，即 (B-A)/(b-a) 应为2的n次幂，n即为乘法操作的次数

所以能否转换成功的判断条件应该为 log2((B-A)/(b-a))==整数，否则转换不会成功

假设 n = log2((B-A)/(b-a))，并假设每次乘法操作前有 x（x=0,1,2,3...）次加法操作，那么：

A = (...(((a + x0) * 2) + x1) * 2 + ... x_n-1) * 2 + xn

= a*2**n + x0*2**n + x1*2**(n-1) + x2*2**(n-2) + ... + x_(n-1) * 2**1 + xn

x_i 即为第 i+1 次乘法操作之前的加法操作的次数，这样共需要的操作系数就为： sum=n(乘法) + x0 + x1 + x2 + ... + xn(加法)

题目则转变为求：已知n的情况下，sum 的最小值

下面证明： x1-xn 都只能取值 (0,1)

假设某一个 xi >= 2，即 A - a*2**n = x0*2**n + x1*2**(n-1) + ... +x_(i-1) * 2**(n-i+1) + xi*2**(n-i) + ... + xn

= x0*2**n + x1*2**(n-1) + ... +( x_(i-1) + 1 ) * 2**(n-i+1) + (xi-2)*2**(n-i) + ... + xn

显然下面的情况获得的 sum 更小

因此，为使 sum 最小，需要 x1-xn 取值（0,1），然而 x0 无此限制（x1-xn构成了一个二进位的表示）

a,b,A,B =map(int, input().split())

import math

if a>A orb>B:

print(-1)

else:

num_mul =math.log((B-A)/(b-a),2) # 需要乘以2的次数

if math.pow(2,int(num_mul)) ==(B-A)/(b-a):

count =0

tmp =num_mul

while num_mul>0: # 除以2要有次数限制，可以用位操作

if A%2==0:

A =A/2

num_mul -=1

else:

A =A -1

count +=1

print(count+A-a+tmp)

else:

print(-1)

编辑于 2019-08-16 23:39:07 回复(0)

千玺家的大可爱

import sys
a,b,A,B=map(int,sys.stdin.readline().strip().split())
counta=0
countb=0
while A>=2*a:
    ca=A%2
    A=A//2
    counta+=1
    counta+=ca
resa=counta+A%a
while B>=2*b:
    cb=B%2
    B=B//2
    countb+=1
    countb+=cb
resb=countb+B%b
if resa==resb:
    print(resa)
else:
    print(-1)

编辑于 2019-03-25 20:08:03 回复(0)

Python

丶昕楚

Python Solution:

看了挺多伪算法，都是刚好只能通过试例。想了一下，这个问题没有那么简单。代码如下，没考虑到的麻烦指出。

a,b,A,B = map(int,input().split())
p,q,bp=0,0,0  for i in range(30):#30是 大致2^30次在10^9附近，反正取不到也会break，就大概就行了
    if a*2**i>A:#在除了小的数字以外，数字越大用倍数来操作操作数越少
        p=i-1#求得倍数的最大的操作次数
        break
if A-a==B-b:#避免了小的数的时候的关于倍数的判断，例如[1 2 4 5]，同样的A==a*2**p的情况也可以处理
    print(A-a)
elif A-a*2**p==B-b*2**p and A!=a*2**p:
    bp=(A-a*2**p)#计算在进行完倍数的操作数之后剩余的大小 for i in range(p):#将剩余的分配到每次倍数的操作
        if bp%(2**(p-i))>2:
            q+=bp//(2**(p-i))
            bp=bp%(2**(p-i))
        else:
            q+=bp//(2**(p-i))
            bp=bp%(2**(p-i))
            break
    print(p+q+bp)#在进行完所有的倍数操作之后多的数只能用加法解决所以直接+bp就可以了
else:
    print('-1')

编辑于 2019-03-17 10:39:56 回复(0)

向宇回桌

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a, b, A, B;
        a = sc.nextInt(); b = sc.nextInt(); A = sc.nextInt(); B = sc.nextInt();
        if ((A - B) % (a - b) != 0) { System.out.println(-1); return; };
        int p = (int)(Math.sqrt((A-B) / (a-b)));
        if (Math.pow(2, p) != (A-B) / (a-b)) {System.out.println(-1); return;};
        int ans = p;
        int remain = (int)(A - a * Math.pow(2, p));
        while (p != 0 || remain > 0) {
            ans += remain / Math.pow(2, p);
            remain -= Math.floor(remain / Math.pow(2, p)) * Math.pow(2, p);
            p--;
        }
        System.out.println(ans);
        return;
    }
}

发表于 2019-02-13 20:22:10 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int a,b,A,B;     while(cin>>a>>b>>A>>B)     {         int cnt=0,aa=2*a,bb=2*b;         bool flag = true;         while(A>=aa)         {             int d1=A%2, d2=B%2;             cnt += d1+1;             if(d1 != d2)             {                 flag = false;                 break;             }             A /= 2;             B /= 2;         }         cnt += (A-a);                 if(A-a==B-b && flag)             cout<<cnt<<endl;         else             cout<<-1<<endl;     }     return 0;
}

发表于 2019-01-22 02:32:42 回复(0)

C++

章闰水

看了几个高赞讨论，没有一个写在点子上的。最离谱的是，他们竟然都过了所有测试用例。我后来随便瞎写了一个半对不对的算法测试了一下，也过了全部用例。真是令人遗憾，牛客网的水平不行。

先说单考虑a到A的算法：

用二进制想，比如a=101，A=11101。

最终一定是a目前的3个bits对准A最高位的3个bits。所以我们第一步要把101变成111，用2次加法按钮。

接着按左移按钮一次，a=1110，A=11101。

同理，最终一定是a目前的4个bits对准A最高位的4个bits。所以我们不需要做操作。

接着按左移按钮一次，a=11100,A=11101。

此时a和A具有相同位宽，只能用加法按钮操作，再按一次加法按钮，得到a==A。

这个策略可以用反证法证明是最优的。比如假设存在下述策略最优：初始a=101，A=11101时，不做加法，先做左移。那么我们将来想让a次高位的0变成1，按加法按钮次数一定大于2。又由于对于给定a和A，按左移按钮的次数固定，为A的位宽减去a的位宽，故先位移的策略一定不是最优。

所以贪心策略总结就是：假设a的位宽为m，先用加法让a与A的前m bits相等，再位移一位，此时m=m+1，循环。

单单掌握贪心策略还不够，这个题最有意思的地方在于a*2=a+1当且仅当a=1。也就是说，a和b中有一个是1时，第一步按加法按钮和位移按钮是等价的。

这也是为什么当输入为

1 2 4 8时

1*2=2，2*2=4；

2*2=4，4*2=8；

答案为2。

当输入为

1 2 4 6时

1+1=2，2*2=4

2+1=3，3*2=6

答案也是2！

发帖人的代码没有一个能同时过这两个样例的，不信你们自己试一下。题目的judge里也少了1，2，4，6这种情况。

所以当a和b有1时，要分两支去判断，有一支能达成，就可以达成。

发表于 2021-08-03 01:31:31 回复(3)

C/C++

卷积神经网络哦

首先a和b必须一模一样的操作，所以只考虑a，然后判断b这样玩是否可行，若b不行则输出-1
贪心反着来
从大数A变成小数a

1.除以二和减一两种操作若干次后一定可以完成

2.为了尽可能快除以二的优先级大于减一

3.只有除以二不能整除或者除完小于a的情况才考虑减一

#include <iostream>
using namespace std;
int a, b, A, B;
int main(){
    scanf("%d%d%d%d", &a, &b, &A, &B);
    int res = 0;
    while(A > a){
        if(A % 2 == 0 && A / 2 > a){
            A /= 2; B /= 2;
            if(A % 2 != B % 2) break;
        }else{A--; B--;}
        res++;
    }
    if(b == B) cout<<res<<endl;
    else cout<<-1<<endl;

}

编辑于 2019-05-23 12:53:59 回复(3)

Starccode

//贪心策略
//假设按钮序列为Seq，以两个为一组考虑：
//由于是寻找最少按动次数，所以每次优先考虑蓝色按钮
//根据贪心的策略就可以初步得到Seq，并且该Seq前面为蓝色按钮，后面为红色按钮
//但实际序列是可以进一步优化的：
//A*2 + 2 = （A+1）*2 由3步减少为2步 -> 蓝红红变为红蓝
//A*2 + 4 = (A+2)*2 由5步减少为3步
//....

//优化的思路就是：其实蓝色按钮数目是不会改变的，可优化的就是红色按钮数目

//每次优化就是把偶数个红按钮除以2放到蓝按钮前面，再跟前面的进行合并优化

//如果红按钮数目为奇数，就留下一个在蓝按钮后面，其余的都放到前面去。可优化的次数最大为蓝按钮个数

//用时5ms

int main() {
int a, b, A, B;
cin >> a >> b >> A >> B;
int blue = 0, red = 0;
//统计最多可以按多少次蓝扭
while(a < A && b < B) {
if(a * 2 <= A && b * 2 <= B) {
blue++;
a *= 2;
b *= 2;
}
}
//统计最多可以按多少次红扭
if((A - a) != (B - b)) {
cout << -1 << endl;
return 0;
} else {
red = A - a;
}
//优化序列
int ret = blue;
int optimize = 0; //可优化的次数
while(red > 1 && optimize <= blue) {
if(red & 1) ret++;
red /= 2;
optimize++;
}
ret += red;
cout << ret << endl;
return 0;
}

发表于 2019-05-23 11:42:30 回复(0)

可乐鸡块

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int a = Integer.parseInt(arr[0]);
        int b = Integer.parseInt(arr[1]);
        int A = Integer.parseInt(arr[2]);
        int B = Integer.parseInt(arr[3]);
        System.out.print(process(a, b, A, B));
    }
    
    private static int process(int a, int b, int A, int B) {  // 从a, b到A, B的次数
        if (a == A && b == B) return 0;
        if (a == A && b != B) return -1;
        if (a != A && b == B) return -1;
        if (a > A || b > B) return -1;
        if (A % 2 == 0 && B % 2 == 0) {
            int red = process(a, b, A - 1, B - 1);  // 上一次红色按钮
            int blue = process(a, b, A / 2, B / 2); // 上一次蓝色按钮
            if (red == -1 && blue == -1) return -1;
            else if (red == -1) return blue + 1;
            else if (blue == -1) return red + 1;
            else return Math.min(red, blue) + 1;
        } else {
            int red = process(a, b, A - 1, B - 1);
            if (red == -1) return -1;
            else return red + 1;
        }
    }
}

发表于 2019-02-27 10:50:37 回复(1)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,A,B,res=0;
    cin>>a>>b>>A>>B;
    while(A>a)
    {
        if(A/2>a&&A%2==0)
        {
            A=A/2;
            B=B/2;
            if(A%2!=B%2)
                break;
        }
        else
        {
            A=A-1;
            B=B-1;
        }
        res++;
    }
    if(b==B)
        cout<<res<<endl;
    else 
        cout<<-1<<endl;
    return 0;
}

发表于 2019-06-27 10:20:19 回复(0)

一目了然

#include <iostream>
using namespace std;

int main(){
    int a,b,A,B;
    scanf("%d%d%d%d", &a, &b, &A, &B);
    int bitLenA=0, bitLena=0;
    while(A>>bitLenA){
        bitLenA++;
        if(a>>bitLena)
            bitLena++;
    }
    int result = 0, delta = bitLenA-bitLena;
    while(true){
        if(A>>delta ^ a){
            int addNum = (A>>delta) - a;
            a+= addNum;
            b+= addNum;
            result+= addNum;  //按几次红按钮（实际上只有第一次需要按多次红按钮，之后只会按一次）
        }
        if(!delta)
            break;
        delta--;
        a = a*2;
        b = b*2;
        result++;  //按蓝按钮后，a和A的比特串长度减一
    }
    if(b==B && a==A)
        printf("%d", result);
    else
        printf("%d", -1);
    return 0;
}

实际上这道题用位操作来做的话，可以省掉很多时间。第一步是计算a和A比特串长度差，那么*2操作就是向左移一位。通过这种方法可以很快将a转成A。只要验证b和B是否相等就行。

编辑于 2019-04-05 18:36:00 回复(0)

DD1a

public class Program {

public static void Main() {

string line;

while ((line = System.Console.ReadLine ()) !=

null) { // 注意 while 处理多个 case

string[] tokens = line.Split(" ");

int a = int.Parse(tokens[0]);

int b = int.Parse(tokens[1]);

int A = int.Parse(tokens[2]);

int B = int.Parse(tokens[3]);

string S1 = "";

string S2 = "";

int x = 0; //红色按钮的次数

int y = 0; //蓝色按钮的次数

int z1 = 10000; //第一种按钮次数和

int z2 = 10000; //第二种按钮次数和

int z3 = 10000; //第三种按钮次数和

int z4 = 10000; //第四种按钮次数和

int z5 = 10000; //第五种按钮次数和

//第一种 (a+x)*2y=A

x = (A * b - B * a) / (B - A);

y = A / (a + x) / 2;

if ((b + x) * 2 * y == B)

z1 = x + y;

//第二种 2ay+x=A

y = (B - A) / 2 / (b - a);

x = A - (2 * a * y);

if (2 * b * y + x == B )

z2 = x + y;

//第三种 x+a=A

x = A - a;

if (b + x == B)

z3 = x;

//第四种 2ay=A

y = A / 2 / a;

if (2 * b * y == B && A % a == 0)

z4 = y;

//第五种 (a+x)*2y+i=A

if((A-B)%(2*(a-b))==0)

{

y = (A - B) / 2 / (a - b) ;

for (int i = 0; i <= A - (2 * y * a); i++) {

if ((A - 2 * y * a - i) % (2 * y) == 0) {

x = (A - 2 * y * a - i) / 2 / y;

if ((b + x) * 2 * y + i == B)

z5 = x + i + y ;

break;

}

int z = -1; //最后输出

int temp = System.Math.Min(z1, z2);

int temp1 = System.Math.Min(temp, z3);

int temp2 = System.Math.Min(temp1, z4);

z = System.Math.Min(temp2, z5);

if(z!=10000)

System.Console.WriteLine(z);

else

System.Console.WriteLine(-1);

}

发表于 2023-01-03 10:22:52 回复(0)

5827686397

直接简单的线性计算不香么。。。

const arr = readline().split(" ").map((item) => +item);
const [a,b,A,B] = arr;
let k = Math.floor((B-A)/(b-a));
let p = A - k*a;
let c = B - k*b;
if(p !== c) print(-1)
else{
let res = 0;
res += (p % k) + Math.floor(p/k);
res += Math.log2(k);
print(res)
}

发表于 2022-05-24 14:20:29 回复(0)

Y2580

#include<bits/stdc++.h>
using namespace std;
int res = -1;
void dfs(int a, int b, int A, int B, int n)
{
    if(a > A || b > B)
        return;
    
    if(a == A && b == B)
    {
        if(res == -1)
            res = n;
        else
            res = min(res, n);
        
        return;
    }
    
    dfs(a * 2, b * 2, A, B, n + 1);
    dfs(a + 1, b + 1, A, B, n + 1);
}

int main()
{
    int a, b, A, B;
    cin >> a >> b >> A >> B;

    dfs(a, b, A, B, 0);
    
    cout << res << endl;
}

直接深度优先遍历所有情况

发表于 2022-05-14 22:13:53 回复(0)

Java

勤奋努力的海螺喜欢摸鱼

通过|B-A|和|b-a|的差值求余进行判断能否存在路径，通过计算|B-A|和|b-a|的差值以2为底的对数取得翻倍次数，通过翻倍次数计算余数取得的最少次数

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong();
        long b = in.nextLong();
        long A = in.nextLong();
        long B = in.nextLong();
        int ans = 0;
        if (Math.abs(B - A) % Math.abs(b - a) == 0) {
            int mulCounter = (int) (Math.log(Math.abs(B - A) / Math.abs(b - a)) / Math.log(2));
            int mulVal = (int) Math.pow(2, mulCounter);
            int addCounter = 0;
            ans += mulCounter;
            A -= mulVal * a;
            //计算余数取得的最少次数，同*2次数相关
            while (A != 0) {
                addCounter += A / mulVal;
                A %= mulVal;
                mulVal /= 2;
            }
            ans += addCounter;
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }
        in.close();
    }
}

发表于 2021-10-21 09:59:45 回复(0)