Submission #3768543
Source Code Expand
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TaskX solver = new TaskX();
solver.solve(1, in, out);
out.close();
}
static int INF = 1 << 30;
static long LINF = 1L << 55;
static int MOD = 1000000007;
static int[] mh4 = { 0, -1, 1, 0 };
static int[] mw4 = { -1, 0, 0, 1 };
static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };
static class TaskX {
long[][][] memo;
public void solve(int testNumber, InputReader in, PrintWriter out) {
char[] s = String.valueOf(in.nextLong()-1).toCharArray();
char[] t = in.nextString().toCharArray();
memo = initMemo(s);
long sc = f(0, 0, 1, s);
memo = initMemo(t);
long tc = f(0, 0, 1, t);
out.println(tc - sc);
}
long f(int digit, int used, int tight, char[] ss) {
if (digit == ss.length) return used == 1 ? 1 : 0;
if (memo[digit][used][tight] != -1) {
return memo[digit][used][tight];
}
long ret = 0;
int d = ss[digit] - '0';
for (int e = 0; e <= (tight == 1 ? d : 9) ; e++) {
int bool = (used == 1 || e == 4 || e == 9) ? 1 : 0;
ret += f(digit + 1, bool, tight == 1 && e == d ? 1 : 0, ss);
}
return memo[digit][used][tight] = ret;
}
long[][][] initMemo(char[] s) {
long[][][] ret = new long[s.length][2][2];
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
ret[i][j][k] = -1;
}
}
}
return ret;
}
}
static class InputReader {
BufferedReader in;
StringTokenizer tok;
public String nextString() {
while (!tok.hasMoreTokens()) {
try {
tok = new StringTokenizer(in.readLine(), " ");
} catch (IOException e) {
throw new InputMismatchException();
}
}
return tok.nextToken();
}
public int nextInt() {
return Integer.parseInt(nextString());
}
public long nextLong() {
return Long.parseLong(nextString());
}
public double nextDouble() {
return Double.parseDouble(nextString());
}
public int[] nextIntArray(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}
public int[] nextIntArrayDec(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt() - 1;
}
return res;
}
public int[] nextIntArray1Index(int n) {
int[] res = new int[n + 1];
for (int i = 0; i < n; i++) {
res[i + 1] = nextInt();
}
return res;
}
public long[] nextLongArray(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong();
}
return res;
}
public long[] nextLongArrayDec(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong() - 1;
}
return res;
}
public long[] nextLongArray1Index(int n) {
long[] res = new long[n + 1];
for (int i = 0; i < n; i++) {
res[i + 1] = nextLong();
}
return res;
}
public double[] nextDoubleArray(int n) {
double[] res = new double[n];
for (int i = 0; i < n; i++) {
res[i] = nextDouble();
}
return res;
}
public InputReader(InputStream inputStream) {
in = new BufferedReader(new InputStreamReader(inputStream));
tok = new StringTokenizer("");
}
}
}
Submission Info
Submission Time |
|
Task |
D - 禁止された数字 |
User |
tutuz |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
100 |
Code Size |
3893 Byte |
Status |
AC |
Exec Time |
88 ms |
Memory |
23380 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask2 |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
74 ms |
18260 KB |
subtask0_sample02.txt |
AC |
75 ms |
22356 KB |
subtask0_sample03.txt |
AC |
74 ms |
18388 KB |
subtask0_sample04.txt |
AC |
76 ms |
20564 KB |
subtask1_01.txt |
AC |
73 ms |
20820 KB |
subtask1_02.txt |
AC |
72 ms |
23124 KB |
subtask1_03.txt |
AC |
72 ms |
18772 KB |
subtask1_04.txt |
AC |
74 ms |
23380 KB |
subtask1_05.txt |
AC |
74 ms |
20820 KB |
subtask1_06.txt |
AC |
74 ms |
18388 KB |
subtask1_07.txt |
AC |
75 ms |
22100 KB |
subtask1_08.txt |
AC |
76 ms |
20820 KB |
subtask1_09.txt |
AC |
76 ms |
19028 KB |
subtask1_10.txt |
AC |
75 ms |
20820 KB |
subtask1_11.txt |
AC |
75 ms |
18900 KB |
subtask1_12.txt |
AC |
75 ms |
19284 KB |
subtask1_13.txt |
AC |
74 ms |
21204 KB |
subtask2_01.txt |
AC |
74 ms |
19924 KB |
subtask2_02.txt |
AC |
74 ms |
19412 KB |
subtask2_03.txt |
AC |
73 ms |
19028 KB |
subtask2_04.txt |
AC |
74 ms |
19284 KB |
subtask2_05.txt |
AC |
76 ms |
23380 KB |
subtask2_06.txt |
AC |
75 ms |
18772 KB |
subtask2_07.txt |
AC |
72 ms |
21076 KB |
subtask2_08.txt |
AC |
73 ms |
19412 KB |
subtask2_09.txt |
AC |
73 ms |
20052 KB |
subtask2_10.txt |
AC |
74 ms |
18772 KB |
subtask2_11.txt |
AC |
76 ms |
20564 KB |
subtask2_12.txt |
AC |
72 ms |
22996 KB |
subtask2_13.txt |
AC |
73 ms |
19284 KB |
subtask2_14.txt |
AC |
74 ms |
19284 KB |
subtask2_15.txt |
AC |
75 ms |
19668 KB |
subtask2_16.txt |
AC |
75 ms |
19028 KB |
subtask2_17.txt |
AC |
73 ms |
20308 KB |
subtask2_18.txt |
AC |
88 ms |
19028 KB |
subtask2_19.txt |
AC |
75 ms |
18260 KB |
subtask2_20.txt |
AC |
75 ms |
19156 KB |
subtask2_21.txt |
AC |
75 ms |
20052 KB |
subtask2_22.txt |
AC |
76 ms |
19668 KB |