#include<bits/stdc++.h>
using namespace std;
long long ans[21][10],lst[21]={0,1};
void init(){
	for(int i=0;i<10;i++)ans[1][i]=1;
	for(int i=2;i<21;i++){
		for(int j=0;j<10;j++)for(int k=0;k<10;k++){
			if(abs(j-k)<2)continue;
			ans[i][j]+=ans[i-1][k];
		}
		lst[i]=ans[i][0];
	}
	for(int i=2;i<21;i++){
		lst[i]+=lst[i-1]+ans[i-1][1];
	}
}
long long solve(long long k){
	if(!k)return 1;
	int num[21]={123123123},tot=0;
	bool alw=1;
	while(k){
		num[++tot]=k%10;
		if(abs(num[tot-1]-num[tot])<2)alw=0;
		k/=10;
	}
	long long sum=0,lstx=-2;
	for(int i=tot;i>=1;i--){
		for(int j=0;j<num[i];j++){
			if(abs(j-lstx)<2)continue;
			sum+=(j==0&&i==tot?lst[i]:ans[i][j]);
		}
		if(abs(num[i]-lstx)<2)break;
		if(i==1){
			if(abs(num[i]-lstx)>=2&&alw)sum+=ans[i][num[i]];
		}
		lstx=num[i];
	}
	return sum;
}
int main(int argc,char** argv){	
	init();
	long long a,b;
	cin>>a>>b;
//	a=stoi(argv[1]),b=stoi(argv[2]);
	cout<<solve(max(a,b))-solve(min(a,b)-1);
	return 0;
	//debug
//	cout<<"\n\n\nDEBUG:\n  0   1   2   3   4   5   6   7   8   9\n---------------------------------------\n";
//	for(int i=1;i<=5;i++){
//		for(int j=0;j<10;j++){
//			cout<<setw(3)<<setfill(' ')<<ans[i][j]<<" ";
//		} 
//		cout<<endl;
//	} 
}

0 comments

No comments so far...

Information

ID
167
Time
1000ms
Memory
256MiB
Difficulty
9
Tags
# Submissions
41
Accepted
5
Uploaded By