Good Numbers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5241 Accepted Submission(s): 1658
Problem Description If we sum up every digit of a number and the result can be exactly divided by 10, we say this number is a good number.
You are required to count the number of good numbers in the range from A to B, inclusive.
Input The first line has a number T (T <= 10000) , indicating the number of test cases.
Each test case comes with a single line with two numbers A and B (0 <= A <= B <= 10 18).
Output For test case X, output "Case #X: " first, then output the number of good numbers in a single line.
Sample Input
2
1 10
1 20
Sample Output
Case #1: 0
Case #2: 1
Hint
The answer maybe very large, we recommend you to use long long instead of int.
Source 2013 ACM/ICPC Asia Regional Online —— Warmup2 想法：對每位目前位%10，在dfs周遊 代碼：
#include<stdio.h>
#include<string.h>
typedef long long ll;
ll dp[20][105];
int a[20];
ll dfs(int pos,int sum,bool limit)
{
if(pos==-1) return sum==0;
if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
int up=limit?a[pos]:9;
ll tmp=0;
for(int i=0;i<=up;i++)
{
tmp+=dfs(pos-1,(sum+i)%10,limit&&(i==up));//
}
if(!limit) dp[pos][sum]=tmp;
return tmp;
}
ll solve(ll x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,0,1);
}
int main()
{
int T,ws=1;
memset(dp,-1,sizeof(dp));
scanf("%d",&T);
while(T--)
{
ll n,m;
scanf("%lld %lld",&n,&m);
printf("Case #%d: %lld\n",ws++,solve(m)-solve(n-1));
}
return 0;
}