Submission #1294738

#TimeUsernameProblemLanguageResultExecution timeMemory
1294738JohanPalindrome-Free Numbers (BOI13_numbers)C++20
42.50 / 100
1097 ms580 KiB
#include<bits/stdc++.h> using namespace std; #define int long long string s; int dp[20][11][11][2]; int f(int pos, int last1, int last2, bool ok){ if(pos == s.size()) return 1; if(dp[pos][last1][last2][ok] != -1) return dp[pos][last1][last2][ok]; int limit = (ok == true ? s[pos] - '0' : 9); int ans = 0; for(int i = 0; i <= limit; i++){ if(last1 == 10 && last2 == 10 && i == 0){ if(ok == true && limit == i) ans += f(pos + 1, last1, last2, 1); else ans += f(pos + 1, last1, last2, 0); } else { if(i == last1 || i == last2) continue; if(ok == true && limit == i) ans += f(pos + 1, i, last1, 1); else ans += f(pos + 1, i, last1, 0); } } return ans; } int solve(int x){ if(x == -1)return 0; s = to_string(x); memset(dp, -1, sizeof(dp)); return f(0, 10, 10, 1); } signed main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); cin.tie(nullptr)->sync_with_stdio(false); int a, b; cin >> a >> b; cout << solve(b) - solve(a - 1) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...