Submission #1254567

#TimeUsernameProblemLanguageResultExecution timeMemory
1254567XXBabaProBerkayPalindrome-Free Numbers (BOI13_numbers)C++20
13.75 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define MP make_pair #define PB push_back using ll = long long; using ld = long double; using pi = pair<int, int>; using pll = pair<ll, ll>; template<typename T> using vec = vector<T>; template<typename T, int N> using arr = array<T, N>; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } const ll INF = 1e18; const int MOD = 998244353; vec<int> num; ll dp[2][10][10][20]; ll f(bool g, int d1, int d2, int i) { if (i >= (int)num.size()) return 1; if (dp[g][d1][d2][i] != -1) return dp[g][d1][d2][i]; dp[g][d1][d2][i] = 0; for (int j = 0; j <= (g ? 9 : num[i]); j++) { if ((i >= 2 && j == d2) || (i >= 1 && j == d1)) continue; dp[g][d1][d2][i] += f(g || j < num[i], j, d1, i + 1); } return dp[g][d1][d2][i]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); memset(dp, -1, sizeof dp); int a, b; cin >> a >> b; a--; while (a > 0) { num.PB(a % 10); a /= 10; } reverse(num.begin(), num.end()); ll x = f(0, 0, 0, 0); memset(dp, -1, sizeof dp); num.clear(); while (b > 0) { num.PB(b % 10); b /= 10; } reverse(num.begin(), num.end()); ll y = f(0, 0, 0, 0); cout << y - x << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...