本文主要是介绍ural 1014. Product of Digits贪心,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1014. Product of Digits
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Your task is to find the minimal positive integer number Q so that the product of digits of Q is exactly equal to N.
Input
The input contains the single integer number N (0 ≤ N ≤ 10 9).
Output
Your program should print to the output the only number Q. If such a number does not exist print −1.
Sample
input | output |
---|---|
10 | 25 |
Problem Source: Ural State University Internal Contest '99 #2
Tags: problem for beginners
)
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Task().solve();}
}class Task {InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);String gao(int n){if(n == 0){return "10" ;}if(n == 1){return "1" ;}int two = 0 ;int three = 0 ;String five = "" , seven = "" , eight = "" , nine = "";while(n % 2 == 0){two++ ;n /= 2 ;}while(n % 3 == 0){three++ ;n /= 3 ;}while(n % 5 == 0){five += "5" ;n /= 5 ;}while(n % 7 == 0){seven += "7" ;n /= 7 ;}if(n != 1){return "-1" ;}for(int i = 0 ; i < two/3 ; i++){eight += "8" ;}two %= 3 ;for(int i = 0 ; i < three/2 ; i++){nine += "9" ;}String prefix = "" ;three %= 2 ;if(three == 0 ){if(two == 1){prefix = "2" + five ; }else if(two == 2){prefix = "4" + five ;} }else{if(two == 0){prefix = "3" + five ;}else if(two == 1){prefix = five + "6" ;}else if(two == 2){prefix = "2" + five + "6" ;}}if("".equals(prefix)){prefix = five ;}return prefix + seven + eight + nine ;}void solve() {while(in.hasNext()){out.println(gao(in.nextInt())) ;}out.flush();}}class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = new StringTokenizer("");}private void eat(String s) {tokenizer = new StringTokenizer(s);}public String nextLine() {try {return reader.readLine();} catch (Exception e) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String s = nextLine();if (s == null)return false;eat(s);}return true;}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public int[] nextInts(int n){int[] nums = new int[n] ;for(int i = 0 ; i < n ; i++){nums[i] = nextInt() ;}return nums ;}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
这篇关于ural 1014. Product of Digits贪心的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!