USTC 2015 dpテーマH邱先生は妹の数位dpを選びます.

邱先生が妹を選ぶ
Time Limit:20 Sec  メモリLimit:256 MB
タイトル接続
http://acm.uestc.edu.cn/#/contest/show/65
Description
邱先生がハンサムだということは誰でも知っていますから、彼を追いかける妹が多いです.
でも、邱先生はとても一途な人だと知っています.だから彼の心の中には一人しかいません.
そこで彼は彼を追いかける多くの妹の中から一つを選ぶことにしました.そこで、醤神は邱先生にアイデアを出しました.妹はすでにいくつか知っています.ちょうど彼女たちにlからrまでの番号を与えられます.妹一人には数字がありますが、r-l＋1人の妹がいます.
ソース神は、私たちは運の悪い女の子にはならないと言いました.ソース神はまた二つの数字62と4をあげました.もし妹の番号の中に62(連続していなければならない)か4があれば、彼は今あなたにlとrをあげます.どのぐらいの妹が第1ラウンドで残してくれますか?
wijキログラムのケーキは、Gorwinが左上(1,1)の格子から歩いて、右下(n,m)の格子に行きます.各ステップにおいて、Gorwinは右または下に行くことができます.すなわち、Gorwinは(i,j)に立っているとき、彼女は(i＋1,j)または(i,j＋1)に向かうことができます.Gorwinが一つの格子に着いたら、彼女はその格子の中のケーキを食べてもいいですか?食べないでもいいです.しかし、彼女は一部だけを食べてはいけません.彼女は胃がそんなに大きくないので、Kキロのケーキしか食べられません.今、Gorwinは左上に立っています.彼女はケーキ園の地図を見ています.道を探したいです.彼女が食べられるケーキの一番多い道を探しています.助けてください.
Input
入力したのは全部整数対l、r(0＜l≦r＜100000)で、もしすべて0の整数対が発生したら、入力は終了します.
Output
各グループのデータ出力が一行を占めています.lとr出力に対してどれぐらいの妹が第1ラウンドで除外されませんか?
Sample Input

1 100
0 0

Sample Output

80

HINT
 
題意
 
クイズ:
実はこの問題は数位dpです.要らないです.
コード:
 

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <ctime>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200001
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
/*

inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
*/
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
//**************************************************************************************
int dp[10][3];
int bit[10];
int n,m;

void init()
{
    dp[0][0]=1,dp[0][1]=0,dp[0][2]=0;
    for(int i=1;i<=9;i++)
    {
        dp[i][0]=dp[i-1][0]*9-dp[i-1][1];
        dp[i][1]=dp[i-1][0];
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1]+dp[i-1][0];
    }
}

int cal(int n)
{
    int temp=n;
    memset(bit,0,sizeof(bit));
    int len=0;
    while(n)
    {
        bit[++len]=n%10;
        n/=10;
    }
    bit[len+1]=0;
    int ans=0;
    bool flag=0;
    for(int i=len;i>=1;i--)
    {
        ans+=bit[i]*dp[i-1][2];
        if(flag)
            ans+=bit[i]*dp[i-1][0];
        else
        {
            if(bit[i]>6)
                ans+=dp[i-1][1];
            if(bit[i]>4)
                ans+=dp[i-1][0];
            if(bit[i+1]==6&&bit[i]>2)
                ans+=dp[i][1];
        }
        if(bit[i]==4||(bit[i+1]==6&&bit[i]==2))
            flag=1;
    }
    if(flag)
        ans++;
    return temp-ans;
}

int main()
{
    init();
    while(cin>>n>>m&&(n||m))
    {
        cout<<(cal(m)-cal(n-1))<<endl;
    }
    return 0;
}