Advertisement
Guest User

Untitled

a guest
Feb 21st, 2018
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. its>
  2. #include <sstream>
  3. using namespace std;
  4.  
  5. /*
  6. brute force:
  7. choice of range: O(n^2)
  8. check each range if interesting: O(n)
  9. total: O(n^3)
  10.  
  11. A better way:
  12. scan from left to right, suppose we are at index i
  13. total:
  14.   total number of interesting range between [0, i-1]
  15. prev_even:
  16.   total number of ranges ending at i - 1 that contains even number of palindromes
  17. prev_odd:
  18.   total number of ranges ending at i - 1 that contains odd nubmer of palindromes
  19.  
  20. so
  21.   If number at i is palindrome
  22.     cur_even = prev_odd
  23.     cur_odd = prev_even + 1
  24.   else
  25.     cur_even = prev_even + 1
  26.     cur_odd = prev_odd
  27.   total = toal + cur_even
  28.  
  29. As we spend O(x) time at each index, so total time O(nx), space O(1).
  30. x is the time to check if a number is palindrome.
  31. */
  32.  
  33. bool is_palindrome(int x) {
  34.     if (x <= 0) return false;
  35.    
  36.     long long y = x, z = 0;
  37.    
  38.     while (y > 0) {
  39.         z = 10 * z + y % 10;
  40.         y /= 10;
  41.     }
  42.    
  43.     return z <= INT_MAX && z == x;
  44. }
  45.  
  46. int solve(int begin, int end) {
  47.     int total = 0;
  48.     int prev_odd = 0, prev_even = 0, cur_odd = 0, cur_even = 0;
  49.    
  50.     for (int n = begin; n <= end; ++n) {
  51.         if (is_palindrome(n)) {
  52.             cur_even = prev_odd;
  53.             cur_odd = prev_even + 1;
  54.         } else {
  55.             cur_even = prev_even + 1;
  56.             cur_odd = prev_odd;
  57.         }
  58.         prev_even = cur_even;
  59.         prev_odd = cur_odd;
  60.         total += cur_even;
  61.     }
  62.    
  63.     return total;
  64. }
  65.  
  66. int main() {
  67.     string line;
  68.     int begin = 0, end = 0;
  69.    
  70.     while (getline(cin, line)) {
  71.         istringstream iss(line);
  72.         iss >> begin;
  73.         iss >> end;
  74.         cout << solve(begin, end) << endl;
  75.     }
  76.    
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement