[白俊]3671産業スパイの手紙

質問する

こんにちは!私は産業スパイです.私の本当の身分を他の人に言わないでください.
私の最近の仕事は有名な数学研究所の最新の研究結果を盗むことです.私は有能な産業スパイなので、研究結果は難しくありません.しかし、研究所は私が来ることを事前に知っていたかもしれないし、研究結果をファイルカッターに入れた.仕方なく、涙を浮かべて紙切れを全部盗んで帰ってきた.
私を雇った人はとても恐ろしい人です.また、私はプロなので、間違いを許すことはありません.いずれにしても、私たちはこの紙を修復しなければなりません.この研究所の研究テーマは素数を急速に分解することである.私の紙切れには数字が1つしか書いていません.元の数字がわからない紙切れに書いてある数字を送りますが、紙切れが適当に少数に置かれている場合はいくつか教えていただけませんか.
ありがとうございます.
スパイの夢.

入力

第1行は、試験例の個数cを与える.(1≦c≦200)各試験箱は1行からなり、紙片に書かれた数字は空白ではない.紙切れの数は少なくとも1つ、最大7つです.

しゅつりょく

各試験箱について、紙片を適当に配置して作製できる数少ない異なる数の紙片を出力する.このとき、すべての紙切れを使わない.(7と1がある場合、作成できる数字は7、17、71)紙片を適当な位置に置いて作成した数字が0で始まると、前の0でクリアした数字は同じです.

入力例1

4
17
1276543
9999999
011

サンプル出力1

3
1336
0
2

に答える

この問題はdfs(深さ優先探索)アルゴリズムで解くことができる.この問題に対しては,99999999までアクセス確認を行うため,配列よりもHashSetを用いて確認した.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    static HashSet<Integer> visited;
    static int ans;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            String str = br.readLine();
            boolean[] selected = new boolean[str.length()];
            visited = new HashSet<>();
            ans = 0;
            dfs(selected, str, "");
            System.out.println(ans);
        }
    }

    public static void dfs(boolean[] selected, String str, String temp) {
        if(temp.length()>0 && visited.add(Integer.parseInt(temp))) {
            if(!isPrime(Integer.parseInt(temp)))
                ans++;
        }

        for(int i=0; i<str.length(); i++) {
            if(!selected[i]) {
                selected[i] = true;
                String x = temp;
                dfs(selected, str, x+str.charAt(i));
                selected[i] = false;
            }
        }
    }

    public static boolean isPrime(int num) {
        if(num==0 || num==1) return true;
        boolean flag = false;

        for (int i=2; i<=Math.sqrt(num); i++) {
            if (num%i == 0) {
                flag = true;
                break;
            }
        }
        return flag;
    }
}