結果

問題 No.6 使いものにならないハッシュ
ユーザー htensai
提出日時 2020-01-15 10:45:00
言語 Java11
(openjdk 11.0.5)
結果
AC  
実行時間 216 ms
コード長 2,357 Byte
コンパイル時間 2,396 ms
使用メモリ 35,812 KB
最終ジャッジ日時 2020-01-15 10:45:10

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt AC 132 ms
33,872 KB
02.txt AC 128 ms
33,888 KB
03.txt AC 212 ms
35,812 KB
04.txt AC 152 ms
34,556 KB
05.txt AC 156 ms
34,648 KB
06.txt AC 156 ms
34,924 KB
07.txt AC 180 ms
34,904 KB
08.txt AC 164 ms
34,880 KB
09.txt AC 176 ms
35,116 KB
10.txt AC 152 ms
34,612 KB
99_system_test1.txt AC 156 ms
34,876 KB
system_test1.txt AC 188 ms
35,264 KB
system_test2.txt AC 148 ms
34,448 KB
system_test3.txt AC 160 ms
34,536 KB
system_test4.txt AC 184 ms
35,232 KB
system_test5.txt AC 176 ms
34,732 KB
system_test6.txt AC 200 ms
35,348 KB
system_test7.txt AC 216 ms
35,560 KB
system_test8.txt AC 196 ms
35,324 KB
system_test9.txt AC 192 ms
35,016 KB
system_test10.txt AC 144 ms
34,532 KB
system_test11.txt AC 196 ms
35,088 KB
system_test12.txt AC 196 ms
35,280 KB
system_test13.txt AC 192 ms
35,092 KB
system_test14.txt AC 176 ms
34,764 KB
system_test15.txt AC 200 ms
35,580 KB
system_test16.txt AC 192 ms
35,316 KB
system_test17.txt AC 168 ms
34,916 KB
system_test18.txt AC 208 ms
35,428 KB
system_test19.txt AC 204 ms
35,480 KB
system_test20.txt AC 192 ms
35,304 KB
テストケース一括ダウンロード

ソースコード

diff #
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        Prime[] used = new Prime[10];
        TreeSet<Prime> primes = new TreeSet<Prime>();
        int max = 0;
        int maxNumber = 0;
        for (int i = k; i <= n; i++) {
            if (!isPrime(i)) {
                continue;
            }
            Prime p = new Prime(i);
            if (used[p.hashCode()] == null) {
                used[p.hashCode()] = p;
                primes.add(p);
            } else {
                Prime x = used[p.hashCode()];
                used[p.hashCode()] = null;
                while (primes.lower(x) != null) {
                    Prime tmp = primes.lower(x);
                    primes.remove(x);
                    x = tmp;
                    used[x.hashCode()] = null;
                }
                primes.remove(x);
                used[p.hashCode()] = p;
                primes.add(p);
            }
            if (max <= primes.size()) {
                max = primes.size();
                maxNumber = primes.first().number;
            }
        }
        System.out.println(maxNumber);
    }
    
    static class Prime implements Comparable<Prime> {
        int number;
        int hash;
        
        public Prime(int number) {
            this.number = number;
            this.hash = getHash(number);
        }
        
        public int hashCode() {
            return hash;
        }
        
        public boolean equals(Object o) {
            Prime another = (Prime) o;
            return number == another.number;
        }
        
        public int compareTo(Prime another) {
            return number - another.number;
        }
        
        private int getHash(int x) {
            while (x >= 10) {
                int y = x;
                x = 0;
                while (y > 0) {
                    x += y % 10;
                    y /= 10;
                }
            }
            return x;
        }
    }
    
    static boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}
0