Submission #163718

---

Source Code Expand

using System;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Threading.Tasks;

class Program {

	static void Main(string[] args) {


		char[] cs = new char[] { ' ', ',' };
		string[] rl = Console.ReadLine().Split(cs);

		/*
		long staa = int.Parse(rl[0]);
		long enda = int.Parse(rl[1]);
		long count = 0;
		for (long i = staa; i <= enda; i++) {
			string str = i.ToString();
			for (int j = 0; j < str.Length; j++) {

				if (str[j] == '4' || str[j] == '9') {
					count++;
					break;
				}
			}
		}
		*/
		long sta = Calc.fun(long.Parse(rl[0]) - 1);
		long end = Calc.fun(long.Parse(rl[1]));
		//Console.WriteLine("真　答え："+count);
		Console.WriteLine(end - sta);
		return;
	}
}

class Calc {
	static long[,] dp;
	static public long fun(long n) {
		if (n == -1) { return 0; }
		string str=n.ToString();
		dp = new long[str.Length+1, 2];
		dp[str.Length,0]=1;
		dp[str.Length,1]=1;
		
			for (int j = 0; j <= (str[0]-'0'); j++) {
				if (j == 4 || j == 9) { continue; }
				if (j == str[0] - '0') {
					dp[0, 1] += cal(n,1,1);
					continue;
				}
				dp[0, 0] += cal(n,1,0);
			}
			return n + 1 - ( dp[0, 0] + dp[0, 1] );
	}


	static long cal(long n,int a ,int b) {
		if (dp[a, b] != 0) { return dp[a, b]; }
		if (b == 0) {
			dp[a, b] = cal(n, a + 1, 0) * 8;
		} else {// b=1
			for (int j = 0; j <= ( n.ToString()[a] - '0' ); j++) {
				if (j == 4 || j == 9) { continue; }
				if (j == n.ToString()[a] - '0') {
					dp[a, b] += cal(n, a + 1, b);
					continue;
				}
				dp[a, b] += cal(n, a + 1, 0);
			}
		}
		return dp[a, b];
	}
}

Submission Info

Judge Result