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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include "aoc.h"
namespace aoc2016 {
struct elf {
int i;
elf* next;
};
void add_elf(elf* e1, elf* ex, elf** last) {
ex->next = e1;
(*last)->next = ex;
*last = ex;
}
elf* del_elf(elf* e1) {
elf* e = e1;
while (e->next != e) {
elf* n = e->next->next;
e->next = n;
e = n;
}
return e;
}
elf* cross(elf* e, int n) {
n = n / 2 - 1;
while (n > 0) {
e = e->next;
n--;
}
return e;
}
elf* del_elf(elf* e1, size_t n) {
elf* e = e1;
while (e->next != e) {
elf* ex = cross(e, n);
elf* en = ex->next->next;
ex->next = en;
e = e->next;
n -= 1;
}
return e;
}
elf* make_elf(int n) {
elf* e1 = new elf;
e1->i = 1;
e1->next = e1;
elf* last = e1;
for (int i = 2; i <= n; i++) {
elf* e = new elf;
e->i = i;
add_elf(e1, e, &last);
}
return e1;
}
size_t last_elf(size_t n) {
size_t x{0};
size_t i{1};
while (x < n) {
x += i;
i <<= 1;
}
x -= (i >> 1);
x += 1;
size_t a{1};
while (x != n) {
a += 2;
x += 1;
}
return a;
}
size_t final_elf(size_t n) {
if (n == 1) return 1;
size_t x{0};
size_t i{1};
while (x + 1 < n) {
x += i + i;
i *= 3;
}
x -= (i / 3) * 2;
x += 1;
size_t m = x + i / 3;
size_t a{1};
while (x != n) {
a += x < m ? 1 : 2;
x += 1;
}
return a - 1;
}
std::pair<int64_t, int64_t> day19(line_view) {
// for (int i = 1; i < 100; i++) {
// elf* e = make_elf(i);
// elf* x = del_elf(e, i);
// printf("%d: %d %zu\n", i, x->i, final_elf(i));
// }
return {last_elf(3005290), final_elf(3005290)};
}
} // namespace aoc2016
|
