首页 > 试题广场 >

数位重排

[编程题]数位重排
  • 热度指数:87 时间限制: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
while True:
    try:
        t=int(raw_input().strip())
        if t==0:
            break
        for i in range(t):
            s=raw_input().strip()
            if int(s)<=9:
                print('Impossible')
            else:
                if len(list(set(list(s))))==1:
                    print('Impossible')
                else:
                    count=0
                    for i in range(2,10):
                        x=str(int(s)*i)
                        a=[int(i) for i in x]
                        b=[int(i) for i in s]
                        a.sort()
                        b.sort()
                        if int(x)!=int(s) and a==b:
                            count+=1
            if count>=1:
                print('Possible')
            else:
                print('Impossible')
    except:
        break
发表于 2018-06-02 08:53:17 回复(0)

方法比较死,就是按照原来数的倍数去判断是否存在这样的数。因为一个数怎样变化,位数和内容都需要一样。

public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    scanner.nextLine();
    while (n-- >0){
        boolean is = false;
        int s = scanner.nextInt();
        String temp = String.valueOf(s);
        for(int i=2;i<=9;i++){
            String str = String.valueOf( s*i);
            if(temp.length()!=str.length()  ){
                break;
            }
            int index = -1;
            int count = 0;
            for(char c:temp.toCharArray()){
                index = str.indexOf(c);
                if(index==-1){
                    break;
                }else{
                    count++;
                }
            }
            if(count==temp.length()){
                is = true;
                break;
            }
        }
        if(is){
            System.out.println("Possible");
        }else{
            System.out.println("Impossible");
        }
    }

}
发表于 2018-06-04 17:08:02 回复(0)
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int i;
bool resf(deque<int> & temp,int index,int t){
    if(index == temp.size()-1){
        ++i;
        int sult = 0;
        for(int i = 0;i < temp.size();i++){
            sult = sult *10 + temp[i];
        }
        if(sult % t == 0 && sult != t)
            return true;
        else
            return false;
    }
    for(int j = index;j < temp.size();j++){
        swap(temp[index],temp[j]);
        bool flag = resf(temp,index+1,t);
        if(flag == true)
            return true;
        swap(temp[index],temp[j]);
    }
    return false;
}
int main(){
    int num,in;
    deque<int> temp;
    deque<bool> res;
    while(cin >> num){
        for(int i = 0;i < num;i++){
            cin >> in;
            int t = in;
            while(in > 0){
                temp.push_front(in % 10);
                in /= 10;
            }
            res.push_back(resf(temp,0,t));
            temp.clear();
        }
        for(int i = 0;i < res.size();i++)
            if(res[i] == true)
                cout<<"Possible"<<endl;
            else
                cout<<"Impossible"<<endl;
        res.clear();
    }
    return 0;
}
发表于 2018-05-29 20:58:44 回复(0)