// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v) memset(h, v, sizeof h)
#define Forv(i, a) for(auto& i : a)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define c_bit(i) __builtin_popcountll(i)
#define Bit(mask, i) ((mask >> i) & 1LL)
#define onbit(mask, i) ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
template <typename T> struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 1e6 + 5;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
#define int long long
ll a, b; string x;
ll dp[25][25][25][2];
string numbertostring (ll x){
string res = "";
while(x) res += char(x % 10 + '0'), x /= 10;
return reverse(all(res)), res;
}
ll solve(int i, int j, int k, bool ok){
if (i == x.size()) return 1;
if (~dp[i][j][k][ok]) return dp[i][j][k][ok];
ll res = 0;
int limit = (ok == 1) ? 9 : (x[i] - '0');
For(cs, 0, limit){
if (j != 10 && cs != k && cs != j) res += solve(i + 1, cs, j, ok | (cs < x[i] - '0'));
if (cs > 0 && j == 10){
res += solve(i + 1, cs, k, ok | (cs < x[i] - '0'));
}
}
return dp[i][j][k][ok] = res;
}
void Solve() {
cin >> a >> b;
reset(dp, -1);
x = numbertostring(b);
ll ans = solve(0, 10, 10, 0);
reset(dp, -1);
x = numbertostring(a - 1);
ans -= solve(0, 10, 10, 0);
cout << ans + (a <= 0 && 0 <= b) << '\n';
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
if(fopen("BOI13_numbers.inp", "r")) {
freopen("BOI13_numbers.inp", "r", stdin);
freopen("BOI13_numbers.out", "w", stdout);
}
int t = 1;
// cin >> t;
while(t --) Solve();
return 0;
}
Compilation message
numbers.cpp: In function 'long long int solve(long long int, long long int, long long int, bool)':
numbers.cpp:48:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | if (i == x.size()) return 1;
| ~~^~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen("BOI13_numbers.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | freopen("BOI13_numbers.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
1 ms |
592 KB |
Output is correct |
| 12 |
Correct |
1 ms |
592 KB |
Output is correct |
| 13 |
Correct |
1 ms |
592 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
592 KB |
Output is correct |
| 17 |
Correct |
1 ms |
592 KB |
Output is correct |
| 18 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 19 |
Correct |
1 ms |
592 KB |
Output is correct |
| 20 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
592 KB |
Output is correct |
| 3 |
Correct |
1 ms |
780 KB |
Output is correct |
| 4 |
Correct |
1 ms |
592 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 6 |
Correct |
1 ms |
592 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 11 |
Correct |
1 ms |
592 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
764 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
592 KB |
Output is correct |
| 17 |
Correct |
1 ms |
592 KB |
Output is correct |
| 18 |
Correct |
1 ms |
592 KB |
Output is correct |
| 19 |
Correct |
1 ms |
592 KB |
Output is correct |
| 20 |
Correct |
1 ms |
592 KB |
Output is correct |
| 21 |
Correct |
1 ms |
592 KB |
Output is correct |
| 22 |
Correct |
1 ms |
592 KB |
Output is correct |
| 23 |
Correct |
1 ms |
592 KB |
Output is correct |
| 24 |
Correct |
1 ms |
592 KB |
Output is correct |
| 25 |
Correct |
1 ms |
592 KB |
Output is correct |
| 26 |
Correct |
1 ms |
760 KB |
Output is correct |
| 27 |
Correct |
1 ms |
844 KB |
Output is correct |
| 28 |
Correct |
1 ms |
592 KB |
Output is correct |
| 29 |
Correct |
1 ms |
592 KB |
Output is correct |
| 30 |
Correct |
1 ms |
592 KB |
Output is correct |
| 31 |
Correct |
1 ms |
592 KB |
Output is correct |
| 32 |
Correct |
1 ms |
592 KB |
Output is correct |
| 33 |
Correct |
1 ms |
592 KB |
Output is correct |
| 34 |
Correct |
1 ms |
592 KB |
Output is correct |
| 35 |
Correct |
1 ms |
760 KB |
Output is correct |
| 36 |
Correct |
1 ms |
592 KB |
Output is correct |
| 37 |
Correct |
1 ms |
592 KB |
Output is correct |
| 38 |
Correct |
1 ms |
592 KB |
Output is correct |
| 39 |
Correct |
1 ms |
592 KB |
Output is correct |
| 40 |
Correct |
1 ms |
592 KB |
Output is correct |
| 41 |
Correct |
1 ms |
592 KB |
Output is correct |
| 42 |
Correct |
1 ms |
592 KB |
Output is correct |
| 43 |
Correct |
1 ms |
592 KB |
Output is correct |
| 44 |
Correct |
1 ms |
592 KB |
Output is correct |
| 45 |
Correct |
1 ms |
592 KB |
Output is correct |
