C++ Implementation of Problem 76
View source code here on GitHub!
Includes
Solution
-
uint64_t p0076()
-
int main(int argc, char const *argv[])
Note
This function is only present in the Python test runner, or when compiling as a standalone program.
1/*
2Project Euler Problem 76
3
4I ended up having to do this iteratively, which I'm not super happy with. I feel like there is almost certainly a
5closed-form solution to this, but I was unable to figure it out.
6
7Revision 1:
8
9Have counts store values instead of numeral counts to shave a few seconds off
10
11Revision 2:
12
13Manually expand the sum loop in the preprocessor to try and get TCC output to be faster. Shaved a ~1/3 of runtime in
14both CL and GCC in my initial testing.
15
16Revision 3:
17
18After testing on non-Windows systems, I found that Revision 2 royally borked it up. I reverted this, then applied an
19optimization I found earlier today. The number of solutions to a + 2b + n = 100, where a, b, n in [0, 100] is
20(100 - n) / 2 + 1. This brought runtime on TCC from ~3min -> ~1min and clang from ~6s -> ~2s.
21
22Revision 4:
23
24Repeat an earlier optimization for the 2s case, so now it tries to keep the 2s value as close to the missing piece as
25possible, cutting out a lot of useless loops. Runtime is approximately halved on TCC.
26
27Problem:
28
29It is possible to write five as a sum in exactly six different ways:
30
314 + 1
323 + 2
333 + 1 + 1
342 + 2 + 1
352 + 1 + 1 + 1
361 + 1 + 1 + 1 + 1
37
38How many different ways can one hundred be written as a sum of at least two
39positive integers?
40*/
41#ifndef EULER_P0076
42#define EULER_P0076
43#include <stdint.h>
44#include <iostream>
45#include "include/macros.hpp"
46
47uint32_t EMSCRIPTEN_KEEPALIVE p0076() {
48 uint32_t answer = 0;
49 uint8_t idx, i, sum = 100, counts[101] = {0, 0, 100, 0};
50 while (!counts[100]) {
51 counts[2] += 2;
52 if (sum >= 100) {
53 answer += (100 + counts[2] - sum) / 2;
54 idx = 2;
55 do {
56 counts[idx++] = 0;
57 counts[idx] += idx;
58 sum = counts[2];
59 for (i = 3; i < 100; ++i)
60 sum += counts[i];
61 } while (sum > 100);
62 counts[2] = 100 - sum - (sum % 2);
63 }
64 sum = counts[2];
65 for (i = 3; i < 100; ++i)
66 sum += counts[i];
67 }
68
69 return answer;
70}
71
72PROGRAM_TAIL(p0076)
73#endif