NO IMAGE

不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description
杭州人稱那些傻乎乎粘嗒嗒的人為62(音:laoer)。
杭州交通管理局經常會擴充一些的士車牌照,新近出來一個好訊息,以後上牌照,不再含有不吉利的數字了,這樣一來,就可以消除個別的士司機和乘客的心理障礙,更安全地服務大眾。
不吉利的數字為所有含有4或62的號碼。例如:
62315 73418 88914
都屬於不吉利號碼。但是,61152雖然含有6和2,但不是62連號,所以不屬於不吉利數字之列。
你的任務是,對於每次給出的一個牌照區間號,推斷出交管局今次又要實際上給多少輛新的士車上牌照了。
 
Input
輸入的都是整數對n、m(0<n≤m<1000000),如果遇到都是0的整數對,則輸入結束。
 
Output
對於每個整數對,輸出一個不含有不吉利數字的統計個數,該數值佔一行位置。
 
Sample Input
1 100
0 0
 
Sample Output
80

 

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int a[10];
int dp[10][2][2];
int dfs(int u, bool is6, bool have, bool limit)
{
if(u < 1)    return !have;
if(!limit && dp[u][is6][have] != -1)    return dp[u][is6][have];
int maxn = limit ? a[u] : 9;
int ret = 0;
for(int i=0; i<=maxn; i  ) {
ret  = dfs(u-1, i==6, have||i==4||(is6&&i==2), limit&&i==maxn);
}
if(!limit)    dp[u][is6][have] = ret;
return ret;
}
int f(int n)
{
int len=0;
while(n) {
a[  len] = n%10;
n /= 10;
}
return dfs(len, 0, 0, 1);
}
int main ()
{
int n, m;
memset(dp, -1, sizeof(dp));
while(scanf("%d%d", &n, &m) != EOF && (m|n)) {
printf("%d\n", f(m) - f(n-1));
}
return 0;
}