Submission #2667877
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 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 { public void solve(int testNumber, InputReader in, PrintWriter out) { long a = in.nextLong(), b = in.nextLong(); String sa = String.valueOf(a-1); String sb = String.valueOf(b); out.println(b-a+1 - (f(sb)-f(sa))); } long f(String ss) { char[] s = ss.toCharArray(); int len = s.length; long[][] dp = new long[30][2]; dp[0][0] = 1; for (int i = 0; i < len; i++) { int d = s[i]-'0'; for (int j = 0; j < 2; j++) { int m = (j == 1 ? 9 : d); for (int k = 0; k <= m; k++) { if (k == 4 || k == 9) continue; dp[i+1][j | (k == m ? 0 : 1)] += dp[i][j]; } } } return dp[len][0]+dp[len][1]; } } 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 long[] nextLongArray(int n) { long[] res = new long[n]; for (int i = 0; i < n; i++) { res[i] = nextLong(); } 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 | 2627 Byte |
Status | AC |
Exec Time | 86 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 | 69 ms | 21588 KB |
subtask0_sample02.txt | AC | 71 ms | 19156 KB |
subtask0_sample03.txt | AC | 70 ms | 21460 KB |
subtask0_sample04.txt | AC | 72 ms | 19028 KB |
subtask1_01.txt | AC | 69 ms | 21460 KB |
subtask1_02.txt | AC | 69 ms | 19412 KB |
subtask1_03.txt | AC | 71 ms | 19156 KB |
subtask1_04.txt | AC | 71 ms | 19028 KB |
subtask1_05.txt | AC | 70 ms | 18516 KB |
subtask1_06.txt | AC | 71 ms | 21588 KB |
subtask1_07.txt | AC | 70 ms | 19412 KB |
subtask1_08.txt | AC | 71 ms | 21460 KB |
subtask1_09.txt | AC | 70 ms | 18772 KB |
subtask1_10.txt | AC | 68 ms | 17620 KB |
subtask1_11.txt | AC | 69 ms | 20180 KB |
subtask1_12.txt | AC | 69 ms | 19412 KB |
subtask1_13.txt | AC | 71 ms | 20820 KB |
subtask2_01.txt | AC | 71 ms | 19028 KB |
subtask2_02.txt | AC | 72 ms | 22868 KB |
subtask2_03.txt | AC | 71 ms | 21204 KB |
subtask2_04.txt | AC | 70 ms | 19284 KB |
subtask2_05.txt | AC | 70 ms | 18260 KB |
subtask2_06.txt | AC | 70 ms | 18516 KB |
subtask2_07.txt | AC | 86 ms | 19028 KB |
subtask2_08.txt | AC | 71 ms | 18644 KB |
subtask2_09.txt | AC | 71 ms | 18772 KB |
subtask2_10.txt | AC | 70 ms | 19668 KB |
subtask2_11.txt | AC | 72 ms | 21204 KB |
subtask2_12.txt | AC | 69 ms | 18644 KB |
subtask2_13.txt | AC | 70 ms | 21332 KB |
subtask2_14.txt | AC | 69 ms | 19412 KB |
subtask2_15.txt | AC | 72 ms | 23380 KB |
subtask2_16.txt | AC | 69 ms | 17620 KB |
subtask2_17.txt | AC | 70 ms | 19412 KB |
subtask2_18.txt | AC | 70 ms | 21332 KB |
subtask2_19.txt | AC | 71 ms | 21460 KB |
subtask2_20.txt | AC | 70 ms | 20308 KB |
subtask2_21.txt | AC | 71 ms | 19540 KB |
subtask2_22.txt | AC | 68 ms | 17616 KB |