AcWing 1085. 不要62(java)
原题链接
中等
作者:
pen999
,
2020-07-31 10:50:15
,
所有人可见
,
阅读 372
import java.io.*;
import java.util.*;
public class Main {
private static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
String tt=br.readLine().replaceAll(" "," ");
String[] s = tt.split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
if (n == 0 && m == 0)
break;
init();
System.out.println(count(m) - count(n - 1));
}
}
private static void init() {
dp = new int[11][10];
for (int i = 0; i < 10; i++) {
if (i == 4)
dp[1][4] = 0;
else
dp[1][i] = 1;
}
for (int i = 2; i < 11; i++) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
if ((j != 4 && k != 4))
dp[i][j] += dp[i - 1][k];
if (j == 6 && k == 2)
dp[i][j] -= dp[i - 1][k];
}
}
}
}
private static int count(int x) {
if (x == 0)
return 1;
List<Integer> list = new ArrayList<>();
while (x > 0) {
list.add(x % 10);
x /= 10;
}
int ans = 0;
int last = 0;
for (int i = list.size() - 1; i >= 0; i--) {
int t = list.get(i);
if (last == 4)
break;
for (int j = 0; j < t; j++) {
if (j == 4 || (last == 6 && j == 2))
continue;
ans += dp[i + 1][j];
}
if (t == 4 || (t == 2 && last == 6))
break;
last = t;
if (i == 0)
ans++;
}
return ans;
}
}