腾讯2018校招软件开发在线笔试-编程题二

发表于 | 分类于 ，

题目

描述

有两个数 a,b 只能进行以下操作
* +1
* *2
现有 a,b,A,B 四个数,对 a,b 同时进行以上同样的操作,求最少多少步可以 a 变为 A,b 变为 B
若不行则输出 -1

输入

1 行 4 个数 a,b,A,B

输出

最少步数

Example

Input

Output

题解

深度优先搜索

  • 当 A 小于 a 或 B 小于 b,不可达
  • 当 A 为偶数,可由 A/2 或 A-1 得到,A 为奇数,只能由 A-1 得到
  • 对于其中 A,B 中只要有一个奇数,则只由 A-1,B-1 得到
  • 优先搜索 *2 的情况,再搜索 +1 情况,若是搜索不到输出-1
1
2