#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define all(x) x.begin(), x.end()
#define nl '\n'
#define MOD1 1000000007
#define MOD2 998244353
#define f0r(a, b) for (long long a = 0; a < (b); ++a)
#define f1r(a, b, c) for (long long a = (b); a < (c); ++a)
#define f0rd(a, b) for (long long a = (b); a >= 0; --a)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define send \
{ \
ios_base::sync_with_stdio(false); \
}
#define help \
{ \
cin.tie(NULL); \
cout.tie(NULL); \
}
#define fix(prec) \
{ \
cout << setprecision(prec) << fixed; \
}
#define mp make_pair
#define f first
#define s second
#define getunique(v) \
{ \
sort(all(v)); \
v.erase(unique(all(v)), v.end()); \
}
#define readgraph(list, edges) \
for (int i = 0; i < edges; i++) \
{ \
int a, b; \
cin >> a >> b; \
a--; \
b--; \
list[a].pb(b); \
list[b].pb(a); \
}
#define ai(a, n) \
for (int ele = 0; ele < n; ele++) \
cin >> a[ele];
#define ain(a, lb, rb) \
for (int ele = lb; ele <= rb; ele++) \
cin >> a[ele];
#define ao(a, n) \
{ \
for (int ele = 0; ele < (n); ele++) \
{ \
if (ele) \
cout << " "; \
cout << a[ele]; \
} \
cout << '\n'; \
}
#define aout(a, lb, rb) \
{ \
for (int ele = (lb); ele <= (rb); ele++) \
{ \
if (ele > (lb)) \
cout << " "; \
cout << a[ele]; \
} \
cout << '\n'; \
}
#define vsz(x) ((long long)x.size())
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
const ll INF = 1e18;
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v);
template <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v)
{
cout << "[";
for (int i = 0; i < v.size(); i++)
{
if (i)
cout << ", ";
cout << v[i];
}
return cout << "]";
}
template <typename A, typename B>
istream &operator>>(istream &cin, pair<A, B> &p)
{
cin >> p.first;
return cin >> p.second;
}
void __print(int 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"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) \
{ \
cerr << "[" << #x << "] = ["; \
_print(x); \
}
#else
#define dbg(x...)
#endif
ll binpow(ll x, ll y) /* (x^y)%p in O(log y) */
{
ll res = 1;
while (y > 0)
{
if (y & 1)
res = (res * x);
y = y >> 1;
x = (x * x);
}
return res;
}
ull binpowmod(ull x, ull y, ull p) /* (x^y)%p in O(log y) */
{
ull res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
ll mod_inverse(ll n, ll p) /* Returns n^(-1) mod p */ { return binpowmod(n, p - 2, p); }
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
return gcd(y, x % y);
}
ll lcm(ll x, ll y)
{
if (x == 0 || y == 0)
return 0;
else
return x * y / gcd(x, y);
}
bool isPowerOfTwo(ll x)
{
/* First x in the below expression is for the case when x is 0 */
return x && (!(x & (x - 1)));
}
// struct custom_hash {
// static uint64_t splitmix64(uint64_t x) {
// // http://xorshift.di.unimi.it/splitmix64.c
// x += 0x9e3779b97f4a7c15;
// x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
// x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
// return x ^ (x >> 31);
// }
// size_t operator()(uint64_t x) const {
// static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
// return splitmix64(x + FIXED_RANDOM);
// }
// };
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
unsigned int onesComplement(unsigned int n)
{
// Find number of bits in the given integer
int number_of_bits = floor(log2(n)) + 1;
// XOR the given integer with poe(2,
// number_of_bits-1 and print the result
return ((1 << number_of_bits) - 1) ^ n;
}
bool comp1(pair<ll, ll> x, pair<ll, ll> y)
{
if (x.first != y.first)
return x.first < y.first;
return x.second > y.second;
}
// class cmp //comrootator for priority_queue
// { //declaration: priority_queue<int,vector<int>,cmp>
// public:
// bool operator()(pair<ll, ll>& a, pair<ll, ll>& b)
// {
// // if(A.first == B.first)
// // return A.second < B.second;
// return a.second > b.second;
// }
// };
void printMSK(int msk)
{
cout << "{ ";
for (int i = 0; i < 32; ++i)
{
if (msk & (1LL << i))
cout << i << ", ";
}
cout << " }";
}
void add(ll &a, ll b, ll MOD = MOD1)
{
a += b;
if (a < 0)
a += MOD;
if (a >= MOD)
a -= MOD;
}
void _min(int &a, int b)
{
a = min(a, b);
}
void KS(int t)
{
cout << "Case #" << t << ": ";
}
ll ceil(ll n, ll r)
{
return (n + r - 1) / r;
}
string num_to_str(ll num)
{
string s = "";
while (num)
{
s += '0' + num % 10;
num /= 10;
}
reverse(all(s));
return s;
}
ll str_to_num(string &s, int base_ = 10)
{
ll num = 0;
for (char c : s)
num = num * base_ + c - '0';
return num;
}
const ll nax = 30 ;
int n = 0;
ll dp[nax][nax][nax][2][2];
bool vs[nax][nax][nax][2][2];
int rec(int x, int l, int sl,bool s, bool z,string v){
if(x==vsz(v)){vs[x][l][sl][s][z]=1;return dp[x][l][sl][s][z]=1;}
if(vs[x][l][sl][s][z])return dp[x][l][sl][s][z];
ll&ans = dp[x][l][sl][s][z];
ans=0;
int c = v[x]-'0';
if(s)c=9;
f0r(i,c+1){
if(i==l||i==sl)continue;
bool ns = 1;
if((!s)&&i==c)ns=0;
bool nz = z||(i^0);
int nl1=i,nll=l;
if((!z)&&(i==0))nl1=10,nll=10;
ans+=rec(x+1,nl1,nll,ns,nz,v);
}
vs[x][l][sl][s][z]=1;
return ans;
}
void solve(int tc = 1)
{
string a,b;
cin>>a>>b;
ll la = str_to_num(a);
la--;
a=num_to_str(la);
memset(dp,0,sizeof(dp));
memset(vs,0,sizeof(vs));
ll ca = rec(0,10,10,0,0,b);
memset(dp,0,sizeof(dp));
memset(vs,0,sizeof(vs));
ll cb = rec(0,10,10,0,0,a);
// dbg(ca,cb)
cout<<ca-cb;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cout << fixed << setprecision(7);
int tc;
tc = 1;
// cin >> tc;
for (int i = 1; i <= tc; ++i)
{
dbg(i)
solve(i);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1156 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1164 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 20 |
Correct |
1 ms |
1328 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 17 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 18 |
Correct |
2 ms |
1276 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 21 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 22 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 23 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 24 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 25 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 26 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 27 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 28 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 29 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 30 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 31 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 32 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 33 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 34 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 35 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 36 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 37 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 38 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 39 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 40 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 41 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 42 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 43 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 44 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 45 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
