首页 > 试题广场 > 数位重排
[编程题]数位重排
  • 热度指数:51 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
牛牛有一个正整数x,牛牛需要把数字x中的数位进行重排得到一个新数(不同于x的数),牛牛想知道这个新数是否可能是原x的倍数。请你来帮他解决这个问题。

输入描述:
输入包括t+1行,第一行包括一个整数t(1 ≤ t ≤ 10),
接下来t行,每行一个整数x(1 ≤ x ≤ 10^6)


输出描述:
对于每个x,如果可能重排之后变为自己的倍数输出"Possible", 否则输出"Impossible".
示例1

输入

2
14
1035

输出

Impossible
Possible
#include<string>
#include<iostream>
#include <algorithm>
int main()
{
    using std::cin;
    using std::cout;
    using std::endl;
    using std::sort;
    int t;
    cin>>t;
    int* ptr= new int[t];
    int* result= new int[t];
    for(int i =0 ; i<t ; i++)
    {
        cin>>ptr[i];
        result[i]=0;
    }
    int a[6];
    int b[6];
    for(int i=0; i<t ;i++)
    {
        int degree = 0;
        a[5] = ptr[i]/100000;
        a[4] = ptr[i]%100000/10000;
        a[3] = ptr[i]%10000/1000;
        a[2] = ptr[i]%1000/100;
        a[1] = ptr[i]%100/10;
        a[0] = ptr[i]%10;
        if(a[1]>0)
            degree = 100/ptr[i];
        if(a[2]>0)
            degree = 1000/ptr[i];
        if(a[3]>0)
            degree = 10000/ptr[i];
        if(a[4]>0)
            degree = 100000/ptr[i];
        if(a[5]>0)
            degree = 1000000/ptr[i];
        if(degree<2)
        {
            result[i] = 0;
            continue;
        }
        bool IS = false;
        for(int j=2;j<=degree;j++)
        {
            b[5] = j*ptr[i]/100000;
            b[4] = j*ptr[i]%100000/10000;
            b[3] = j*ptr[i]%10000/1000;
            b[2] = j*ptr[i]%1000/100;
            b[1] = j*ptr[i]%100/10;
            b[0] = j*ptr[i]%10;
            sort(b,b+6);
            sort(a,a+6);
            int k;
            for(k=0;k<6;k++)
            {
                if(a[k]!=b[k])
                {
                    break;
                }
            }
            if(k!=6)
                continue;
            else
            {
                IS = true;
                break;
            }
        }
        if(IS)
        {
           result[i] = 1;
        }
        else
        {
           result[i] = 0;
        }
    }

    for(int i=0; i<t;i++)
    {
        if(result[i] == 1)
            cout<<"Possible\n";
        else
            cout<<"Impossible\n";
    }
    delete []ptr;
    delete []result;
    return 0;
}
发表于 2019-08-02 20:14:13 回复(0)