# 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