Rust Implementation of Problem 76
View source code here on GitHub!
Problem Solution
- pub fn problems::p0076::p0076() -> utils::Answer
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
7Problem:
8
9It is possible to write five as a sum in exactly six different ways:
10
114 + 1
123 + 2
133 + 1 + 1
142 + 2 + 1
152 + 1 + 1 + 1
161 + 1 + 1 + 1 + 1
17
18How many different ways can one hundred be written as a sum of at least two
19positive integers?
20*/
21use crate::include::utils::Answer;
22
23pub fn p0076() -> Answer {
24 let mut answer: u64 = 0;
25 let mut idx: usize;
26 let mut sum: u64 = 100;
27 let mut counts: Vec<u64> = vec![0; 101];
28 counts[2] = 100;
29 while counts[100] == 0 {
30 counts[2] += 2;
31 if sum >= 100 {
32 answer += (100 + counts[2] - sum) / 2;
33 idx = 2;
34 loop {
35 counts[idx] = 0;
36 idx += 1;
37 counts[idx] += idx as u64;
38 sum = counts.iter().sum();
39 if sum <= 100 {
40 break;
41 }
42 }
43 counts[2] = 100 - sum - (sum % 2);
44 }
45 sum = counts.iter().sum();
46 }
47 return Answer::Int(answer.into());
48}