#include <bits/stdc++.h>
#define ll long long
using namespace std;
int cnt,a[22];
ll dp[22][11][11][2],P[22];
void Clear() {
cnt=0;
for (int i=0; i<=20; i++) a[i]=0;
for (int i=0; i<=20; i++)
for (int j1=0; j1<=9; j1++)
for (int j2=0; j2<=9; j2++)
for (int k=0; k<=1; k++)
dp[i][j1][j2][k]=0;
}
void N(ll x) {
while (x>0) { a[++cnt]=x%10; x/=10; }
for (int i=1; i<=cnt/2; i++)
swap(a[i],a[cnt-i+1]);
}
ll Get(ll x,int type) {
if (x==-1) return 0;
if (x<=9) return x+1;
Clear();
N(x);
for (int j1=1; j1<=a[1]; j1++)
for (int j2=0; j2<=9; j2++) {
if (j1==j2) continue;
if (j1==a[1] && j2>a[2]) break;
if (j1==a[1] && j2==a[2]) dp[2][j1][j2][1]=1;
else dp[2][j1][j2][0]=1;
}
for (int i=2; i<cnt; i++)
for (int j1=0; j1<=9; j1++) {
for (int j2=0; j2<=9; j2++) {
if (j1==j2) continue;
for (int j3=0; j3<=9; j3++) {
if (j3==j2 || j3==j1) continue;
dp[i+1][j2][j3][0]+=dp[i][j1][j2][0];
if (j2==a[i] && j3<a[i+1]) dp[i+1][j2][j3][0]+=dp[i][j1][j2][1];
if (j2==a[i] && j3==a[i+1]) dp[i+1][j2][j3][1]+=dp[i][j1][j2][1];
}
}
}
ll res=0;
for (int j1=0; j1<=9; j1++)
for (int j2=0; j2<=9; j2++)
for (int k=0; k<=1; k++)
res+=dp[cnt][j1][j2][k];
if (!type) return res;
return res+P[cnt-1];
}
main () {
ll x=0,a,b;
for (int i=1; i<=19; i++) {
x=(1ll*x*10)+9;
P[i]=P[i-1]+Get(x,0);
}
cin>>a>>b;
cout<<Get(b,1)-Get(a-1,1)<<"\n";
}
Compilation message
numbers.cpp:61:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
9 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
504 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
376 KB |
Output is correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Correct |
3 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| 27 |
Correct |
2 ms |
376 KB |
Output is correct |
| 28 |
Correct |
2 ms |
376 KB |
Output is correct |
| 29 |
Correct |
2 ms |
376 KB |
Output is correct |
| 30 |
Correct |
2 ms |
372 KB |
Output is correct |
| 31 |
Correct |
12 ms |
376 KB |
Output is correct |
| 32 |
Correct |
2 ms |
376 KB |
Output is correct |
| 33 |
Correct |
2 ms |
376 KB |
Output is correct |
| 34 |
Correct |
3 ms |
376 KB |
Output is correct |
| 35 |
Correct |
2 ms |
376 KB |
Output is correct |
| 36 |
Correct |
2 ms |
376 KB |
Output is correct |
| 37 |
Correct |
2 ms |
376 KB |
Output is correct |
| 38 |
Correct |
2 ms |
376 KB |
Output is correct |
| 39 |
Correct |
2 ms |
376 KB |
Output is correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Correct |
2 ms |
376 KB |
Output is correct |
| 42 |
Correct |
2 ms |
376 KB |
Output is correct |
| 43 |
Correct |
2 ms |
376 KB |
Output is correct |
| 44 |
Correct |
2 ms |
376 KB |
Output is correct |
| 45 |
Correct |
2 ms |
376 KB |
Output is correct |
