結果
問題 | No.308 素数は通れません |
ユーザー | Kilisame |
提出日時 | 2016-09-28 15:35:56 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 124 ms / 1,000 ms |
コード長 | 5,249 bytes |
コンパイル時間 | 3,479 ms |
コンパイル使用メモリ | 82,216 KB |
実行使用メモリ | 58,012 KB |
最終ジャッジ日時 | 2023-08-18 13:28:10 |
合計ジャッジ時間 | 19,406 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 118 ms
55,496 KB |
testcase_01 | AC | 119 ms
55,708 KB |
testcase_02 | AC | 117 ms
55,876 KB |
testcase_03 | AC | 118 ms
55,664 KB |
testcase_04 | AC | 117 ms
55,936 KB |
testcase_05 | AC | 118 ms
55,996 KB |
testcase_06 | AC | 118 ms
55,616 KB |
testcase_07 | AC | 118 ms
55,416 KB |
testcase_08 | AC | 119 ms
55,672 KB |
testcase_09 | AC | 120 ms
55,836 KB |
testcase_10 | AC | 118 ms
55,812 KB |
testcase_11 | AC | 118 ms
55,688 KB |
testcase_12 | AC | 119 ms
55,604 KB |
testcase_13 | AC | 117 ms
55,668 KB |
testcase_14 | AC | 118 ms
55,940 KB |
testcase_15 | AC | 118 ms
55,672 KB |
testcase_16 | AC | 118 ms
55,664 KB |
testcase_17 | AC | 117 ms
55,612 KB |
testcase_18 | AC | 120 ms
55,860 KB |
testcase_19 | AC | 120 ms
55,928 KB |
testcase_20 | AC | 121 ms
55,664 KB |
testcase_21 | AC | 121 ms
55,504 KB |
testcase_22 | AC | 120 ms
55,868 KB |
testcase_23 | AC | 119 ms
55,764 KB |
testcase_24 | AC | 119 ms
55,728 KB |
testcase_25 | AC | 119 ms
55,656 KB |
testcase_26 | AC | 116 ms
55,456 KB |
testcase_27 | AC | 118 ms
55,704 KB |
testcase_28 | AC | 116 ms
53,724 KB |
testcase_29 | AC | 118 ms
55,648 KB |
testcase_30 | AC | 118 ms
55,924 KB |
testcase_31 | AC | 117 ms
56,444 KB |
testcase_32 | AC | 119 ms
56,132 KB |
testcase_33 | AC | 117 ms
55,956 KB |
testcase_34 | AC | 117 ms
55,996 KB |
testcase_35 | AC | 115 ms
55,668 KB |
testcase_36 | AC | 116 ms
55,824 KB |
testcase_37 | AC | 118 ms
55,828 KB |
testcase_38 | AC | 117 ms
56,056 KB |
testcase_39 | AC | 117 ms
55,788 KB |
testcase_40 | AC | 116 ms
55,944 KB |
testcase_41 | AC | 116 ms
55,776 KB |
testcase_42 | AC | 117 ms
55,780 KB |
testcase_43 | AC | 117 ms
55,696 KB |
testcase_44 | AC | 117 ms
55,760 KB |
testcase_45 | AC | 119 ms
56,020 KB |
testcase_46 | AC | 120 ms
55,856 KB |
testcase_47 | AC | 118 ms
56,120 KB |
testcase_48 | AC | 117 ms
56,140 KB |
testcase_49 | AC | 117 ms
55,928 KB |
testcase_50 | AC | 118 ms
56,008 KB |
testcase_51 | AC | 119 ms
55,728 KB |
testcase_52 | AC | 113 ms
55,772 KB |
testcase_53 | AC | 115 ms
55,912 KB |
testcase_54 | AC | 116 ms
55,656 KB |
testcase_55 | AC | 116 ms
55,732 KB |
testcase_56 | AC | 116 ms
58,012 KB |
testcase_57 | AC | 116 ms
55,972 KB |
testcase_58 | AC | 117 ms
55,820 KB |
testcase_59 | AC | 118 ms
55,912 KB |
testcase_60 | AC | 116 ms
55,856 KB |
testcase_61 | AC | 117 ms
55,912 KB |
testcase_62 | AC | 119 ms
55,856 KB |
testcase_63 | AC | 116 ms
55,492 KB |
testcase_64 | AC | 116 ms
53,788 KB |
testcase_65 | AC | 118 ms
55,864 KB |
testcase_66 | AC | 116 ms
55,460 KB |
testcase_67 | AC | 116 ms
55,940 KB |
testcase_68 | AC | 115 ms
55,936 KB |
testcase_69 | AC | 117 ms
55,560 KB |
testcase_70 | AC | 117 ms
55,812 KB |
testcase_71 | AC | 117 ms
55,860 KB |
testcase_72 | AC | 118 ms
56,132 KB |
testcase_73 | AC | 117 ms
55,652 KB |
testcase_74 | AC | 116 ms
55,816 KB |
testcase_75 | AC | 117 ms
55,980 KB |
testcase_76 | AC | 119 ms
55,476 KB |
testcase_77 | AC | 116 ms
56,032 KB |
testcase_78 | AC | 122 ms
55,976 KB |
testcase_79 | AC | 116 ms
55,524 KB |
testcase_80 | AC | 119 ms
55,672 KB |
testcase_81 | AC | 117 ms
55,756 KB |
testcase_82 | AC | 116 ms
55,852 KB |
testcase_83 | AC | 119 ms
55,704 KB |
testcase_84 | AC | 120 ms
55,840 KB |
testcase_85 | AC | 117 ms
53,800 KB |
testcase_86 | AC | 120 ms
55,780 KB |
testcase_87 | AC | 122 ms
55,936 KB |
testcase_88 | AC | 120 ms
56,772 KB |
testcase_89 | AC | 121 ms
55,776 KB |
testcase_90 | AC | 124 ms
55,852 KB |
testcase_91 | AC | 118 ms
56,016 KB |
testcase_92 | AC | 119 ms
56,000 KB |
testcase_93 | AC | 117 ms
55,668 KB |
testcase_94 | AC | 118 ms
55,684 KB |
testcase_95 | AC | 117 ms
55,692 KB |
testcase_96 | AC | 120 ms
56,028 KB |
testcase_97 | AC | 121 ms
55,848 KB |
testcase_98 | AC | 118 ms
55,924 KB |
testcase_99 | AC | 122 ms
56,048 KB |
testcase_100 | AC | 121 ms
55,692 KB |
testcase_101 | AC | 123 ms
55,472 KB |
testcase_102 | AC | 117 ms
55,836 KB |
testcase_103 | AC | 118 ms
55,708 KB |
testcase_104 | AC | 118 ms
56,316 KB |
testcase_105 | AC | 117 ms
55,712 KB |
testcase_106 | AC | 121 ms
55,836 KB |
ソースコード
package puzzle.yukicoder.primeimpassable; import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class PrimeImpassable { private static List<Integer> primeList; public static void main(String[] args) { Scanner cin = new Scanner(System.in); BigInteger n = new BigInteger(cin.next()); cin.close(); int w; /* * wが1のとき、スタートである1に隣接するのは素数である2のみなので、どこへも移動できない。 * wが2以上で、w+1が素数のとき、スタートである1に隣接する2とw+1へ移動できないため、どこへも移動できない。 * なので、w+1が素数でない数字のみをwの候補として検討する。 * w=3のとき、4へ移動できる。しかし5と7へ移動できないので、N=4のときのみw=3が答え。 * w=5のとき、6へ移動できる。しかし7と11へ移動できないので、N=6のときのみw=5が答え。 * w=7のとき、8,9,10,15,16,22が移動可能な範囲全てである。Nが上記の場合にw=7となる。 * w=8のとき、9,10,18,26,27,28,20,21,22,14,15,16と移動することで全ての列に移動することができる。wが偶数の場合、偶数列目は全ての数字が偶数なので、上下に好きなだけ移動することができる。 * Nが偶数であれば、必ず到達することができる。またNが奇数でも一番左の列(N mod 8 = 1)でなければ、左隣の偶数から移動してくれば良い。またN-8が素数でなければ、そのマスには偶数であるN-7から左に移動することができるので、そこから下に移動してNに到達可能。 * 全ての列に到達するまでに通る最大のマスは28であり、28に到達するまでに26,27を通過しているので、N>=26において、N mod 8 = 1かつN-8が素数、以外の数はw=8が答え。 * 同様にw+1が素数ではない偶数のwを探すと、次の候補は14である。w=14のとき、全ての列に到達するために通過する一番大きいマスは46である。46へは44,45を通過するので、N>=44であれば、 N mod 14 = 1 かつ N-14が素数 でなければw=14で成り立つ。 * 以上より、N<26の時と、N<46でw=8が成り立たない数字の場合のみ、全探索を実行する。それ以外のケースはw=8もしくはw=14が解。 */ /* 全探索は44未満の場合しかやらないので、そこまでの素数を列挙しておく。 */ primeList = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43); if (n.compareTo(new BigInteger("26")) < 0) { /* 26までの数字は、w=8で全ての偶数列に到達できないケースなので全探索する */ w = checkAllRoot(n.intValue()); } else if (n.compareTo(new BigInteger("44")) < 0 && n.mod(new BigInteger("8")).equals(new BigInteger("1")) && n.subtract(new BigInteger("8")).isProbablePrime(8)) { /* 44までの数字は、w=14で全ての偶数列に到達できないケースなので全探索する */ w = checkAllRoot(n.intValue()); } else if (n.mod(new BigInteger("8")).equals(new BigInteger("1")) && n.subtract(new BigInteger("8")).isProbablePrime(8)) { w = 14; } else { w = 8; } System.out.println(w); } private static int checkAllRoot(int n) { for (int w = 1; w < n; w++) { if (primeList.contains(w + 1)) { continue; } if (w == n - 1) { return w; } List<Integer> reachedBlock = new ArrayList<Integer>(); List<Integer> currentBlock = new ArrayList<Integer>(); reachedBlock.add(1); currentBlock.add(1); while (!currentBlock.isEmpty()) { List<Integer> nextBlock = new ArrayList<Integer>(); for (int block : currentBlock) { if ((block - 1) % w > 0 && !primeList.contains(block - 1) && !reachedBlock.contains(block - 1)) { nextBlock.add(block - 1); } if (block + 1 <= n && (block - 1) % w < w - 1 && !primeList.contains(block + 1) && !reachedBlock.contains(block + 1)) { nextBlock.add(block + 1); } if ((block - 1) / w > 0 && !primeList.contains(block - w) && !reachedBlock.contains(block - w)) { nextBlock.add(block + w); } if (block + w <= n && (block - 1) / w < n / w && !primeList.contains(block + w) && !reachedBlock.contains(block + w)) { nextBlock.add(block + w); } } if (nextBlock.contains(n)) { return w; } reachedBlock.addAll(nextBlock); currentBlock = nextBlock; } } return -1; } }