#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
//#define endl "\n"
const ll maxn=1e6+50;
const ll mod =998244353 ;
const ll base=3e18;
ll b[100];
ll dp[100][100][100][5];
ll dp1[100][100][100][5];
ll cnt1;
ll dem(ll p)
{
ll cnt=0;
while (p)
{
cnt++;
p/=10;
}
return cnt;
}
ll dem1=0;
ll dosth(ll id,ll nw1,ll nw2,ll h)
{
if (dp[id][nw1][nw2][h]!=-1)
{
return dp[id][nw1][nw2][h];
}
if (id==cnt1) return dp[id][nw1][nw2][h]=1;
ll t=0;
if (id==0)
{
t=t+dosth(id+1,10,10,1);
}
for (int i=0;i<=9;i++)
{
if (id==0&&i==0) continue;
if (!h&&b[id+1]<i) continue;
if (i==nw1||i==nw2) continue;
t=t+dosth(id+1,nw2,i,h|(b[id+1]>i));
}
dem1++;
// dp1[id][nw1][nw2][h]++;
// cout <<id<<" "<<nw1<<" "<<nw2<<" "<<h<<" "<<dem1<<" "<<dp1[id][nw1][nw2][h]<<endl;
return dp[id][nw1][nw2][h]=t;
}
ll cntpp(ll a)
{
if (a<0) return 0;
cnt1 =dem(a);
ll h= cnt1;
memset(dp,-1,sizeof(dp));
while (a)
{
b[h]=(a%10);
a/=10;
h--;
}
/*for (int i=1;i<=cnt1;i++)
{
cout <<b[i]<<endl;
}*/
return dosth(0,10,10,0);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
/*if (fopen("p.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}*/
ll a, b;
cin>> a>> b;
cout <<cntpp(b)-cntpp(a-1);
// cout <<cntpp(a)<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
39524 KB |
Output isn't correct |
| 2 |
Incorrect |
24 ms |
39532 KB |
Output isn't correct |
| 3 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 4 |
Incorrect |
20 ms |
39532 KB |
Output isn't correct |
| 5 |
Correct |
26 ms |
39660 KB |
Output is correct |
| 6 |
Incorrect |
24 ms |
39532 KB |
Output isn't correct |
| 7 |
Incorrect |
24 ms |
39532 KB |
Output isn't correct |
| 8 |
Incorrect |
24 ms |
39532 KB |
Output isn't correct |
| 9 |
Correct |
24 ms |
39532 KB |
Output is correct |
| 10 |
Correct |
25 ms |
39648 KB |
Output is correct |
| 11 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 12 |
Correct |
24 ms |
39532 KB |
Output is correct |
| 13 |
Correct |
24 ms |
39532 KB |
Output is correct |
| 14 |
Incorrect |
20 ms |
39428 KB |
Output isn't correct |
| 15 |
Incorrect |
25 ms |
39532 KB |
Output isn't correct |
| 16 |
Correct |
26 ms |
39532 KB |
Output is correct |
| 17 |
Correct |
25 ms |
39652 KB |
Output is correct |
| 18 |
Correct |
20 ms |
39532 KB |
Output is correct |
| 19 |
Correct |
26 ms |
39532 KB |
Output is correct |
| 20 |
Incorrect |
24 ms |
39524 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 2 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 3 |
Correct |
26 ms |
39532 KB |
Output is correct |
| 4 |
Correct |
25 ms |
39468 KB |
Output is correct |
| 5 |
Incorrect |
24 ms |
39532 KB |
Output isn't correct |
| 6 |
Correct |
24 ms |
39524 KB |
Output is correct |
| 7 |
Incorrect |
25 ms |
39532 KB |
Output isn't correct |
| 8 |
Incorrect |
25 ms |
39552 KB |
Output isn't correct |
| 9 |
Incorrect |
24 ms |
39532 KB |
Output isn't correct |
| 10 |
Incorrect |
24 ms |
39532 KB |
Output isn't correct |
| 11 |
Correct |
25 ms |
39552 KB |
Output is correct |
| 12 |
Incorrect |
25 ms |
39532 KB |
Output isn't correct |
| 13 |
Incorrect |
26 ms |
39532 KB |
Output isn't correct |
| 14 |
Incorrect |
25 ms |
39532 KB |
Output isn't correct |
| 15 |
Incorrect |
26 ms |
39532 KB |
Output isn't correct |
| 16 |
Correct |
25 ms |
39524 KB |
Output is correct |
| 17 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 18 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 19 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 20 |
Correct |
25 ms |
39528 KB |
Output is correct |
| 21 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 22 |
Correct |
25 ms |
39524 KB |
Output is correct |
| 23 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 24 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 25 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 26 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 27 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 28 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 29 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 30 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 31 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 32 |
Correct |
28 ms |
39524 KB |
Output is correct |
| 33 |
Correct |
26 ms |
39532 KB |
Output is correct |
| 34 |
Correct |
25 ms |
39448 KB |
Output is correct |
| 35 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 36 |
Correct |
24 ms |
39532 KB |
Output is correct |
| 37 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 38 |
Correct |
26 ms |
39524 KB |
Output is correct |
| 39 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 40 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 41 |
Correct |
27 ms |
39532 KB |
Output is correct |
| 42 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 43 |
Correct |
24 ms |
39532 KB |
Output is correct |
| 44 |
Correct |
25 ms |
39532 KB |
Output is correct |
| 45 |
Correct |
25 ms |
39532 KB |
Output is correct |
