小Q从牛博士那里获得了一个数字转换机,这台数字转换机必须同时输入两个正数a和b,并且这台数字转换机有一个红色的按钮和一个蓝色的按钮:
当按下了红色按钮,两个数字同时加1。
当按下了蓝色按钮,两个数字同时乘2。
小Q现在手中有四个整数a,b,A,B,他希望将输入的两个整数a和b变成A,B(a对应A,b对应B)。因为牛博士允许小Q使用数字转换机的时间有限,所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。
小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。
100 1000 202 2002
2
我笑了,本来只想看看它有没有ab大于AB的测试用例,结果直接通过??? import java.util.*; public class Main { private static long count = 0; 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(); if (a > A || b > B) System.out.println(-1); } }
//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; }
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); } }
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)
#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是否相等就行。
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')
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; } }
#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; }
首先a和b必须一模一样的操作,所以只考虑a, 然后判断b这样玩是否可行, 若b不行则输出-1
贪心反着来
从大数A变成小数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; }
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; } } }
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) }
#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; }直接深度优先遍历所有情况
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(); } }