#include<stdio.h>
#include<string.h>
#define S 181
int q, A[S];
long long dp[19][S], l, r;
void init()
{
for(int k,i=0;i<S;++i)
{
A[i]=i;
while (A[i] > 9)
{
k=A[i],A[i]=0;
while(k)A[i]+=k%10,k/=10;
}
}
memset(dp, -1, sizeof dp);
}
char s[20];
long long calc(int i, int sum, int f)
{
if(sum < 0) return 0;
if(i==-1)return sum==0;
if (f && dp[i][sum] != -1)
return dp[i][sum];
long long ans = 0;
int high = f ? 9 : s[i] - '0';
for (int j = 0; j <= high; ++j)
ans += calc(i-1, sum - j, f || (j < high));
if(f) dp[i][sum] = ans;
return ans;
}
long long count_bounded(long long x)
{
long long z = 0;
sprintf(s, "%019lld", x);
for (int wa, l = 0, r = 18; l < r; ++l, --r)
wa = s[l], s[l] = s[r], s[r] = wa;
for (int i = 0; i < S; ++i) z += calc(18, i, 0) * A[i];
return z;
}
int main()
{
init();
scanf("%d",&q);
for (long long l, r; q--;)
scanf("%lld%lld", &l, &r),
printf("%lld\n",count_bounded(r) - count_bounded(l-1));
}
Compilation message
trol.c: In function 'main':
trol.c:54:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d",&q);
| ^~~~~~~~~~~~~~
trol.c:56:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%lld%lld", &l, &r),
| ^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
444 KB |
Output is correct |
| 2 |
Correct |
5 ms |
452 KB |
Output is correct |
| 3 |
Correct |
8 ms |
500 KB |
Output is correct |
| 4 |
Correct |
5 ms |
348 KB |
Output is correct |
| 5 |
Correct |
7 ms |
444 KB |
Output is correct |
