This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// teddybear's code
// the one who loves NBP
// noe the second
// goal: 0 / 8
// get medal in APIO (like TKN)
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// prob:
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define FOR(i,n) for (int i = 0; i<n; i++)
using ll = long long;
using ull = unsigned long long;
ll n,m,t;
ll cnt = 0;
const int maxn = 1e5;
const ll mod = 1e9 + 7;
#define Y "YES"
#define N "NO"
int a[1005][1005];
bool visited[1005][1005];
int dist[1005][1005];
int w,h;
int fx[4] = {-1, 1, 0, 0};
int fy[4] = {0, 0, -1, 1};
queue <pair<int,int>> q;
string s;
ll num[20][2][12][12][2];
ll dp(ll pos, ll eq, ll last1, ll last2, ll start)
{
if (pos == s.size())
{
return 1;
}
ll ans = 0;
if (num[pos][eq][last1+1][last2+1][start] != -1)
{
return num[pos][eq][last1+1][last2+1][start];
}
ll mxnum;
if (eq)
{
mxnum = s[pos] - '0';
}
else
{
mxnum = 9;
}
if (start == -1)
{
for (ll dig = 0; dig<=mxnum; dig++)
{
/*if ((dig == last1 && last1 > 0) || (dig == last2 && last2 > 0))
{
continue;
}*/
ll neweq = eq & (dig == mxnum);
ll newlast1 = dig;
ll newlast2 = last1;
if (dig == 0)
{
newlast1 = -1;
}
/*if (dig != 0)
{
start = 0;
}
else
{
start = -1;
}*/
ll newstart;
if (dig != 0)
{
newstart = 0;
}
else newstart = -1;
ans += dp(pos+1,neweq,newlast1,newlast2,newstart);
}
}
else
{
for (ll dig = 0; dig<=mxnum; dig++)
{
if (dig == last1 || dig == last2)
{
continue;
}
ll neweq = eq & (dig == mxnum);
ll newlast1 = dig;
ll newlast2 = last1;
ans += dp(pos+1,neweq,newlast1,newlast2,start);
}
}
return num[pos][eq][last1+1][last2+1][start] = ans;
}
ll DP_digit(ll x)
{
if (x < 0) return 0;
s = to_string(x);
memset(num,-1,sizeof(num));
return dp(0,1,-1,-1,-1);
}
void solve()
{
ll a,b;
cin >> a >> b;
//cout << "! " << DP_digit(b) << ' ' << DP_digit(a-1) << '\n';
cout << DP_digit(b) - DP_digit(a-1) << '\n';
}
void init()
{
int te = 1; //cin >> te;
while (te--)
{
solve();
}
}
void preprocess()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//cin.tie(0); cout.tie(0);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
init();
preprocess();
//solve();
return 0;
}
Compilation message (stderr)
numbers.cpp: In function 'll dp(ll, ll, ll, ll, ll)':
numbers.cpp:39:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if (pos == s.size())
| ~~~~^~~~~~~~~~~
numbers.cpp: In function 'll _Z8DP_digitx.part.0(ll)':
numbers.cpp:110:45: warning: array subscript -1 is below array bounds of 'll [2]' {aka 'long long int [2]'} [-Warray-bounds]
110 | return num[pos][eq][last1+1][last2+1][start] = ans;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |