#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
li dp[2][10][10]; //da li moram da postujem pravila, dvocifreni zavrsetak
li pp[2][10][10]; //prethodni dp
vector<int> cifre;
li uradi(li n)
{
if (n<=9) return n+1;
li temp=n;
cifre.clear();
while (temp)
{
cifre.pb(temp%10);
temp/=10;
}
reverse(all(cifre));
ff(STA_,0,2) ff(i,0,10) ff(j,0,10) dp[STA_][i][j]=0,pp[STA_][i][j]=0;
ff(i,1,10) ff(j,0,10) if (i!=j)
{
if (i<cifre[0]) dp[0][i][j]++;
else if (i==cifre[0] && j<cifre[1]) dp[0][i][j]++;
else if (i==cifre[0] && j==cifre[1]) dp[1][i][j]++;
}
ff(i,2,(int)cifre.size())
{
ff(STA_,0,2) ff(i,0,10) ff(j,0,10) pp[STA_][i][j]=dp[STA_][i][j],dp[STA_][i][j]=0;
ff(ac,0,10) ff(bc,0,10) ff(tc,0,10) if (tc!=ac && tc!=bc) //prekjucerasnja cifra, jucerasnja cifra, danasnja cifra
{
dp[0][bc][tc]+=pp[0][ac][bc];
if (tc<cifre[i]) dp[0][bc][tc]+=pp[1][ac][bc];
if (tc==cifre[i]) dp[1][bc][tc]+=pp[1][ac][bc];
}
}
li ret=0;
ff(i,0,10) ff(j,0,10) ret+=dp[0][i][j];
ff(i,0,10) ff(j,0,10) ret+=dp[1][i][j];
return ret;
}
li solve(li n)
{
if (n==-1) return 0ll;
if (n==0) return 1;
if (n==1'000'000'000'000'000'000) return solve(n-1);
li kur=0;
li stp=1;
while (stp>0)
{
stp*=10;
if (n<=stp-1) return kur+uradi(n);
kur+=uradi(stp-1);
}
return -69; //ovo zaista ne bi trebalo da se izvrsi
}
int main()
{
FAST;
li a,b; cin>>a>>b;
cout<<solve(b)-solve(a-1)<<"\n";
}
//Note to self: Check for overflow
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
320 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
320 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
324 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
1 ms |
324 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| 30 |
Correct |
1 ms |
212 KB |
Output is correct |
| 31 |
Correct |
1 ms |
324 KB |
Output is correct |
| 32 |
Correct |
1 ms |
212 KB |
Output is correct |
| 33 |
Correct |
1 ms |
212 KB |
Output is correct |
| 34 |
Correct |
1 ms |
212 KB |
Output is correct |
| 35 |
Correct |
1 ms |
320 KB |
Output is correct |
| 36 |
Correct |
1 ms |
212 KB |
Output is correct |
| 37 |
Correct |
1 ms |
212 KB |
Output is correct |
| 38 |
Correct |
1 ms |
320 KB |
Output is correct |
| 39 |
Correct |
1 ms |
328 KB |
Output is correct |
| 40 |
Correct |
1 ms |
212 KB |
Output is correct |
| 41 |
Correct |
1 ms |
212 KB |
Output is correct |
| 42 |
Correct |
1 ms |
328 KB |
Output is correct |
| 43 |
Correct |
1 ms |
276 KB |
Output is correct |
| 44 |
Correct |
1 ms |
212 KB |
Output is correct |
| 45 |
Correct |
1 ms |
212 KB |
Output is correct |
