Description
windy定义了一种windy数。相邻两个数字之差至少为2的正整数被称为windy数。windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

Input

包含两个整数，A B。

Output

包含一个整数。

Sample Input

1
1 10

Sample Output

1
9

Hint

20%的数据，满足 1 <= A <= B <= 1000000 。100%的数据，满足 1 <= A <= B <= 2000000000 。

分析

Success Text.
{:.success}

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define maxn 66
using namespace std;
typedef long long LL;
int spr[maxn];
LL f[maxn][maxn];
LL dfs(int x,int p,bool lim){
	if(!x) return 1;
	if(!lim && f[x][p]!=-1) return f[x][p];
	LL ans=0;
	int imax=lim?spr[x]:9;
	for(int i=0;i<=imax;i++){
		if(abs(i-p)<2) continue;
		if(i==0 && p==11) ans+=dfs(x-1,11,lim && i==imax);
		else ans+=dfs(x-1,i,lim && i==imax);
	}
	if(!lim) f[x][p]=ans;
	return ans;
}
LL res(int x){
	// spr[0] 存位数 
	memset(spr,0,sizeof(spr));
	while(x>0){
		spr[++spr[0]]=x%10;
		x/=10;
	} spr[spr[0]+1]=-1;
	memset(f,-1,sizeof(f));
	return dfs(spr[0],11,true);
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	int a,b; cin>>a>>b;
	cout<<res(b)-res(a-1);
	return 0;
}