odd-even number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*10^18).
Input
First line a t,then t cases.every line contains two integers L and R.
Output
Print the output for each case on one line in the format as shown below.
Sample Input
2
1 100
110 220
Sample Output
Case #1: 29
Case #2: 36
Source
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cmath> #include<string> #include<queue> #include<algorithm> #include<stack> #include<cstring> #include<vector> #include<list> #include<set> #include<map> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-4 #define bug(x) cout<<"bug"<<x<<endl; const int N=2e3+10,M=9e3+10,inf=2147483647,mod=1e9+7; const ll INF=1e18+10; ll f[20][3][20][3],bit[20]; ll dp(int pos,int pre,int now,int k,int flag,int p) { //cout<<pos<<" "<<pre<<" "<<now<<" "<<k<<endl; if(pos==0)return (pre%2!=now%2&&k==0); if(flag&&f[pos][pre][now][k]!=-1)return f[pos][pre][now][k]; int x=flag?9:bit[pos]; ll ans=0; for(int i=0;i<=x;i++) { if(!p&&!i) ans+=dp(pos-1,1,0,0,flag||i<x,p||i); else { if(pre%2==i%2) ans+=dp(pos-1,i%2,now+1,k,flag||i<x,p||i); else { if(now%2!=pre%2) ans+=dp(pos-1,i%2,1,k,flag||i<x,p||i); else ans+=dp(pos-1,i%2,1,1,flag||i<x,p||i); } } } if(flag)f[pos][pre][now][k]=ans; return ans; } ll getans(ll x) { int len=0; while(x) { bit[++len]=x%10; x/=10; } return dp(len,1,0,0,0,0); } int main() { int T,cas=1; memset(f,-1,sizeof(f)); scanf("%d",&T); while(T--) { ll l,r; scanf("%lld%lld",&l,&r); printf("Case #%d: %lld ",cas++,getans(r)-getans(l-1)); } return 0; }