首页 > 试题广场 >

数位重排

[编程题]数位重排
  • 热度指数:74 时间限制: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
importjava.util.ArrayList;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Scanner;
 
publicclassMain {
    staticboolean[] ksksksk= newboolean[100];
    publicstaticvoidisOK(inta,intindex, int[] param, intstart) {
 
        if(start == param.length) {
            //达到了
            inti = 0;
            intk = 1;
            for(ints = param.length-1; s >= 0; s--) {
                i += k * param[s];
                k *= 10;
            }
            if(i%a==0&& i!=a){//符合要求
                ksksksk[index] = true;
            }
        } else{
            for(inti = start; i < param.length; i++) {
                Swap(param, i, start);
                isOK(a,index, param, start + 1);
                Swap(param, start,i);
            }
        }
    }
 
    publicstaticvoidSwap(int[] a, inti, intj) {
        inttemp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
 
 
    publicstaticvoidnumSlice(inta,intindex) {
        int[] nums = newint[10];
        intcount = 0;
        inttemp = a;
        while(temp > 0) {
            nums[count++] = temp % 10;
            temp /= 10;
        }
        int[] new1 = newint[count];
        for(inti = 0;i<count;i++){
            new1[i] = nums[i];
        }
        isOK(a,index, new1, 0);
    }
 
    publicstaticvoidmain(String[] args) {
        Scanner sin = newScanner(System.in);
        intlen= sin.nextInt();
        intcounti= 0;
        while(sin.hasNext()){
            inta = sin.nextInt();
            numSlice(a,counti);
            counti++;
            if(counti==len){
                break;
            }
        }
        for(inti = 0;i<len;i++){
            if(ksksksk[i]){
                System.out.println("Possible");
            }else{
                System.out.println("Impossible");
            }
        }
    }
}
发表于 2021-03-16 00:28:40 回复(0)
#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)