A palindromic number or numeral palindrome is a ‘symmetrical’ number like 16461 that remains the same when its digits are reversed. In this problem you will be given two integers i j, you have to find the number of palindromic numbers between i and j (inclusive).
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case starts with a line containing two integers i j (0 ≤ i, j ≤ 1017).
Output
For each case, print the case number and the total number of palindromic numbers between i and j (inclusive).
Sample Input
4
1 10
100 1
1 1000
1 10000
Output for Sample Input
Case 1: 9
Case 2: 18
Case 3: 108
Case 4: 198
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[],tmp[];
ll dp[][][];
ll dfs(int start,int pos,int ok,bool limit)
{
if(pos<)
return ok;
if(!limit&&dp[pos][ok][start]!=-)
return dp[pos][ok][start];
ll ans=;
int up=limit?a[pos]:;
for(int d=; d<=up; ++d)
{
tmp[pos]=d;
if(start==pos&&d==)
ans+=dfs(start-,pos-,ok,limit&&d==up);
else if(ok&&pos<(start+)/)
ans+=dfs(start,pos-,tmp[start-pos]==d,limit&&d==up);
else
ans+=dfs(start,pos-,ok,limit&&d==up);
}
if(!limit)
dp[pos][ok][start]=ans;
return ans;
}
ll solve(ll x)
{
memset(a,,sizeof(a));
int cnt=;
while(x!=)
{
a[cnt++]=x%;
x/=;
}
return dfs(cnt-,cnt-,,);
}
int main()
{
memset(dp,-,sizeof(dp));
int t,cnt=;
scanf("%d",&t);
while(t--)
{
ll x,y;
scanf("%lld%lld",&x,&y);
if(x>y)
swap(x,y);
printf("Case %d: %lld\n",cnt++,solve(y)-solve(x-));
}
return ;
}