結果
問題 | No.12 限定された素数 |
ユーザー | SugihaM |
提出日時 | 2020-04-29 18:12:12 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 119 ms / 5,000 ms |
コード長 | 1,838 bytes |
コンパイル時間 | 10,728 ms |
コンパイル使用メモリ | 241,492 KB |
実行使用メモリ | 16,896 KB |
最終ジャッジ日時 | 2024-05-06 19:40:01 |
合計ジャッジ時間 | 13,608 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 59 ms
16,896 KB |
testcase_01 | AC | 60 ms
16,896 KB |
testcase_02 | AC | 59 ms
16,896 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 60 ms
16,896 KB |
testcase_05 | AC | 65 ms
16,896 KB |
testcase_06 | AC | 74 ms
16,896 KB |
testcase_07 | AC | 82 ms
16,896 KB |
testcase_08 | AC | 61 ms
16,896 KB |
testcase_09 | AC | 59 ms
16,896 KB |
testcase_10 | AC | 60 ms
16,896 KB |
testcase_11 | AC | 119 ms
16,896 KB |
testcase_12 | AC | 83 ms
16,896 KB |
testcase_13 | AC | 67 ms
16,896 KB |
testcase_14 | AC | 61 ms
16,896 KB |
testcase_15 | AC | 67 ms
16,896 KB |
testcase_16 | AC | 78 ms
16,896 KB |
testcase_17 | AC | 58 ms
16,896 KB |
testcase_18 | AC | 58 ms
16,896 KB |
testcase_19 | AC | 59 ms
16,896 KB |
testcase_20 | AC | 59 ms
16,896 KB |
testcase_21 | AC | 59 ms
16,896 KB |
testcase_22 | AC | 61 ms
16,896 KB |
testcase_23 | AC | 58 ms
16,896 KB |
testcase_24 | AC | 59 ms
16,896 KB |
testcase_25 | AC | 62 ms
16,896 KB |
ソースコード
package main import ( "bufio" "fmt" "os" "strconv" ) var sc = bufio.NewScanner(os.Stdin) func Scanner() string { sc.Scan() return sc.Text() } func main() { buf := make([]byte, 0) sc.Buffer(buf, 100000007) sc.Split(bufio.ScanWords) inf := 5000000 n, _ := strconv.Atoi(Scanner()) a := make([]bool, 10) num := 0 for i := 0; i < n; i++ { num, _ = strconv.Atoi(Scanner()) a[num] = true } if n == 10 { fmt.Println(4999999) return } p := prime(5000000) var max, min int ans := -1 for i := 0; i < len(p); i++ { if !judge(a, p[i]) { continue } else { if i == 0 { min = 1 } else { min = p[i-1] + 1 } } for j := i; j < len(p); j++ { if !judge(a, p[j]) { num = j break } if j+1 >= len(p) { max = inf } else { max = p[j+1] - 1 } } count := make([]int, 10) for k := i; k < num; k++ { add(count, p[k]) } if !judge2(a, count) { continue } ans = big(ans, max-min) } fmt.Println(ans) } func prime(n int) []int { notprime := make([]bool, n+1) prime := make([]int, 0) notprime[0] = true notprime[1] = true for i := 2; i <= n; i++ { if notprime[i] { continue } for j := 2 * i; j <= n; j += i { notprime[j] = true } } for i, j := range notprime { if !j { prime = append(prime, i) } } return prime } func judge(a []bool, n int) bool { count := make([]int, 10) add(count, n) for i := 0; i < 10; i++ { if !a[i] && count[i] > 0 { return false } } return true } func judge2(a []bool, count []int) bool { for i := 0; i < 10; i++ { if !a[i] && count[i] > 0 { return false } else if a[i] && count[i] == 0 { return false } } return true } func add(count []int, n int) { for n > 0 { count[n%10]++ n /= 10 } } func big(x int, y int) int { if x >= y { return x } else { return y } }