Codeforces 1362A - Johnny and An

日常一道算法题。

翻译

Johnny 和老电脑

Johnny 最近发现了一个老旧电脑。这个机器只有一个寄存器，一次只允许放入一个变量。一次操作只能左移或者右移最多三位。并且，右移禁止切断任何1。所以，事实上，一次操作你可以将它乘以2，4 或 8，如果它能被 2，4，8 整除，那么可以除以 2，4 或 8。

• x * 2
• x * 4
• x * 8
• x / 2，如果 x 可以被 2 整除
• x / 4，如果 x 可以被 4 整除
• x / 8，如果 x 可以被 8 整除

现在 Johnny 有个疑问，他输入数字 a 能否通过一些操作得到 b。

输入格式

输入整数 t 表示测试用例组数。

每组测试用例，输入 a 和 b，用空格分隔。

输出格式

输出最少的操作步数，如果不能得到 b，那么输出 -1。

分析

一道水题花费我了三个小时，脑子一抽就用了除法，我要是再乱用除法我就。。。

判断 a 和 b 的大小，交换 a b 位置，使 a 小于等于 b，因为题目中右移操作不能截断 1，所以无论大小都是可逆的操作。也就是可以用乘法的方式替代除法。

判断 a 和 b 相等，则直接输出 0 即可。

如果 a 小于 b ，则持续让 a 乘以 2， 直到 a 大于等于 b。再判断 a 和 b 是否相等，如果相等则输出 int(result / 3) + (1 if result % 3 > 0 else 0) ，否则输出 -1

总结经验，Python 对于整数除法也是浮点数的结果，导致当数字偏大时，浮点数精度不够，这也是卡主我的原因。

代码(Python 3)

# https://codeforces.com/problemset/problem/1362/A
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
t = int(input())
 
def printd(value):
    # print(value)
    pass
 
def case():
    arr = list(map(int, input().split(" ")))
    a, b = arr[0], arr[1]
    
    if a == b:
        print(0)
        return
 
    if a > b:
        b, a = a, b
 
    result = 0
    while a < b:
        a *= 2
        result += 1
 
    if a == b:
        print(int(result / 3) + (1 if result % 3 > 0 else 0))
        return
        
    print(-1)
 
for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.08 长春