2512 重排列得到2的幂

佚名 6年前 (2019-04-15) 随笔 847人围观抢沙发百度已收录

2512 重排列得到2的幂

2 秒
262,144 KB
10 分
2 级题

小b有一个数n，现在她想把n的每一位重排列，使得得到的结果为2的幂次。

请问小b能得到2的幂次吗？

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

注意重排列后不允许有前导0。

样例解释：46重排列成64，为2^6。

收起

输入

输入一个数N，其中1≤N≤10^9

输出

满足条件，输出“true”；
不满足，则输出“false”。

输入样例

输出样例

true

#include <bits/stdc++.h>
using namespace std;
int a[10];
int b[30] = {1};
void init()
{
    for (int i = 1; i <= 29; i++)
        b[i] = b[i - 1] * 2;
}
int main()
{
    int n, l = 0;
    init();
    scanf("%d", &n);
    while (n)
    {
        a[l++] = n % 10;
        n /= 10;
    }
    sort(a, a + l);
    do
    {
        if(a[0]==0)
          continue;
        int t = 0;
        for (int i = 0; i < l - 1; i++)
        {
            t += a[i];
            t *= 10;
        }
        t += a[l - 1];
        for (int i = 0; i <= 29; i++)
        {
            if (t == b[i])
            {
                printf("true\n");
                return 0;
            }
            else if (t < b[i])
                break;
        }
    } while (next_permutation(a, a + l));
    printf("false\n");
    return 0;
}