#include<bits/stdc++.h>
using namespace std ;
const int unvisited = -1 ;
long long dp[20][11][11][2] ;
long long calc(string &s , int siz , int pos , int prev1 , int prev2 , int smaller)
{
if(pos>=siz) return 1 ;
if(dp[pos][prev1][prev2][smaller]!=unvisited) return dp[pos][prev1][prev2][smaller] ;
int mx = s[pos] - '0' , cur = s[pos] - '0' ;
if(smaller) mx = 9 ;
long long res = 0 ;
for(int i = 0 ; i <= mx ; ++i)
{
if(i==prev1 || i==prev2) continue ;
if(cur>i) res += calc(s,siz,pos+1,prev2,i,1) ;
else res += calc(s,siz,pos+1,prev2,i,smaller) ;
}
return dp[pos][prev1][prev2][smaller] = res ;
}
void clean()
{
for(int i = 0 ; i < 20 ; ++i)
{
for(int j = 0 ; j < 11 ; ++j)
{
for(int k = 0 ; k < 11 ; ++k)
{
dp[i][j][k][0] = unvisited ;
dp[i][j][k][1] = unvisited ;
}
}
}
}
int main()
{
long long A , B , zero = 0 ;
scanf("%lld%lld",&A,&B) ;
if(A) --A ;
else zero = 1 ;
string a = to_string(A) , b = to_string(B) ;
int a_siz = a.size() , b_siz = b.size() ;
clean() ;
long long fst = calc(a,a_siz,0,0,10,0) ;
for(int i = 1 ; i < a_siz ; ++i)
{
fst += calc(a,a_siz,i,0,10,1) ;
}
clean() ;
long long sst = calc(b,b_siz,0,0,10,0) ;
for(int i = 1 ; i < b_siz ; ++i)
{
sst += calc(b,b_siz,i,0,10,1) ;
}
printf("%lld\n",sst-fst+zero) ;
return 0 ;
}
Compilation message
numbers.cpp: In function 'int main()':
numbers.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
46 | scanf("%lld%lld",&A,&B) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
0 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
372 KB |
Output is correct |
| 20 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
0 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
0 ms |
364 KB |
Output is correct |
| 13 |
Correct |
0 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
364 KB |
Output is correct |
| 21 |
Correct |
1 ms |
364 KB |
Output is correct |
| 22 |
Correct |
1 ms |
364 KB |
Output is correct |
| 23 |
Correct |
1 ms |
364 KB |
Output is correct |
| 24 |
Correct |
1 ms |
364 KB |
Output is correct |
| 25 |
Correct |
1 ms |
364 KB |
Output is correct |
| 26 |
Correct |
1 ms |
364 KB |
Output is correct |
| 27 |
Correct |
1 ms |
364 KB |
Output is correct |
| 28 |
Correct |
1 ms |
364 KB |
Output is correct |
| 29 |
Correct |
1 ms |
364 KB |
Output is correct |
| 30 |
Correct |
1 ms |
364 KB |
Output is correct |
| 31 |
Correct |
1 ms |
364 KB |
Output is correct |
| 32 |
Correct |
1 ms |
364 KB |
Output is correct |
| 33 |
Correct |
1 ms |
364 KB |
Output is correct |
| 34 |
Correct |
1 ms |
364 KB |
Output is correct |
| 35 |
Correct |
1 ms |
364 KB |
Output is correct |
| 36 |
Correct |
1 ms |
364 KB |
Output is correct |
| 37 |
Correct |
1 ms |
364 KB |
Output is correct |
| 38 |
Correct |
1 ms |
364 KB |
Output is correct |
| 39 |
Correct |
1 ms |
364 KB |
Output is correct |
| 40 |
Correct |
1 ms |
364 KB |
Output is correct |
| 41 |
Correct |
1 ms |
364 KB |
Output is correct |
| 42 |
Correct |
1 ms |
364 KB |
Output is correct |
| 43 |
Correct |
1 ms |
364 KB |
Output is correct |
| 44 |
Correct |
1 ms |
364 KB |
Output is correct |
| 45 |
Correct |
1 ms |
364 KB |
Output is correct |
