Submission #2670743


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.Arrays;
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 {

		long[][] memo;
		char[] sa;
		char[] sb;

		public void solve(int testNumber, InputReader in, PrintWriter out) {

			long a = in.nextLong(), b = in.nextLong();
			sa = String.valueOf(a-1).toCharArray();
			sb = String.valueOf(b).toCharArray();

			out.println(b-a+1-dfs(0, 1, sb, true)+dfs(0, 1, sa, true));

		}

		long dfs(int i, int tight, char[] s, boolean isFirst) {
			if (isFirst) {
				memo = new long[20][2];
				for (int j = 0; j < 20; j++) {
					Arrays.fill(memo[j], -1);
				}
			}
			if (memo[i][tight] >= 0) {
				return memo[i][tight];
			}
			if (i == s.length) return 1;

			long ret = 0;
			int d = s[i]-'0';
			for (int e = 0; e <= (tight == 1 ? d : 9); e++) {
				if (e == 4 || e == 9) continue;
				ret += dfs(i+1, tight == 1 && d == e ? 1 : 0, s, false);
			}

			return memo[i][tight] = 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 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 2813 Byte
Status AC
Exec Time 72 ms
Memory 23380 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 4
AC × 16
AC × 39
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 70 ms 17620 KB
subtask0_sample02.txt AC 70 ms 18772 KB
subtask0_sample03.txt AC 72 ms 19284 KB
subtask0_sample04.txt AC 70 ms 20564 KB
subtask1_01.txt AC 71 ms 21204 KB
subtask1_02.txt AC 70 ms 21460 KB
subtask1_03.txt AC 72 ms 23380 KB
subtask1_04.txt AC 71 ms 19412 KB
subtask1_05.txt AC 71 ms 21332 KB
subtask1_06.txt AC 70 ms 21332 KB
subtask1_07.txt AC 70 ms 19412 KB
subtask1_08.txt AC 70 ms 19156 KB
subtask1_09.txt AC 71 ms 19028 KB
subtask1_10.txt AC 71 ms 19668 KB
subtask1_11.txt AC 70 ms 17748 KB
subtask1_12.txt AC 70 ms 19540 KB
subtask1_13.txt AC 71 ms 17876 KB
subtask2_01.txt AC 69 ms 18516 KB
subtask2_02.txt AC 70 ms 18772 KB
subtask2_03.txt AC 71 ms 18004 KB
subtask2_04.txt AC 71 ms 19668 KB
subtask2_05.txt AC 71 ms 21332 KB
subtask2_06.txt AC 71 ms 18516 KB
subtask2_07.txt AC 72 ms 18900 KB
subtask2_08.txt AC 70 ms 19284 KB
subtask2_09.txt AC 70 ms 21460 KB
subtask2_10.txt AC 72 ms 19284 KB
subtask2_11.txt AC 70 ms 19668 KB
subtask2_12.txt AC 71 ms 19668 KB
subtask2_13.txt AC 71 ms 18772 KB
subtask2_14.txt AC 71 ms 18900 KB
subtask2_15.txt AC 71 ms 21460 KB
subtask2_16.txt AC 70 ms 19412 KB
subtask2_17.txt AC 70 ms 21460 KB
subtask2_18.txt AC 72 ms 18644 KB
subtask2_19.txt AC 71 ms 18260 KB
subtask2_20.txt AC 72 ms 21076 KB
subtask2_21.txt AC 71 ms 19540 KB
subtask2_22.txt AC 71 ms 17876 KB