Submission #1178978

#TimeUsernameProblemLanguageResultExecution timeMemory
1178978_dtq_Palindrome-Free Numbers (BOI13_numbers)C++20
32.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, ll sum ) { 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 && sum) continue; if(w == x && sum >= 10) continue; //cout << vt << " " << w << "\n"; ans += calc(vt - 1, y, w, c & (w == t[vt]), sum * 10 + w); } 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; } return calc( maxn, 20, 20, 1, 0 ); } 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); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...