//Author = Anirudh Srikanth (yeetholmes619) [B20CS006]
//https://github.com/yeetholmes619/Template.git
#include<bits/stdc++.h>
#define curtime chrono::high_resolution_clock::now()
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define timedif(start,end) chrono::duration_cast<chrono::nanoseconds>(end - start).count()
using namespace std;
#define RESET "\033[0m"
#define BR "\033[1m\033[31m" /* Bold Red */
#define BG "\033[1m\033[32m" /* Bold Green */
#define BB "\033[1m\033[34m" /* Bold Blue */
#define ll long long
#define ld long double
#define INF 1000000007
#define pb push_back
#define pf push_front
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define ROF(i,a,b) for(int i = a; i >= b; i--)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int,int>>
#define pii pair<int,int>
#define mii map<int,int>
#define mci map<char,int>
template <typename T>
using matrix = vector<vector<T>>;
//as seen on https://codeforces.com/profile/I_love_Tanya_Romanova 's template
//in order to be able to use pre-defined variables in STL
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define left asdgashgrketwjklrej
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd
#define prev asdgSHJsfgsdfhdsh
#define umap unordered_map
#define sz(x) (int)(x.size())
#define mp make_pair
#define allvec(v) v.begin(), v.end()
#define int long long
#define output(value) cout << value << "\n"
#define error(errorString) cout << BR << errorString << RESET<< "\n"
#define info(infoString) cout << BB << infoString << RESET << "\n"
#define success(successString) cout << BB << successString << RESET << "\n"
#define allarr(a,n) a, a+n
const int mod1 =1000000007;
const int mod2 = 998244353;
// precedence order :- double > float > long long int > long int > int > char
// remember that boolean arrays and variables if uninitialized are given false
// say x is a character, s += x is faster than s = s+x
//Check if constraints are correct
// for single arrays declare them as long long int
//overflow must be taken care of!! use strings when big
// 0 < |int| < 1e9
// 0 < |long long int| < 1e18
//when you are working with stacks, remember to take care of stacks of 0 size
//when you see a problem, and you know how you would tackle it in the real world, but don't know how
//you would do it in code, go step by step, in each step try to be concious of what you want to do
//and once you have done so, review through and remember what data structure would be perfect
//when we pass an array in a function the pointer is passed but when we pass a vector, a copy is passed
template<typename T1, typename T2> // cin >> pair<T1, T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
template<typename T> // cin >> vector<T>
istream& operator>>(istream &istream, vector<T> &v)
{
for (auto &it : v)
cin >> it;
return istream;
}
template<typename T1, typename T2> // cout << pair<T1, T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
template<typename T> // cout << vector<T>
ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\DEBUG/\/\/\/\/\/\/\/\/\/\/\/\///\/\/
void __print(int32_t x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n"<<RESET;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define debug(x...) cerr <<BR<< "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\///\/\/\/\/\/\/
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\GLOBAL VARIABLES/\/\/\/\/\/\/\/\/\/\/\/\///\/\/
int l,r;
int dp[20][11][11][2][2];
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\///\/\/\/\/\/\/
void reset(){
for(int i = 0; i < 20; i++)
for(int j = 0; j < 11; j++)
for(int k = 0; k < 11; k++)
for(int l = 0; l < 2; l++)
for(int m = 0; m < 2; m++)
dp[i][j][k][l][m] = -1;
}
int solve(int c, int pos = 0, int last2 = 10, int last1 = 10, int valid = 0, int smaller =0){
debug(c,pos,last2,last1,valid,smaller);
int &ref = dp[pos][last2][last1][valid][smaller];
if(ref != -1)
return ref;
int len = to_string(c).size();
if(pos == len)
return ref = 1;
ref = 0;
int limit = 9;
if(!smaller){
limit = to_string(c)[pos] - '0';
}
for(int dig = 0; dig <= limit; dig++){
if(last1 == dig or last2 == dig)
continue;
int ndig = dig;
int nvalid = valid;
if(!valid){
nvalid = (pos+1 == len or dig > 0);
}
if(!nvalid){
ndig = 10;
}
ref += solve(c,pos+1,last1,ndig,nvalid,(smaller) ? true : (dig != limit));
}
return ref;
}
void take(){
cin>>l>>r;
}
void solve(){
take();
reset();
int total = solve(r);
reset();
cout<<total - solve(l-1)<<"\n";
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto time0 = curtime;
ll t = 1;
for(int i = 1 ; i <= t; i++) {
//cout << "Case #" << i << ": ";
solve();
}
#ifdef YEET
cerr<<"Execution Time: "<<timedif(time0,curtime)*1e-9<<" sec\n";
#endif
return 0;
}
Compilation message
numbers.cpp: In function 'int32_t main()':
numbers.cpp:171:10: warning: variable 'time0' set but not used [-Wunused-but-set-variable]
171 | auto time0 = curtime;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
328 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
324 KB |
Output is correct |
| 9 |
Correct |
0 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 |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 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 |
0 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
324 KB |
Output is correct |
| 19 |
Correct |
1 ms |
324 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
436 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 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 |
328 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 |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
324 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 |
292 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
324 KB |
Output is correct |
| 26 |
Correct |
1 ms |
324 KB |
Output is correct |
| 27 |
Correct |
2 ms |
320 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
1 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
340 KB |
Output is correct |
| 34 |
Correct |
1 ms |
340 KB |
Output is correct |
| 35 |
Correct |
1 ms |
340 KB |
Output is correct |
| 36 |
Correct |
1 ms |
340 KB |
Output is correct |
| 37 |
Correct |
1 ms |
340 KB |
Output is correct |
| 38 |
Correct |
1 ms |
340 KB |
Output is correct |
| 39 |
Correct |
1 ms |
324 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
1 ms |
340 KB |
Output is correct |
| 42 |
Correct |
1 ms |
364 KB |
Output is correct |
| 43 |
Correct |
1 ms |
340 KB |
Output is correct |
| 44 |
Correct |
1 ms |
340 KB |
Output is correct |
| 45 |
Correct |
1 ms |
340 KB |
Output is correct |
