-
Notifications
You must be signed in to change notification settings - Fork 0
/
day 96
60 lines (48 loc) · 1.21 KB
/
day 96
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
60
#include <iostream>
#include <vector>
#define ORIGINAL
// memoized solutions
const long long Unknown = -1;
std::vector<long long> solutions;
// find result for row with a certain length
unsigned long long count(unsigned long long space)
{
// finished ?
if (space == 0)
return 1;
// already know the answer ?
if (solutions[space] != Unknown)
return solutions[space];
// insert red blocks at the current position with all possible spaces
unsigned long long result = 0;
for (unsigned long long block = 1; block <= 4 && block <= space; block++)
{
// how much is left after inserting ?
auto next = space - block;
// count all combinations
result += count(next);
}
// memoize result
solutions[space] = result;
return result;
}
int main()
{
unsigned int tests;
std::cin >> tests;
while (tests--)
{
// what number should be exceeded ?
unsigned long long limit = 50;
std::cin >> limit;
// cached results
solutions.clear();
solutions.resize(limit+1, Unknown);
auto result = count(limit);
#ifndef ORIGINAL
result %= 1000000007; // Hackerrank asks for "small" results
#endif
std::cout << result << std::endl;
}
return 0;
}