#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
ll set_on(int n, int k){
return (n |= 1 << k);
}
ll set_off(int n, int k){
return (n &= ~(1UL << k));
}
bool check_bit(int n, int k){
int bit = (n >> k) & 1U;
if(bit == 1)
return true;
return false;
}
ll dp[25][25][25][2][2];
vi get_digits(ll n) {
vi v;
do {
v.push_back(n % 10);
n /= 10;
} while (n > 0);
reverse(v.begin(), v.end());
return v;
}
ll f(int idx, int last, int blast, bool big, bool nonzero, vi& digits){
if(idx == (int)digits.size()){
return dp[idx][last][blast][big][nonzero] = 1;
}
if(dp[idx][last][blast][big][nonzero] != -1)
return dp[idx][last][blast][big][nonzero];
ll ans = 0;
int sega = digits[idx];
if(big)
sega = 9;
for(int d = 0; d <= sega; d++){
if(d == last || d == blast)
continue;
bool nxtSmall = true;
if(!big && d == sega){
nxtSmall = false;
}
bool nZero = nonzero | (d > 0);
int lst = last, curr = d;
if(d == 0 && !nonzero){
lst = 10;
curr = 10;
}
ans += f(idx + 1, curr, lst, nxtSmall, nZero, digits);
}
return dp[idx][last][blast][big][nonzero] = ans;
}
ll solve(ll n) {
if (n <= 10) {
return (n == -1 ? 0 : n + 1);
}
memset(dp, -1, sizeof dp);
auto digits = get_digits(n);
return f(0, 10, 10, false, false, digits);
}
int main(){
ll l, r;
cin>>l>>r;
cout<<solve(r) - solve(l-1)<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
696 KB |
Output is correct |
| 9 |
Correct |
1 ms |
692 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Correct |
1 ms |
724 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
1 ms |
724 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
772 KB |
Output is correct |
| 16 |
Correct |
1 ms |
724 KB |
Output is correct |
| 17 |
Correct |
1 ms |
696 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
724 KB |
Output is correct |
| 20 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
696 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
688 KB |
Output is correct |
| 9 |
Correct |
1 ms |
688 KB |
Output is correct |
| 10 |
Correct |
1 ms |
724 KB |
Output is correct |
| 11 |
Correct |
1 ms |
724 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
1 ms |
688 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
1 ms |
724 KB |
Output is correct |
| 17 |
Correct |
1 ms |
724 KB |
Output is correct |
| 18 |
Correct |
1 ms |
724 KB |
Output is correct |
| 19 |
Correct |
1 ms |
724 KB |
Output is correct |
| 20 |
Correct |
1 ms |
724 KB |
Output is correct |
| 21 |
Correct |
1 ms |
724 KB |
Output is correct |
| 22 |
Correct |
1 ms |
724 KB |
Output is correct |
| 23 |
Correct |
1 ms |
724 KB |
Output is correct |
| 24 |
Correct |
1 ms |
724 KB |
Output is correct |
| 25 |
Correct |
1 ms |
692 KB |
Output is correct |
| 26 |
Correct |
1 ms |
724 KB |
Output is correct |
| 27 |
Correct |
1 ms |
724 KB |
Output is correct |
| 28 |
Correct |
1 ms |
724 KB |
Output is correct |
| 29 |
Correct |
1 ms |
724 KB |
Output is correct |
| 30 |
Correct |
1 ms |
724 KB |
Output is correct |
| 31 |
Correct |
1 ms |
724 KB |
Output is correct |
| 32 |
Correct |
1 ms |
724 KB |
Output is correct |
| 33 |
Correct |
1 ms |
688 KB |
Output is correct |
| 34 |
Correct |
1 ms |
692 KB |
Output is correct |
| 35 |
Correct |
1 ms |
724 KB |
Output is correct |
| 36 |
Correct |
1 ms |
724 KB |
Output is correct |
| 37 |
Correct |
1 ms |
724 KB |
Output is correct |
| 38 |
Correct |
1 ms |
724 KB |
Output is correct |
| 39 |
Correct |
1 ms |
692 KB |
Output is correct |
| 40 |
Correct |
1 ms |
724 KB |
Output is correct |
| 41 |
Correct |
1 ms |
724 KB |
Output is correct |
| 42 |
Correct |
1 ms |
724 KB |
Output is correct |
| 43 |
Correct |
1 ms |
724 KB |
Output is correct |
| 44 |
Correct |
1 ms |
724 KB |
Output is correct |
| 45 |
Correct |
1 ms |
724 KB |
Output is correct |
