#include<bits/stdc++.h>
using namespace std;
string a,b;
long long dp[25][15][15][3][3][3];
long long f(int x,int last,int llast,int on,int of,int tk)
{
if(x==b.size())return 1;
if(dp[x][last][llast][on][of][tk]!=-1)return dp[x][last][llast][on][of][tk];
long long ans=0;
for(int i=0;i<=9;i++)
{
int oon=on,oof=of,tkk=tk;
if(i)tkk=1;
char dj='0'+i;
if(a[x]<dj)oon=0;
if(dj<b[x])oof=0;
if(on&&a[x]>dj)continue;
if(of&&dj>b[x])continue;
if(tk)
{
if(last==i||llast==i)continue;
}
if(tkk==0)ans+=f(x+1,10,10,oon,oof,tkk);
else ans+=f(x+1,i,last,oon,oof,tkk);
}
return dp[x][last][llast][on][of][tk]=ans;
}
int main()
{
memset(dp,-1,sizeof dp);
cin>>a>>b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
while(a.size()!=20)a.push_back('0');
while(b.size()!=20)b.push_back('0');
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
cout<<f(0,10,10,1,1,0);
}
Compilation message
numbers.cpp: In function 'long long int f(int, int, int, int, int, int)':
numbers.cpp:7:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(x==b.size())return 1;
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1552 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1560 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 16 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 17 |
Correct |
6 ms |
1532 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 19 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 20 |
Correct |
5 ms |
1528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1532 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 16 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 17 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 19 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 20 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 21 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 22 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 23 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 24 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 25 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 26 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 27 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 28 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 29 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 30 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 31 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 32 |
Correct |
5 ms |
1580 KB |
Output is correct |
| 33 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 34 |
Correct |
6 ms |
1552 KB |
Output is correct |
| 35 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 36 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 37 |
Correct |
5 ms |
1532 KB |
Output is correct |
| 38 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 39 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 40 |
Correct |
5 ms |
1528 KB |
Output is correct |
| 41 |
Correct |
7 ms |
1656 KB |
Output is correct |
| 42 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 43 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 44 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 45 |
Correct |
6 ms |
1528 KB |
Output is correct |
