小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
func Test6() {
testCase := [][]uint32{
{uint32(100), uint32(1000), uint32(202), uint32(2002)},
{uint32(100), uint32(1000), uint32(202), uint32(2003)},
{uint32(100), uint32(1000), uint32(203), uint32(2003)},
{uint32(101), uint32(1000), uint32(202), uint32(2002)},
{uint32(51), uint32(61), uint32(101), uint32(111)},
}
f := func(s1, s2, e1, e2 uint32) (int, []string) {
stepCounter, ret := 0, []string{}
for s1*2 <= e1 && s2*2 <= e2 {
s1, s2 = s1*2, s2*2
stepCounter, ret = stepCounter+1, append(ret, "*2")
}
if e2-s2 != e1-s1 {
return -1, nil
} else {
stepCounter = stepCounter + int(e2-s2)
for i := 0; i < int(e2-s2); i++ {
ret = append(ret, "+1")
}
}
return stepCounter, ret
}
for i := 0; i < len(testCase); i++ {
stepCounter, path := f(testCase[i][0], testCase[i][1], testCase[i][2], testCase[i][3])
if stepCounter > 0 {
fmt.Printf("%d %d -->%d %d use %d step,", testCase[i][0], testCase[i][1], testCase[i][2],
testCase[i][3], stepCounter)
for i := 0; i < len(path); i++ {
fmt.Printf("%s \t", path[i])
}
fmt.Printf("\n")
} else {
fmt.Printf("no way %d %d -->%d %d\n", testCase[i][0], testCase[i][1], testCase[i][2], testCase[i][3])
}
}
}
