#62274 (Java21) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	uafr_cs
提出日時	2015-12-03 20:14:06
言語	Java21 (openjdk 21)
結果	AC
実行時間	141 ms / 1,000 ms
コード長	3,430 bytes
コンパイル時間	3,289 ms
コンパイル使用メモリ	86,876 KB
実行使用メモリ	42,176 KB
最終ジャッジ日時	2024-05-05 18:36:11
合計ジャッジ時間	17,052 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	107 ms 41,160 KB
testcase_01	AC	109 ms 39,776 KB
testcase_02	AC	110 ms 40,188 KB
testcase_03	AC	110 ms 41,248 KB
testcase_04	AC	111 ms 40,812 KB
testcase_05	AC	109 ms 40,936 KB
testcase_06	AC	106 ms 39,916 KB
testcase_07	AC	98 ms 39,900 KB
testcase_08	AC	108 ms 41,072 KB
testcase_09	AC	132 ms 40,056 KB
testcase_10	AC	107 ms 40,060 KB
testcase_11	AC	110 ms 40,872 KB
testcase_12	AC	119 ms 40,908 KB
testcase_13	AC	120 ms 41,216 KB
testcase_14	AC	118 ms 41,084 KB
testcase_15	AC	106 ms 41,388 KB
testcase_16	AC	95 ms 40,216 KB
testcase_17	AC	116 ms 41,204 KB
testcase_18	AC	112 ms 41,172 KB
testcase_19	AC	109 ms 41,476 KB
testcase_20	AC	95 ms 40,452 KB
testcase_21	AC	110 ms 41,216 KB
testcase_22	AC	120 ms 41,320 KB
testcase_23	AC	115 ms 41,264 KB
testcase_24	AC	113 ms 41,252 KB
testcase_25	AC	115 ms 41,396 KB
testcase_26	AC	108 ms 41,148 KB
testcase_27	AC	111 ms 41,468 KB
testcase_28	AC	107 ms 41,428 KB
testcase_29	AC	105 ms 41,220 KB
testcase_30	AC	111 ms 40,940 KB
testcase_31	AC	127 ms 41,052 KB
testcase_32	AC	103 ms 40,044 KB
testcase_33	AC	111 ms 41,056 KB
testcase_34	AC	112 ms 41,500 KB
testcase_35	AC	103 ms 40,984 KB
testcase_36	AC	98 ms 40,232 KB
testcase_37	AC	105 ms 41,124 KB
testcase_38	AC	104 ms 41,256 KB
testcase_39	AC	96 ms 40,008 KB
testcase_40	AC	111 ms 41,320 KB
testcase_41	AC	106 ms 41,224 KB
testcase_42	AC	98 ms 40,024 KB
testcase_43	AC	109 ms 40,916 KB
testcase_44	AC	105 ms 41,256 KB
testcase_45	AC	105 ms 41,040 KB
testcase_46	AC	112 ms 41,084 KB
testcase_47	AC	95 ms 40,096 KB
testcase_48	AC	92 ms 39,744 KB
testcase_49	AC	104 ms 40,932 KB
testcase_50	AC	105 ms 40,944 KB
testcase_51	AC	106 ms 41,224 KB
testcase_52	AC	107 ms 41,264 KB
testcase_53	AC	105 ms 41,228 KB
testcase_54	AC	103 ms 41,088 KB
testcase_55	AC	105 ms 41,072 KB
testcase_56	AC	107 ms 40,924 KB
testcase_57	AC	115 ms 41,608 KB
testcase_58	AC	98 ms 40,092 KB
testcase_59	AC	107 ms 40,616 KB
testcase_60	AC	98 ms 39,996 KB
testcase_61	AC	108 ms 41,420 KB
testcase_62	AC	110 ms 41,204 KB
testcase_63	AC	112 ms 41,080 KB
testcase_64	AC	112 ms 41,128 KB
testcase_65	AC	110 ms 41,148 KB
testcase_66	AC	108 ms 41,120 KB
testcase_67	AC	108 ms 41,120 KB
testcase_68	AC	120 ms 41,800 KB
testcase_69	AC	112 ms 41,116 KB
testcase_70	AC	109 ms 41,128 KB
testcase_71	AC	99 ms 40,208 KB
testcase_72	AC	108 ms 41,072 KB
testcase_73	AC	107 ms 41,260 KB
testcase_74	AC	107 ms 41,296 KB
testcase_75	AC	99 ms 40,216 KB
testcase_76	AC	118 ms 41,484 KB
testcase_77	AC	101 ms 40,052 KB
testcase_78	AC	100 ms 39,756 KB
testcase_79	AC	102 ms 40,220 KB
testcase_80	AC	129 ms 41,596 KB
testcase_81	AC	124 ms 41,316 KB
testcase_82	AC	105 ms 40,944 KB
testcase_83	AC	100 ms 39,936 KB
testcase_84	AC	122 ms 41,320 KB
testcase_85	AC	99 ms 40,732 KB
testcase_86	AC	124 ms 41,396 KB
testcase_87	AC	133 ms 41,628 KB
testcase_88	AC	105 ms 40,744 KB
testcase_89	AC	110 ms 41,292 KB
testcase_90	AC	126 ms 41,492 KB
testcase_91	AC	94 ms 39,876 KB
testcase_92	AC	107 ms 40,908 KB
testcase_93	AC	106 ms 41,060 KB
testcase_94	AC	98 ms 40,048 KB
testcase_95	AC	97 ms 40,040 KB
testcase_96	AC	111 ms 41,252 KB
testcase_97	AC	96 ms 40,040 KB
testcase_98	AC	102 ms 41,252 KB
testcase_99	AC	98 ms 40,164 KB
testcase_100	AC	107 ms 40,988 KB
testcase_101	AC	141 ms 42,176 KB
testcase_102	AC	104 ms 41,168 KB
testcase_103	AC	108 ms 41,196 KB
testcase_104	AC	94 ms 40,044 KB
testcase_105	AC	94 ms 39,992 KB
testcase_106	AC	106 ms 40,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;

public class Main {
	
	public static int simulate(final int N){
		boolean[] is_prime = new boolean[N + 1];
		Arrays.fill(is_prime, 2, N + 1, true);
		
		for(int i = 2; i * i <= N; i++){
			if(!is_prime[i]){ continue; }
			
			for(int j = i * 2; j <= N; j += i){
				is_prime[j] = false;
			}
		}
		
		if(is_prime[N]){ return -1; }

		boolean[] visited = new boolean[N];
		for(int mid = 1; mid <= N; mid++){
			Arrays.fill(visited, false);

			
			LinkedList<Integer> queue = new LinkedList<Integer>();
			queue.add(0);
			visited[0] = true;
			while(!queue.isEmpty()){
				final int pos = queue.poll();
				final int number = pos + 1;
				
				if(number == N){ break; }
				//System.out.println(mid + " => " + pos + " : " + (pos % mid));
				
				if(pos % mid > 0 && !is_prime[number - 1] && !visited[pos - 1]){
					queue.add(pos - 1);
					visited[pos - 1] = true;
				}
				if(pos % mid < (mid - 1) && !is_prime[number + 1] && !visited[pos + 1]){
					queue.add(pos + 1);
					visited[pos + 1] = true;
				}
				if((pos - mid) > 0 && !is_prime[number - mid] && !visited[pos - mid]){
					queue.add(pos - mid);
					visited[pos - mid] = true;
				}
				if((pos + mid) < N && !is_prime[number + mid] && !visited[pos + mid]){
					queue.add(pos + mid);
					visited[pos + mid] = true;
				}
			}
			
			if(visited[N - 1]){
				return mid;
			}
		}
		
		return -1;
	}
	
	public static int smart(final BigInteger N){
		final BigInteger four = BigInteger.valueOf(4);
		final BigInteger six = BigInteger.valueOf(6);
		final BigInteger eight = BigInteger.valueOf(8);
		final BigInteger nine = BigInteger.valueOf(9);
		final BigInteger ten = BigInteger.valueOf(10);
		final BigInteger twelve = BigInteger.valueOf(12);
		final BigInteger fourteen = BigInteger.valueOf(14);
		final BigInteger fifteen = BigInteger.valueOf(15);
		final BigInteger sixteen = BigInteger.valueOf(16);
		final BigInteger twenty = BigInteger.valueOf(20);
		final BigInteger twentyone = BigInteger.valueOf(21);
		final BigInteger twentytwo = BigInteger.valueOf(22);
		final BigInteger twentyfour = BigInteger.valueOf(24);
		final BigInteger twentyfive = BigInteger.valueOf(25);
		
		if(N.equals(four)){
			return 3;
		}else if(N.equals(six)){
			return 5;
		}else if(N.equals(eight) || N.equals(nine) || N.equals(ten) || N.equals(fifteen) || N.equals(sixteen) || N.equals(twentytwo)){
			return 7;
		}else if(N.equals(twelve)){
			return 11;
		}else if(N.equals(fourteen)){
			return 13;
		}else if(N.equals(twenty) || N.equals(twentyone)){
			return 19;
		}else if(N.equals(twentyfour) || N.equals(twentyfive)){
			return 23;
		}else if(N.subtract(BigInteger.ONE).mod(eight).equals(BigInteger.ZERO) && N.subtract(eight).isProbablePrime(1000000000)){
			return 14;
		}else{
			return 8;
		}
	}
	
	// シュミレーションして法則性を掴むべき. 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		/*
		for(int i = 2; i <= 10000; i++){
			final int sim_value = simulate(i);
			if(sim_value > 0){
				final int big_value = smart(BigInteger.valueOf(i));
				if(sim_value != big_value){
					System.out.printf("%05d : %d, %d\n", i, sim_value, big_value);
				}
			}
		}
		*/
		
		BigInteger N = new BigInteger(sc.next());
		
		System.out.println(smart(N));
		
	}

}

yukicoder

結果

テストケース

ソースコード