-
Notifications
You must be signed in to change notification settings - Fork 0
/
day 16
59 lines (50 loc) · 1.1 KB
/
day 16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <vector>
#include <iostream>
// store single digits in an array, lowest digit come first
typedef std::vector<unsigned int> Digits;
int main()
{
// memoize powers of two
std::vector<Digits> cache;
// add 2^0 = 1
cache.push_back({ 1 });
unsigned int tests;
std::cin >> tests;
while (tests--)
{
unsigned int exponent;
std::cin >> exponent;
// and compute the remaining exponents
for (unsigned int current = cache.size(); current <= exponent; current++)
{
auto power = cache.back();
unsigned int carry = 0;
for (auto& i : power)
{
// times two ...
i = 2 * i + carry;
// handle overflow
if (i >= 10)
{
i -= 10;
carry = 1;
}
else
{
carry = 0;
}
}
// still some carry left ?
if (carry != 0)
power.push_back(carry);
// memoize result
cache.push_back(power);
}
// sum of all digits
unsigned int sum = 0;
for (auto i : cache[exponent])
sum += i;
std::cout << sum << std::endl;
}
return 0;
}