hearot

Bases Conversion (ois_23)

Jul 5th, 2020
47
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Public and published.
  3.  * Written by Gabriel Hearot <gabriel@hearot.it>.
  4.  */
  5.  
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <map>
  9. #include <queue>
  10. #include <vector>
  11.  
  12. unsigned int T, i, k, c, v;
  13.  
  14. using namespace std;
  15.  
  16. #define MAX_BASE_2 16384 // 2**14, half of the maximum number of the digits a number can have in base 2 without being greater than 100_000_000 (base 10)
  17. #define MAX_BASE_3 19683 // 3**9, see MAX_BASE_2
  18.  
  19. vector<unsigned int> base2{ /* sum of digits up to MAX_BASE_2 */ };
  20.  
  21. vector<unsigned int> base3{ /* sum of digits up to MAX_BASE_3 */ };
  22.  
  23. unsigned int sum(unsigned int n, unsigned int base)
  24. {
  25.     if (base == 2)
  26.     {
  27.         if (n <= MAX_BASE_2)
  28.         {
  29.             return base2[n - 1];
  30.         }
  31.         else
  32.         {
  33.             if (n % MAX_BASE_2 == 0)
  34.                 return base2[n / MAX_BASE_2 - 1];
  35.  
  36.             return base2[n % MAX_BASE_2 - 1] + base2[n / MAX_BASE_2 - 1];
  37.         }
  38.     }
  39.     else
  40.     {
  41.         if (n <= MAX_BASE_3)
  42.         {
  43.             return base3[n - 1];
  44.         }
  45.         else
  46.         {
  47.             if (n % MAX_BASE_3 == 0)
  48.                 return base3[n / MAX_BASE_3 - 1];
  49.  
  50.             return base3[n % MAX_BASE_3 - 1] + base3[n / MAX_BASE_3 - 1];
  51.         }
  52.     }
  53. }
  54.  
  55. int32_t main()
  56. {
  57.     cin >> T;
  58.  
  59.     vector<unsigned int> input(T);
  60.     vector<unsigned int> keys;
  61.     map<unsigned int, unsigned int> special_numbers;
  62.  
  63.     for (i = 0; i < T; i++)
  64.     {
  65.         cin >> input[i];
  66.  
  67.         if (count(keys.begin(), keys.end(), input[i]) == 0)
  68.             keys.push_back(input[i]);
  69.  
  70.         k = max(k, input[i]);
  71.     }
  72.  
  73.     priority_queue<unsigned int, vector<int>, greater<unsigned int>> pq;
  74.  
  75.     for (auto e : keys)
  76.         pq.push(e);
  77.  
  78.     v = pq.top();
  79.     pq.pop();
  80.  
  81.     for (i = 1; i <= k; i++)
  82.     {
  83.         if (sum(i, 2) == sum(i, 3))
  84.         {
  85.             c++;
  86.         }
  87.  
  88.         if (i == v) {
  89.             special_numbers[i] = c;
  90.  
  91.             if (pq.size() > 0) {
  92.                 v = pq.top();
  93.                 pq.pop();
  94.             }
  95.         }
  96.     }
  97.  
  98.     for (i = 0; i < T; i++)
  99.     {
  100.         cout << special_numbers[input[i]] << " ";
  101.     }
  102.  
  103.     return 0;
  104. }
RAW Paste Data