题目描述

You are given an integer $n$ . In $1$ move, you can do one of the following actions:

  • erase any digit of the number (it's acceptable that the number before the operation has exactly one digit and after the operation, it is "empty");
  • add one digit to the right.

The actions may be performed in any order any number of times.

Note that if, after deleting some digit from a number, it will contain leading zeroes, they will not be deleted. E.g. if you delete from the number $301$ the digit $3$ , the result is the number $01$ (not $1$ ).

You need to perform the minimum number of actions to make the number any power of $2$ (i.e. there's an integer $k$ ( $k \ge 0$ ) such that the resulting number is equal to $2^k$ ). The resulting number must not have leading zeroes.

E.g. consider $n=1052$ . The answer is equal to $2$ . First, let's add to the right one digit $4$ (the result will be $10524$ ). Then let's erase the digit $5$ , so the result will be $1024$ which is a power of $2$ .

E.g. consider $n=8888$ . The answer is equal to $3$ . Let's erase any of the digits $8$ three times. The result will be $8$ which is a power of $2$ .

输入格式

The first line contains one integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing one integer $n$ ( $1 \le n \le 10^9$ ).

输出格式

For each test case, output in a separate line one integer $m$ — the minimum number of moves to transform the number into any power of $2$ .

输入输出样例

输入 #1

12
1052
8888
6
75
128
1
301
12048
1504
6656
1000000000
687194767

输出 #1

2
3
1
3
0
0
2
1
3
4
9
2

分析

对数字的操作实质上就是对字符串中的字符的增删操作,所以我们就很容易地把问题转化成了对一个字符串进行增删操作,至少操作多少次能使它变成 $2$ 的次幂的字符串形式。

于是我们考虑计算原始串和目标串的“差异”(长度-最长前缀的长度),然后更新答案。需要注意的是 $2$ 的次幂的表不止需要打 $k(2^{k-1}\lt 10^9\lt 2^k)$ 大小,因为显然字符串之间的“差异”和数字之间的“差异”并不是同种概念。

时间复杂度 $O(1)$。

代码

#include<bits/stdc++.h>
using namespace std;
int ans;
char a[51];
char str[101][51]={"1","2","4","8","16","32","64","128","256","512","1024","2048","4096","8192","16384","32768","65536","131072","262144","524288","1048576","2097152","4194304","8388608","16777216","33554432","67108864","134217728","268435456","536870912","1073741824","2147483648","4294967296","8589934592","17179869184","34359738368","68719476736","137438953472","274877906944","549755813888","1099511627776","2199023255552","4398046511104","8796093022208","17592186044416","35184372088832","70368744177664","140737488355328","281474976710656","562949953421312","1125899906842624","2251799813685248","4503599627370496","9007199254740992","18014398509481984","36028797018963968","72057594037927936","144115188075855872","288230376151711744","576460752303423488","1152921504606846976","2305843009213693952","4611686018427387904"};
inline int work(int x){
    int sum=0;
    int n=strlen(a),m=strlen(str[x]);
    for(int i=0;i<n;i++){
        if(a[i]==str[x][sum])sum++;
    }
    ans=min(ans,n+m-2*sum);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>a;ans=0x3f3f3f3f;
        for(int i=0;i<=62;i++){
            work(i);
        }
        printf("%d\n",ans);
    }
}
最后修改:2021 年 08 月 22 日 12 : 49 PM
如果觉得我的文章对你有用,请随意赞赏