Submission #1178976

#TimeUsernameProblemLanguageResultExecution timeMemory
1178976_dtq_Palindrome-Free Numbers (BOI13_numbers)C++20
72.50 / 100
1 ms840 KiB
#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define all(v) v.begin(), v.end() #define sz(x) (long long)(x.size()) using namespace std; ll a, b, maxn, t[30], dp[30][30][30][3]; ll calc( ll vt, ll x, ll y, bool c ) { if(vt == 0) return dp[vt][x][y][c] = 1; if(dp[vt][x][y][c] != -1) return dp[vt][x][y][c]; ll ans = 0; for( int w = 0; w <= (c ? t[vt] : 9); w ++ ) { if(w == y || w == x) continue; //cout << vt << " " << w << "\n"; ans += calc(vt - 1, y, w, c & (w == t[vt])); } return dp[vt][x][y][c] = ans; } ll solve( ll k ) { memset(dp, -1, sizeof(dp)); string s; while(k) { s = s + char(k % 10 + 48); k /= 10; } for( int w = 0; w < sz(s); w ++ ) { t[w + 1] = s[w] - 48; maxn = w + 1; } ll sum = 0; if(maxn == 2) sum ++; else if(maxn >= 3) sum += 10; return calc( maxn, 20, 20, 1 ) + sum; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> a >> b; if( a == 0 ) { cout << solve(b); return 0; } cout << solve(b) - solve(a - 1); // cout << solve(10) << " " << dp[1][20][0][0] << " " << dp[1][20][1][1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...