输入包括t+1行,第一行包括一个整数t(1 ≤ t ≤ 10), 接下来t行,每行一个整数x(1 ≤ x ≤ 10^6)
对于每个x,如果可能重排之后变为自己的倍数输出"Possible", 否则输出"Impossible".
2 14 1035
Impossible Possible
C++因为有next_permutation,还是方便呀。
#include <bits/stdc++.h> using namespace std; int main() { int T; cin >> T; while (T--) { int n; cin >> n; string s_n = to_string(n); sort(s_n.begin(), s_n.end()); bool flag = false; do { int p_num = stoi(s_n); if (p_num!=n && p_num%n==0) { flag = true; break; } } while (next_permutation(s_n.begin(), s_n.end())); cout << (flag ? "Possible" : "Impossible") << endl; } return 0; }
#include <bits/stdc++.h> using namespace std; bool isSame(int x, int y){ vector<int> a, b; while(x){ a.push_back(x%10); x /= 10; } while(y){ b.push_back(y%10); y /= 10; } int n=a.size(), m=b.size(); if(n!=m) return false; sort(a.begin(), a.end()); sort(b.begin(), b.end()); for(int i=0;i<n;i++) if(a[i]!=b[i]) return false; return true; } int main(){ int t, x; scanf("%d", &t); while(t--){ bool flag = false; scanf("%d", &x); for(int i=2;i<=9;i++){ flag = isSame(x, x*i); if(flag) break; } if(flag) puts("Possible"); else puts("Impossible"); } return 0; }
# 数位重排之后,是否是之前自己的倍数,假设是可以的,那可能是自己的多少倍呢 # 除去自身(1倍),还不可能到达10倍及以上,也就是只可能在2~9倍中选择,先计算出自身的2~9倍,看是否可以用自身数字重排获得即可 # 统一按照字典序排序,比较两个数字包含的每一位组合是否相同 def num_sort(ns): lns = sorted(list(ns)) n = int(ns) for i in range(2, 10): if lns == sorted(list(str(n*i))): return 'Possible' else: return 'Impossible' # 看输入输出,应该有个分离,现在这种写法,相当于输入一个就计算一个结果,但是花费的时间更少,而且能沟通过测试 for i in range(int(input())): print(num_sort(input()))
思路:题目要求使用x的原始数字重排,即重排后的位数等于x的位数, 即只需判断x的2到9倍中的数是否存在由x重排得到的数 #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { int t,mid,l; cin>>t; string s1,s2; while(t--) { cin>>mid; s1=to_string(mid); sort(s1.begin(), s1.end()); for(int i=2;i<=10;i++) { l=i*mid; s2=to_string(l); if(s1.length()>s2.length()) { cout<<"Impossible"<<endl; break; } else { sort(s2.begin(), s2.end()); if(s1==s2) { cout<<"Possible"<<endl; break; } } if(i==10) { cout<<"Impossible"<<endl; } } } return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner input = new Scanner(System.in); int t = input.nextInt(); for(int j = 0;j<t;j++){ int x = input.nextInt(); boolean flag = true; for(int i =2;i<=9;i++){ int y = x*i; if(Equal(x,y)){ System.out.println("Possible"); flag = false; break; } } if(flag) System.out.println("Impossible"); } } public static boolean Equal(int x,int y){ String str = String.valueOf(x); String str1 = String.valueOf(y); if(str.length() != str1.length()) return false; char[] s1 =str.toCharArray(); char[] s2 =str1.toCharArray(); Arrays.sort(s1); Arrays.sort(s2); for(int i =0;i<s1.length;i++){ if(s1[i]!=s2[i]) return false; } return true; } }
核心是找到一个数,这个数是原数的倍数,且组成数字与原来的数相同。例如1035和3105。
只需要将某个数从2乘到9,每一个结果都判断一下组成数字是否与原来相同。(乘到10位数都变了,肯定不满足条件,所以是阈值)
def judge(number): for i in range(2, 10): if sorted(str(number * i)) == sorted(str(number)): return True return False for i in range(int(input())): print("Possible" if judge(int(input())) else "Impossible")
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int i=0; i<n; i++) { int org = in.nextInt(); int o = org; ArrayList<Integer> tmpl = new ArrayList<>(); while(o != 0) { int t = o%10; tmpl.add(t); o = o/10; } int[] tmp = new int[tmpl.size()]; for(int j=tmpl.size()-1; j>=0; j--) { tmp[tmpl.size()-1-j] = tmpl.get(j); } ArrayList<Integer> rec = new ArrayList<>(); int[] flag = new int[1]; dfs(tmp, rec, flag, org); if(flag[0] == 0) { System.out.println("Impossible"); } else { System.out.println("Possible"); } } } public static void dfs(int[] tmp, ArrayList<Integer> rec, int[] flag, int org) { if(flag[0] == 1) return; if(rec.size() == tmp.length) { int t = 0; for(int i=0; i<rec.size(); i++) { t = t*10 + rec.get(i); } if (t!=org && t%org == 0) flag[0] = 1; return; } else { for(int i=0; i<tmp.length; i++) { if(tmp[i]>=0) { int t = tmp[i]; tmp[i] = -1; rec.add(t); dfs(tmp, rec, flag, org); rec.remove(rec.size()-1); tmp[i] = t; } } } } }
import itertools t = int(input()) # 题目要求使用x的原始数字重排,即重排后的位数等于x的位数,即只需判断x的2到9倍中的数是否存在由x重排得到的数 def f(s): x = itertools.permutations(s) for n in x: for k in range(2,10): a = "".join(list(n)) if int(a) == (k*int(s)): return "Possible" return "Impossible" i = 0 while i < t: s = input() print(f(s)) i = i + 1
import java.util.*; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int t = s.nextInt(); List<String> res = new ArrayList<>(); for(int i=0;i<t;i++){ int num = s.nextInt(); int prud = 0; boolean flag = false; for(int j=2;j<10;j++){ prud = num*j; if(equals(num,prud)){ flag = true; break; } } if(flag){ res.add("Possible"); }else{ res.add("Impossible"); } } for (String re : res) { System.out.println(re); } } private static boolean equals(Integer x,Integer y){ String a = x.toString(); String b = y.toString(); for(int i=0;i<a.length();i++){ if(b.indexOf(a.charAt(i)) ==-1){ return false; } } return true; } }本地测试半点问题都没有,提交上来就少输出,我傻了
#include<bits/stdc++.h> using namespace std; int x; int getLength(int x){ int ans = 0; while(x){ x/=10; ++ans; } return ans; } string s; void dfs(int cur,int n,string& tmp,int& find,vector<int>& vis){ if(cur==n){ if(tmp!=s&&stoi(tmp)%x==0) find=1; return; } for(int i=0;i<n;++i){ if(!vis[i]){ vis[i]=1; tmp.push_back(s[i]); dfs(cur+1,n,tmp,find,vis); tmp.pop_back(); vis[i]=0; } } } int main(){ int t;; cin>>t; while(t--){ cin>>x; int find = 0; int n = getLength(x); vector<int>vis(n,0); s = to_string(x); string tmp = ""; dfs(0,n,tmp,find,vis); cout<<(find?"Possible":"Impossible")<<endl; } return 0; }
var n=parseInt(readline()); while(n>0){ n--; var num=parseInt(readline()); var old=String(num).split('').sort().join() // 遍历 var flag=true; for(var j=2;j<10;j++){ var sum=num*j; var mynew=String(sum).split('').sort().join() if(old==mynew){ console.log("Possible") flag=false; break; } } if(flag){ console.log("Impossible") } }
import java.util.HashMap; import java.util.Scanner; public clas***ain { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] arrs=new int[n]; for(int i=0;i<n;i++){ arrs[i]=sc.nextInt(); } for(int j:arrs){ if(isPossible(j)){ System.out.println("Possible"); }else{ System.out.println("Impossible"); } } } private static boolean isPossible(int n){ HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<10;i++){ map.put(i,0); } int t=n; while(t>0){ int val=map.get(t%10)+1; map.put(t%10,val); t/=10; } //用于恢复 HashMap<Integer,Integer> mapTemp=new HashMap<>(); for(int i=2;i<10;i++){ int x=n*i; while(x>0){ int val2=map.get(x%10); if(!mapTemp.containsKey(x%10)){ mapTemp.put(x%10,val2); } map.put(x%10,val2-1); x/=10; } for(int val:map.keySet()){ if(map.get(val)!=0){ for(int j:mapTemp.keySet()){ map.put(j,mapTemp.get(j)); } break; } if(val==9){ return true; } } } return false; } }
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Digitalrearrangement { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int num[] = new int[n]; ArrayList<String> arrayList = new ArrayList<String>(); for (int i = 0; i < n; i++) { num[i] = scanner.nextInt(); if (canrearrange(num[i]) == true) { arrayList.add("Possible"); } else { arrayList.add("Impossible"); } } for (int i = 0; i < arrayList.size(); i++) { System.out.println(arrayList.get(i)); } } public static boolean canrearrange(int num) { int n = String.valueOf(num).length(); int[] letter = new int[n]; int temp = num; for (int i = 0; i < n; i++) { letter[i] = temp % 10; temp /= 10; } int[] letter_tmp = new int[n]; for (int i = 2; String.valueOf(num * i).length() == n; i++) { int tmp = num * i; for (int j = 0; j < n; j++) { letter_tmp[j] = tmp % 10; tmp /= 10; } int[] tmp_letter = new int[n]; tmp_letter = letter; Arrays.sort(tmp_letter); Arrays.sort(letter_tmp); if (Arrays.equals(tmp_letter, letter_tmp)) { return true; } } return false; } }} }
import sys if __name__ == '__main__': n = input() i = 0 while i < int(n): s = sys.stdin.readline().strip() if s == '': break if len(s) == 1: print('Impossible') else: j = 2 res = str(int(s)*j) while len(res) <= len(s): j += 1 res = str(int(s)*j) if set(res) == set(s)and len(res) <= len(s): print('Possible') break else: print('Impossible')
//计算输入的数的2-9倍与原数据进行判断 public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(reader.readLine()); Random random = new Random(); for (int i = 0; i < count; i++) { String s1 = reader.readLine(); panduan(i, s1); } } public static void panduan(int i, String s1) { int num = Integer.parseInt(s1); int count=0; for (int j = 2; j <= 9; j++) { int x = num * j; String s2 = String.valueOf(x); if (s1.length() != s2.length()) { System.out.println("Impossible"); break; } else { for (int k = 0; k < s1.length(); k++) { if (!s1.contains(String.valueOf(s2.charAt(k)))) { count++; if (count == 8) { System.out.println("Impossible"); } break; } if (k == s1.length() - 1) { System.out.println("Possible"); return; } } } } } }
#include<iostream> #include<string> #include<algorithm> using namespace std; int main(){ int t; cin>>t; while(t--){ string s; cin>>s; int ori=stoi(s),flag=0; sort(s.begin(),s.end()); do{ int num=stoi(s); if(num!=ori&&num%ori==0){ flag=1; break; } }while(next_permutation(s.begin(),s.end())); if(flag)cout<<"Possible"<<endl; else cout<<"Impossible"<<endl; } }
import java.util.*; public class demo4 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } for (int i = 0; i < n; i++) { System.out.println(solve(arr[i])); } } private static String solve(int n) { int[] arr1 = toArr(n); Arrays.sort(arr1); for (int i = 2; i <= 9; i++) { int s = n * i; int[] arr2 = toArr(s); Arrays.sort(arr2); if (Arrays.equals(arr1,arr2)) { return "Possible"; } } return "Impossible"; } private static int[] toArr(int n) { int a = String.valueOf(n).length();// n的长度 int[] arr2 = new int[a]; String str = String.valueOf(n); for (int i = 0; i < a; i++) { arr2[i] = str.charAt(i); } return arr2; } }写的比较差,,,见笑了