Submission #1262098

#TimeUsernameProblemLanguageResultExecution timeMemory
1262098nguyenvietanhPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms328 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pii pair<int,int> #define inp(name) freopen(name, "r", stdin); #define out(name) freopen(name, "w", stdout); const int N = 1e5 + 5; const int mod = 1e9 + 7; int l, r; int f[21][2][13][13], a[N]; int calc(int pos, int smaller, int pre1, int pre2, int ans){ if (pos == 0){ //cout << ans << " "; return 1; } if (f[pos][smaller][pre1][pre2] > -1) return f[pos][smaller][pre1][pre2]; int cur = 9; if (!smaller) cur = a[pos]; int res = 0; for (int i = 0; i <= cur; i ++){ if (ans == 0 && i == 0){ res += calc(pos - 1, smaller || (i < a[pos]), -1, -1, ans); } else{ if (i != pre1 && i != pre2) res += calc(pos - 1, smaller || (i < a[pos]), pre2, i, ans * 10 + i); } } return f[pos][smaller][pre1][pre2] = res; } int solve(int x){ int cur = 0; while (x){ a[++cur] = x % 10; x /= 10; } memset(f, -1, sizeof(f)); return calc(cur, 0, 11, 11, 0); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> l >> r; int x = solve(r), y = 0; //cout << solve(l - 1) << '\n'; if (l > 0) y = solve(l - 1); cout << x - y; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...