Submission #1436033


Source Code Expand

import java.util.Scanner;

/**
 * http://abc007.contest.atcoder.jp/tasks/abc007_4
 */
public class Main {
	
	private final static int MAX_SIZE = 19; 
	private final static long dp[][] = new long[MAX_SIZE][10];

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		sc.close();
		
		for(int s=0; s<MAX_SIZE; s++){
			for(int d=0; d<10; d++){
				if(s==0){
					dp[s][d] = d==4 || d==9 ? 1 : 0;
				}else{
					if( d==4 || d==9){
						dp[s][d] = (long) Math.pow(10,s);
					}else{
						for(int bd=0; bd<10; bd++){
							dp[s][d] += dp[s-1][bd];
						}
					}
				}
			}
			// System.out.println(s + ":" + Arrays.toString(dp[s]));
		}
		
		System.out.println(getCount(b)-getCount(a-1));

	}
	
	
	private static long getCount(long targetNum){
		long count = 0;
		String numStr = String.valueOf(targetNum);
		for(int i=numStr.length()-1; i>=0; i--){
			int num = numStr.charAt(numStr.length()-i-1) - '0';
			for(int d=0; d<num; d++){
				count += dp[i][d];
			}
			// System.out.println(num + ":" + count);
			if(num==4||num==9){
				if(i>0){
					count += Long.valueOf(numStr.substring(numStr.length()-i, numStr.length())) + 1;
				}else{
					count += 1;
				}
				break;
			}
			
		}
		return count;
	}

}

Submission Info

Submission Time
Task D - 禁止された数字
User namayaki
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 1354 Byte
Status AC
Exec Time 101 ms
Memory 23124 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 90 ms 21716 KB
subtask0_sample02.txt AC 89 ms 21716 KB
subtask0_sample03.txt AC 90 ms 21716 KB
subtask0_sample04.txt AC 91 ms 19540 KB
subtask1_01.txt AC 101 ms 19792 KB
subtask1_02.txt AC 91 ms 19668 KB
subtask1_03.txt AC 90 ms 21844 KB
subtask1_04.txt AC 91 ms 21844 KB
subtask1_05.txt AC 96 ms 21588 KB
subtask1_06.txt AC 89 ms 21972 KB
subtask1_07.txt AC 90 ms 19796 KB
subtask1_08.txt AC 91 ms 20948 KB
subtask1_09.txt AC 90 ms 19028 KB
subtask1_10.txt AC 90 ms 21204 KB
subtask1_11.txt AC 97 ms 21716 KB
subtask1_12.txt AC 92 ms 20948 KB
subtask1_13.txt AC 91 ms 21076 KB
subtask2_01.txt AC 91 ms 21204 KB
subtask2_02.txt AC 91 ms 18516 KB
subtask2_03.txt AC 90 ms 21844 KB
subtask2_04.txt AC 90 ms 21204 KB
subtask2_05.txt AC 90 ms 19924 KB
subtask2_06.txt AC 90 ms 19796 KB
subtask2_07.txt AC 91 ms 20692 KB
subtask2_08.txt AC 90 ms 19796 KB
subtask2_09.txt AC 90 ms 21844 KB
subtask2_10.txt AC 90 ms 19796 KB
subtask2_11.txt AC 91 ms 21716 KB
subtask2_12.txt AC 90 ms 19924 KB
subtask2_13.txt AC 92 ms 23124 KB
subtask2_14.txt AC 92 ms 21204 KB
subtask2_15.txt AC 89 ms 21844 KB
subtask2_16.txt AC 91 ms 20692 KB
subtask2_17.txt AC 92 ms 18516 KB
subtask2_18.txt AC 97 ms 19924 KB
subtask2_19.txt AC 91 ms 21716 KB
subtask2_20.txt AC 90 ms 17104 KB
subtask2_21.txt AC 94 ms 21844 KB
subtask2_22.txt AC 92 ms 21332 KB