結果
問題 | No.308 素数は通れません |
ユーザー | Kilisame |
提出日時 | 2016-09-28 15:35:56 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 116 ms / 1,000 ms |
コード長 | 5,249 bytes |
コンパイル時間 | 3,330 ms |
コンパイル使用メモリ | 80,520 KB |
実行使用メモリ | 41,592 KB |
最終ジャッジ日時 | 2024-05-05 18:42:26 |
合計ジャッジ時間 | 16,561 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 105 ms
40,960 KB |
testcase_01 | AC | 107 ms
41,288 KB |
testcase_02 | AC | 106 ms
41,592 KB |
testcase_03 | AC | 105 ms
40,668 KB |
testcase_04 | AC | 103 ms
40,928 KB |
testcase_05 | AC | 102 ms
41,192 KB |
testcase_06 | AC | 102 ms
41,160 KB |
testcase_07 | AC | 92 ms
39,468 KB |
testcase_08 | AC | 108 ms
41,140 KB |
testcase_09 | AC | 111 ms
41,252 KB |
testcase_10 | AC | 98 ms
40,008 KB |
testcase_11 | AC | 107 ms
41,356 KB |
testcase_12 | AC | 105 ms
41,212 KB |
testcase_13 | AC | 108 ms
41,124 KB |
testcase_14 | AC | 109 ms
41,300 KB |
testcase_15 | AC | 106 ms
40,920 KB |
testcase_16 | AC | 109 ms
41,256 KB |
testcase_17 | AC | 104 ms
41,320 KB |
testcase_18 | AC | 108 ms
41,076 KB |
testcase_19 | AC | 104 ms
40,916 KB |
testcase_20 | AC | 97 ms
40,044 KB |
testcase_21 | AC | 103 ms
41,192 KB |
testcase_22 | AC | 108 ms
41,384 KB |
testcase_23 | AC | 102 ms
41,200 KB |
testcase_24 | AC | 104 ms
41,304 KB |
testcase_25 | AC | 113 ms
40,940 KB |
testcase_26 | AC | 102 ms
40,152 KB |
testcase_27 | AC | 105 ms
41,212 KB |
testcase_28 | AC | 106 ms
40,788 KB |
testcase_29 | AC | 105 ms
40,792 KB |
testcase_30 | AC | 104 ms
41,024 KB |
testcase_31 | AC | 108 ms
41,356 KB |
testcase_32 | AC | 106 ms
40,984 KB |
testcase_33 | AC | 105 ms
41,040 KB |
testcase_34 | AC | 96 ms
40,132 KB |
testcase_35 | AC | 104 ms
40,904 KB |
testcase_36 | AC | 103 ms
41,248 KB |
testcase_37 | AC | 96 ms
39,796 KB |
testcase_38 | AC | 107 ms
41,016 KB |
testcase_39 | AC | 108 ms
41,300 KB |
testcase_40 | AC | 99 ms
40,380 KB |
testcase_41 | AC | 103 ms
41,096 KB |
testcase_42 | AC | 99 ms
40,560 KB |
testcase_43 | AC | 110 ms
41,240 KB |
testcase_44 | AC | 107 ms
40,060 KB |
testcase_45 | AC | 100 ms
40,124 KB |
testcase_46 | AC | 105 ms
40,904 KB |
testcase_47 | AC | 105 ms
40,752 KB |
testcase_48 | AC | 93 ms
40,084 KB |
testcase_49 | AC | 104 ms
41,160 KB |
testcase_50 | AC | 104 ms
41,372 KB |
testcase_51 | AC | 95 ms
39,992 KB |
testcase_52 | AC | 98 ms
40,104 KB |
testcase_53 | AC | 95 ms
39,792 KB |
testcase_54 | AC | 108 ms
40,900 KB |
testcase_55 | AC | 107 ms
40,432 KB |
testcase_56 | AC | 109 ms
41,544 KB |
testcase_57 | AC | 112 ms
41,052 KB |
testcase_58 | AC | 99 ms
40,044 KB |
testcase_59 | AC | 96 ms
40,132 KB |
testcase_60 | AC | 105 ms
41,480 KB |
testcase_61 | AC | 107 ms
41,244 KB |
testcase_62 | AC | 109 ms
41,176 KB |
testcase_63 | AC | 106 ms
41,248 KB |
testcase_64 | AC | 109 ms
41,064 KB |
testcase_65 | AC | 100 ms
40,588 KB |
testcase_66 | AC | 105 ms
40,940 KB |
testcase_67 | AC | 109 ms
41,056 KB |
testcase_68 | AC | 99 ms
39,908 KB |
testcase_69 | AC | 112 ms
41,396 KB |
testcase_70 | AC | 115 ms
41,160 KB |
testcase_71 | AC | 98 ms
40,128 KB |
testcase_72 | AC | 105 ms
41,032 KB |
testcase_73 | AC | 105 ms
41,252 KB |
testcase_74 | AC | 105 ms
41,020 KB |
testcase_75 | AC | 103 ms
41,312 KB |
testcase_76 | AC | 99 ms
40,052 KB |
testcase_77 | AC | 108 ms
40,928 KB |
testcase_78 | AC | 106 ms
41,072 KB |
testcase_79 | AC | 106 ms
40,680 KB |
testcase_80 | AC | 100 ms
40,296 KB |
testcase_81 | AC | 100 ms
39,932 KB |
testcase_82 | AC | 98 ms
40,348 KB |
testcase_83 | AC | 90 ms
39,668 KB |
testcase_84 | AC | 106 ms
41,096 KB |
testcase_85 | AC | 108 ms
41,024 KB |
testcase_86 | AC | 109 ms
41,036 KB |
testcase_87 | AC | 98 ms
39,936 KB |
testcase_88 | AC | 96 ms
40,024 KB |
testcase_89 | AC | 89 ms
39,516 KB |
testcase_90 | AC | 110 ms
41,088 KB |
testcase_91 | AC | 104 ms
41,052 KB |
testcase_92 | AC | 104 ms
41,216 KB |
testcase_93 | AC | 104 ms
41,340 KB |
testcase_94 | AC | 96 ms
40,056 KB |
testcase_95 | AC | 106 ms
41,240 KB |
testcase_96 | AC | 116 ms
41,276 KB |
testcase_97 | AC | 102 ms
40,048 KB |
testcase_98 | AC | 109 ms
40,800 KB |
testcase_99 | AC | 107 ms
41,332 KB |
testcase_100 | AC | 107 ms
40,232 KB |
testcase_101 | AC | 108 ms
40,416 KB |
testcase_102 | AC | 114 ms
41,456 KB |
testcase_103 | AC | 99 ms
39,996 KB |
testcase_104 | AC | 106 ms
40,744 KB |
testcase_105 | AC | 102 ms
41,116 KB |
testcase_106 | AC | 109 ms
41,484 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; } }