Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- its>
- #include <sstream>
- using namespace std;
- /*
- brute force:
- choice of range: O(n^2)
- check each range if interesting: O(n)
- total: O(n^3)
- A better way:
- scan from left to right, suppose we are at index i
- total:
- total number of interesting range between [0, i-1]
- prev_even:
- total number of ranges ending at i - 1 that contains even number of palindromes
- prev_odd:
- total number of ranges ending at i - 1 that contains odd nubmer of palindromes
- so
- If number at i is palindrome
- cur_even = prev_odd
- cur_odd = prev_even + 1
- else
- cur_even = prev_even + 1
- cur_odd = prev_odd
- total = toal + cur_even
- As we spend O(x) time at each index, so total time O(nx), space O(1).
- x is the time to check if a number is palindrome.
- */
- bool is_palindrome(int x) {
- if (x <= 0) return false;
- long long y = x, z = 0;
- while (y > 0) {
- z = 10 * z + y % 10;
- y /= 10;
- }
- return z <= INT_MAX && z == x;
- }
- int solve(int begin, int end) {
- int total = 0;
- int prev_odd = 0, prev_even = 0, cur_odd = 0, cur_even = 0;
- for (int n = begin; n <= end; ++n) {
- if (is_palindrome(n)) {
- cur_even = prev_odd;
- cur_odd = prev_even + 1;
- } else {
- cur_even = prev_even + 1;
- cur_odd = prev_odd;
- }
- prev_even = cur_even;
- prev_odd = cur_odd;
- total += cur_even;
- }
- return total;
- }
- int main() {
- string line;
- int begin = 0, end = 0;
- while (getline(cin, line)) {
- istringstream iss(line);
- iss >> begin;
- iss >> end;
- cout << solve(begin, end) << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement