Cerinta completa
Chloe is fascinated by prime numbers. She came across the number on a sign and, though the number is not prime, found some primes hiding in it by using the following rules:
- Every three consecutive digits sum to a prime:
- Every four consecutive digits sum to a prime:
- Every five consecutive digits sum to a prime:
You must answer queries, where each query consists of an integer, . For each , find and print the number of positive -digit numbers, modulo , that satisfy all three of Chloe’s rules (i.e., every three, four, and five consecutive digits sum to a prime).
Input Format
The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains an integer denoting the value of for a query.
Constraints
Output Format
For each query, print the number of -digit numbers satisfying Chloe’s rules, modulo , on a new line.
Sample Input 0
1
6
Sample Output 0
95
Explanation 0
There are six-digit numbers satisfying the property above, where the respective first and last ones are and .
Limbajul de programare folosit: java8
Cod:
import java.io.*;
import java.util.*;
public class Solution {
static final int MOD = 1_000_000_007;
static final boolean[] PRIME = new boolean[46];
static {
int[] p = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43};
for (int x : p) PRIME[x] = true;
}
private static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do { c = read(); } while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') { sign = -1; c = read(); }
int val = 0;
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sign;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int q = fs.nextInt();
int[] queries = new int[q];
int maxN = 0;
for (int i = 0; i < q; i++) {
queries[i] = fs.nextInt();
if (queries[i] > maxN) maxN = queries[i];
}
long[] ans = new long[Math.max(5, maxN + 1)];
ans[1] = 9;
ans[2] = 90;
long cnt3 = 0;
for (int a = 1; a <= 9; a++) {
for (int b = 0; b <= 9; b++) {
for (int c = 0; c <= 9; c++) {
if (PRIME[a + b + c]) cnt3++;
}
}
}
ans[3] = cnt3 % MOD;
// Build valid 4-digit states
int[] stateCode = new int[415];
int stateCnt = 0;
int[] map = new int[10000];
Arrays.fill(map, -1);
for (int x = 0; x < 10000; x++) {
int a = (x / 1000) % 10;
int b = (x / 100) % 10;
int c = (x / 10) % 10;
int d = x % 10;
if (PRIME[a + b + c] && PRIME[b + c + d] && PRIME[a + b + c + d]) {
map[x] = stateCnt;
stateCode[stateCnt++] = x;
}
}
int[] from = new int[2000];
int[] to = new int[2000];
int eCnt = 0;
for (int i = 0; i < stateCnt; i++) {
int x = stateCode[i];
int a = (x / 1000) % 10;
int b = (x / 100) % 10;
int c = (x / 10) % 10;
int d = x % 10;
for (int e = 0; e <= 9; e++) {
if (!PRIME[c + d + e]) continue;
if (!PRIME[b + c + d + e]) continue;
if (!PRIME[a + b + c + d + e]) continue;
int y = b * 1000 + c * 100 + d * 10 + e;
int j = map[y];
if (j >= 0) {
from[eCnt] = i;
to[eCnt] = j;
eCnt++;
}
}
}
long[] cur = new long[stateCnt];
long[] nxt = new long[stateCnt];
long cnt4 = 0;
for (int i = 0; i < stateCnt; i++) {
int x = stateCode[i];
int a = (x / 1000) % 10;
if (a != 0) {
cur[i] = 1;
cnt4++;
}
}
ans[4] = cnt4 % MOD;
for (int len = 5; len <= maxN; len++) {
Arrays.fill(nxt, 0);
for (int e = 0; e < eCnt; e++) {
int u = from[e], v = to[e];
long val = cur[u];
if (val == 0) continue;
long nv = nxt[v] + val;
if (nv >= MOD) nv -= MOD;
nxt[v] = nv;
}
long total = 0;
for (int i = 0; i < stateCnt; i++) {
total += nxt[i];
if (total >= MOD) total -= MOD;
}
ans[len] = total;
long[] tmp = cur;
cur = nxt;
nxt = tmp;
}
StringBuilder out = new StringBuilder();
for (int n : queries) {
out.append(ans[n] % MOD).append('\n');
}
System.out.print(out);
}
}
Scor obtinut: 1.0
Submission ID: 464619080
Link challenge: https://www.hackerrank.com/challenges/prime-digit-sums/problem