# include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define endl '\n'
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define vi vector<int>
#define vii vector<pair<int, int> >
#define mp make_pair
#define mem1(a) memset((a),-1,sizeof(a))
#define mem0(a) memset((a),0,sizeof(a))
#define memf(a) memset((a),false,sizeof(a))
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a)*((b)/gcd((a),(b)))
#define DECIMAL(n) cout << fixed ; cout << setprecision(n);
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mi map<int,int>
#define sz(x) (ll)(x).size()
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pii pair<int,int>
long long dp[19][2][2][11][11];
long long rec(int indx, int tight, int started, int prev, int pprev, string num)
{
if (indx == (int)num.size())
return 1;
long long &ans = dp[indx][tight][started][prev][pprev];
if (ans != -1)
return ans;
ans = 0;
int up = num[indx] - '0';
if (tight)
up = 9;
for (int i = 0; i <= up; i++)
{
if ((prev == 10 || i != prev) && (pprev == 10 || i != pprev))
{
int ntight = tight | i < (num[indx] - '0');
int nstarted = started | (i > 0);
if (!started && !i)
{
ans += rec(indx + 1, ntight, nstarted, prev, pprev, num);
}
else
{
ans += rec(indx + 1, ntight, nstarted, i, prev, num);
}
}
}
return ans;
}
int solve()
{
long long l, r;
cin >> l >> r;
mem1(dp);
string R = to_string(r);
long long ans = rec(0, 0, 0, 10, 10, R);
mem1(dp);
string L = to_string(--l);
ans -= rec(0, 0, 0, 10, 10, L);
cout << ans;
return 0;
}
signed main()
{
FAST
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int t = 1;
// cin>>t;
while (t)
{
solve();
t--;
}
return 0;
}
Compilation message
numbers.cpp: In function 'long long int rec(int, int, int, int, int, std::string)':
numbers.cpp:46:27: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
46 | int ntight = tight | i < (num[indx] - '0');
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
320 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
324 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
320 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
320 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
324 KB |
Output is correct |
| 14 |
Correct |
1 ms |
328 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
2 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
324 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
2 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
320 KB |
Output is correct |
| 26 |
Correct |
2 ms |
340 KB |
Output is correct |
| 27 |
Correct |
2 ms |
388 KB |
Output is correct |
| 28 |
Correct |
2 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
324 KB |
Output is correct |
| 31 |
Correct |
2 ms |
328 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
340 KB |
Output is correct |
| 34 |
Correct |
2 ms |
340 KB |
Output is correct |
| 35 |
Correct |
2 ms |
340 KB |
Output is correct |
| 36 |
Correct |
1 ms |
340 KB |
Output is correct |
| 37 |
Correct |
2 ms |
328 KB |
Output is correct |
| 38 |
Correct |
2 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
340 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
2 ms |
340 KB |
Output is correct |
| 42 |
Correct |
1 ms |
340 KB |
Output is correct |
| 43 |
Correct |
2 ms |
320 KB |
Output is correct |
| 44 |
Correct |
1 ms |
340 KB |
Output is correct |
| 45 |
Correct |
2 ms |
324 KB |
Output is correct |
