結果
問題 | No.12 限定された素数 |
ユーザー | atn112323 |
提出日時 | 2016-02-06 21:44:53 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 256 ms / 5,000 ms |
コード長 | 12,575 bytes |
コンパイル時間 | 3,064 ms |
コンパイル使用メモリ | 90,856 KB |
実行使用メモリ | 64,616 KB |
最終ジャッジ日時 | 2024-05-03 09:39:56 |
合計ジャッジ時間 | 9,762 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 191 ms
63,572 KB |
testcase_01 | AC | 230 ms
64,448 KB |
testcase_02 | AC | 197 ms
63,468 KB |
testcase_03 | AC | 246 ms
64,052 KB |
testcase_04 | AC | 206 ms
63,936 KB |
testcase_05 | AC | 238 ms
64,580 KB |
testcase_06 | AC | 222 ms
64,440 KB |
testcase_07 | AC | 244 ms
64,260 KB |
testcase_08 | AC | 215 ms
64,356 KB |
testcase_09 | AC | 214 ms
63,720 KB |
testcase_10 | AC | 235 ms
64,616 KB |
testcase_11 | AC | 256 ms
64,456 KB |
testcase_12 | AC | 214 ms
64,040 KB |
testcase_13 | AC | 223 ms
64,480 KB |
testcase_14 | AC | 214 ms
64,096 KB |
testcase_15 | AC | 220 ms
64,488 KB |
testcase_16 | AC | 243 ms
64,200 KB |
testcase_17 | AC | 188 ms
63,588 KB |
testcase_18 | AC | 190 ms
63,612 KB |
testcase_19 | AC | 194 ms
63,664 KB |
testcase_20 | AC | 232 ms
64,584 KB |
testcase_21 | AC | 211 ms
64,044 KB |
testcase_22 | AC | 192 ms
63,648 KB |
testcase_23 | AC | 191 ms
63,652 KB |
testcase_24 | AC | 195 ms
63,496 KB |
testcase_25 | AC | 213 ms
64,128 KB |
ソースコード
import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Main { /** * This class represents a problem setting. */ class Problem implements IProblem { int N; int[] A; @Override public void set(ProblemReader reader) throws IOException { N = reader.nextInt(); A = reader.nextIntArray(); } @Override public String toString() { // TODO return null; } } /** * Solver for the problem. * It's the most important part of codes in this file. */ class Solver implements IProblemSolver<Problem> { int MAX = 5000000; @Override public String solve(Problem problem) { int N = problem.N; int[] A = problem.A; return StringUtils.toString(solve(N, A)); } private int solve(int N, int[] A) { boolean[] contained = new boolean[10]; for (int i = 0; i < N; i++) { contained[A[i]] = true; } boolean[] notPrime = new boolean[MAX + 1]; List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= MAX; i++) { if (!notPrime[i]) { primes.add(i); for (int j = i + i; j <= MAX; j += i) { notPrime[j] = true; } } } boolean[] invalid = new boolean[primes.size()]; for (int i = 0; i < primes.size(); i++) { int n = primes.get(i); while (n > 0) { if (!contained[n % 10]) { invalid[i] = true; break; } n /= 10; } } int max = -1; int[] cnt = new int[10]; int idx = 0; for (int i = 0; i < primes.size(); i++) { if (invalid[i]) { continue; } idx = Math.max(idx, i); while (idx < primes.size() && !invalid[idx]) { int n = primes.get(idx); while (n > 0) { cnt[n % 10]++; n /= 10; } idx++; } boolean filled = true; for (int j = 0; j < 10; j++) { if (contained[j] && cnt[j] == 0) { filled = false; break; } } if (filled) { int K = 1, L = MAX; if (i > 0) { K = primes.get(i - 1) + 1; } if (idx < primes.size()) { L = primes.get(idx) - 1; } max = Math.max(max, L - K); } int n = primes.get(i); while (n > 0) { cnt[n % 10]--; n /= 10; } } return max; } } /** * This class is a solver to confirm the main solver. * This solver often works only for a problem with a small number setting. */ class Solver2 implements IProblemSolver<Problem> { @Override public String solve(Problem problem) { // TODO return null; } } class Factory implements IProblemFactory<Problem> { @Override public Problem newProblem() { // TODO return null; } @Override public Problem newProblem(ProblemReader reader) throws IOException { Problem problem = new Problem(); problem.set(reader); return problem; } } ProblemProcessor<Problem> processor; Main() { Init(); } void Init() { ProblemProcessorConfig<Problem> config = new ProblemProcessorConfig<>(); config.factory = new Factory(); config.solver = new Solver(); config.solver2 = new Solver2(); processor = new ProblemProcessor<Problem>(config); } void process(String mode) throws IOException { processor.process(mode); } public static void main(String args[]) throws IOException { String mode = "solve"; new Main().process(mode); } /* Common library */ interface IProblem { abstract void set(ProblemReader reader) throws IOException; } interface IProblemFactory<P extends IProblem> { abstract P newProblem(); abstract P newProblem(ProblemReader reader) throws IOException; } interface IProblemSolver<P extends IProblem> { abstract String solve(P problem); } class ProblemReader { BufferedReader br = null; ProblemReader() { br = new BufferedReader(new InputStreamReader(System.in)); } int nextInt() throws IOException { return StringUtils.toInt(br.readLine()); } long nextLong() throws IOException { return StringUtils.toLong(br.readLine()); } double nextDouble() throws IOException { return StringUtils.toDouble(br.readLine()); } String nextString() throws IOException { return br.readLine(); } int[] nextIntArray() throws IOException { return StringUtils.toIntArray(br.readLine()); } long[] nextLongArray() throws IOException { return StringUtils.toLongArray(br.readLine()); } double[] nextDoubleArray() throws IOException { return StringUtils.toDoubleArray(br.readLine()); } String[] nextStringArray() throws IOException { return StringUtils.toStringArray(br.readLine()); } int[] nextIntArray(int n) throws IOException { int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } long[] nextLongArray(int n) throws IOException { long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = nextLong(); } return a; } double[] nextDoubleArray(int n) throws IOException { double[] a = new double[n]; for (int i = 0; i < n; i++) { a[i] = nextDouble(); } return a; } String[] nextStringArray(int n) throws IOException { String[] strs = new String[n]; for (int i = 0; i < n; i++) { strs[i] = nextString(); } return strs; } int[][] nextIntArray2(int n) throws IOException { int[][] a = new int[n][]; for (int i = 0; i < n; i++) { a[i] = nextIntArray(); } return a; } long[][] nextLongArray2(int n) throws IOException { long[][] a = new long[n][]; for (int i = 0; i < n; i++) { a[i] = nextLongArray(); } return a; } double[][] nextDoubleArray2(int n) throws IOException { double[][] a = new double[n][]; for (int i = 0; i < n; i++) { a[i] = nextDoubleArray(); } return a; } String[][] nextStringArray2(int n) throws IOException { String[][] strs = new String[n][]; for (int i = 0; i < n; i++) { strs[i] = nextStringArray(); } return strs; } void close() throws IOException { if (br != null) { br.close(); } } } class ProblemCreator<P extends IProblem> { IProblemFactory<P> factory; ProblemCreator(IProblemFactory<P> factory) { this.factory = factory; } void create() throws FileNotFoundException { P problem = factory.newProblem(); System.out.println(problem.toString()); } } class ProblemSolverComparator<P extends IProblem> { IProblemFactory<P> factory; IProblemSolver<P> solver1, solver2; ProblemSolverComparator(IProblemFactory<P> factory, IProblemSolver<P> solver1, IProblemSolver<P> solver2) { this.factory = factory; this.solver1 = solver1; this.solver2 = solver2; } void compare() throws IOException { ProblemReader reader = null; try { reader = new ProblemReader(); P problem = factory.newProblem(reader); String res1 = solver1.solve(problem); String res2 = solver2.solve(problem); if (res1.equals(res2)) { System.out.println(res1); } else { System.err.println(res1 + " " + res2); } } finally { if (reader != null) { reader.close(); } } } } class ProblemAnswerer<P extends IProblem> { IProblemFactory<P> factory; IProblemSolver<P> solver; ProblemAnswerer(IProblemFactory<P> factory, IProblemSolver<P> solver) { this.factory = factory; this.solver = solver; } void answer() throws IOException { ProblemReader reader = null; try { reader = new ProblemReader(); P problem = factory.newProblem(reader); String res = solver.solve(problem); System.out.println(res); } finally { if (reader != null) { reader.close(); } } } } class ProblemProcessorConfig<P extends IProblem> { IProblemFactory<P> factory; IProblemSolver<P> solver, solver2; } class ProblemProcessor<P extends IProblem> { ProblemProcessorConfig<P> config; ProblemCreator<P> creator; ProblemSolverComparator<P> comparator; ProblemAnswerer<P> answerer; ProblemProcessor(ProblemProcessorConfig<P> config) { this.config = config; creator = new ProblemCreator<P>(config.factory); comparator = new ProblemSolverComparator<P>(config.factory, config.solver, config.solver2); answerer = new ProblemAnswerer<P>(config.factory, config.solver); } void process(String mode) throws IOException { switch (mode) { case "create": creator.create(); break; case "debug": comparator.compare(); break; case "solve": answerer.answer(); break; } } } static class StringUtils { static String toString(int a) { return String.valueOf(a); } static String toString(long a) { return String.valueOf(a); } static String toString(double a) { return String.valueOf(a); } static String toString(String str) { return str; } static String toString(int[] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { if (i < a.length - 1) { sb.append(a[i] + " "); } else { sb.append(a[i]); } } return sb.toString(); } static String toString(long[] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { if (i < a.length - 1) { sb.append(a[i] + " "); } else { sb.append(a[i]); } } return sb.toString(); } static String toString(double[] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { if (i < a.length - 1) { sb.append(a[i] + " "); } else { sb.append(a[i]); } } return sb.toString(); } static String toString(String[] strs) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < strs.length; i++) { if (i < strs.length - 1) { sb.append(strs[i] + " "); } else { sb.append(strs[i]); } } return sb.toString(); } static String toString(int[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static String toString(long[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static String toString(double[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static String toString(String[][] a) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (j < a[i].length - 1) { sb.append(a[i][j] + " "); } else { sb.append(a[i][j]); } } sb.append("\n"); } sb.setLength(sb.length() - 1); return sb.toString(); } static int toInt(String s) throws IOException { return Integer.parseInt(s); } static long toLong(String s) throws IOException { return Long.parseLong(s); } static double toDouble(String s) throws IOException { return Double.parseDouble(s); } static int[] toIntArray(String s) throws IOException { String[] tokens = s.split(" "); int[] a = new int[tokens.length]; for (int i = 0; i < tokens.length; i++) { a[i] = Integer.parseInt(tokens[i]); } return a; } static long[] toLongArray(String s) throws IOException { String[] tokens = s.split(" "); long[] a = new long[tokens.length]; for (int i = 0; i < tokens.length; i++) { a[i] = Long.parseLong(tokens[i]); } return a; } static double[] toDoubleArray(String s) throws IOException { String[] tokens = s.split(" "); double[] a = new double[tokens.length]; for (int i = 0; i < tokens.length; i++) { a[i] = Double.parseDouble(tokens[i]); } return a; } static String[] toStringArray(String s) throws IOException { return s.split(" "); } } }