CF1560D Make a Power of Two

发表于 分类于

思路

根据题目所给操作倒推可得，最优情况下，应保留所给数$n$中所包含$2^k$的前缀（不一定连续），并在末尾补充剩余的数。且答案最大为$n$的位数$+1$（全部删除后补$1/2/4/8$）。

由此在$0\sim 63$之间枚举$k$并取最小值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
_t=int(input())
for _c in range(_t):
    n=int(input())
    _n=str(n)
    lenn=len(_n)
    ans=lenn+1
    for i in range(64):
        num=1<<i
        _num=str(num)
        lennum=len(_num)
        _ans=lenn+lennum
        k,j=0,0
        while k<lenn and j<lennum:
            tmp=_n[k:].find(_num[j])
            if tmp==-1:
                break
            k+=tmp+1
            _ans-=2
            j+=1
        ans=min(ans,_ans)
    print(ans)