题解 | 小招喵跑步

import sys
import math

def times_divisible_by_two(n):
    """n > 1"""
    assert n > 1
    cnt2 = 0
    while n > 1:
        if n % 2 == 0:
            n = n / 2; cnt2 +=1
        else:
            break
    if n == 1:if_one = True
    else: if_one = False
    return cnt2, if_one

for line in sys.stdin:
    a = line.split()[0]
a = int(a)
cnt = 0
if a == 0:
    print(0)
elif a == 1:
    print(1)
elif a == 2:
    print(2)
else:
    a = math.sqrt(a ** 2)
    while a !=1:
        cnt +=1
        if a % 2 == 0:
            a = a / 2
            continue
        else:
            cnt_1, if_one_1 = times_divisible_by_two(a-1)
            cnt_2, if_one_2 = times_divisible_by_two(a+1)
            if if_one_1 == 1:
                a = a-1
                continue
            elif cnt_1 < cnt_2:
                a = a + 1
                continue
            else:
                a = a -1
                continue
    cnt += 1
    print(cnt)