blob: 95d07173dffc08aba6ea09ffee244df773641b09 (
plain)
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#include <vector>
using namespace std;
namespace {
void
part1(const size_t n)
{
vector<size_t> v{ 3, 7 };
size_t first = 0;
size_t second = 1;
while ( v.size() < n + 10 ) {
auto value = v[first] + v[second];
if ( value >= 10 ) {
v.emplace_back(1);
value -= 10;
}
v.emplace_back(value);
first = (first + v[first] + 1) % v.size();
second = (second + v[second] + 1) % v.size();
}
cout << "Part 1: ";
for ( size_t i = n; i != n + 10; ++i ) {
cout << v[i];
}
cout << '\n';
}
void
part2(const size_t n)
{
vector<size_t> v{ 3, 7 };
size_t first = 0;
size_t second = 1;
const size_t len = to_string(n).length();
auto check = [&] {
if ( v.size() < len ) {
return false;
}
size_t value = 0;
for ( size_t i = len; i > 0; --i ) {
value *= 10;
value += v[v.size() - i];
}
return value == n;
};
for ( ;; ) {
auto value = v[first] + v[second];
if ( value >= 10 ) {
v.emplace_back(1);
if ( check() ) {
break;
}
value -= 10;
}
v.emplace_back(value);
if ( check() ) {
break;
}
first = (first + v[first] + 1) % v.size();
second = (second + v[second] + 1) % v.size();
}
cout << "Part 2: " << v.size() - len << '\n';
}
} // namespace
int
main()
{
const size_t input = 607331;
part1(input);
part2(input);
}
|
