Heap of boxes P44911
Consider a heap with n boxes at the bottom. The next row has n−1 boxes, the following row n−2 boxes, and so on. The boxes at the bottom row can store any integer numbers, but every other box must contain the sum of the two boxes underneath. The figure shows an example for n = 4:
linecolor=blue
-(2,2)(10,2) -(2,3)(10,3) -(3,4)(9,4) -(4,5)(8,5) -(5,6)(7,6)
-(3,3)(3,4) -(5,3)(5,4) -(5,5)(5,6) -(7,3)(7,4) -(7,5)(7,6) -(9,3)(9,4) -(2,2)(2,3) -(4,2)(4,3) -(4,4)(4,5) -(6,2)(6,3) -(6,4)(6,5) -(8,2)(8,3) -(8,4)(8,5) -(10,2)(10,3)
(3,2.5)23 (5,2.5)19 (7,2.5)6 (9,2.5)3 (4,3.5)42 (6,3.5)25 (8,3.5)9 (5,4.5)67 (7,4.5)34 (6,5.5)101
Given n, you must fill the heap of boxes with integer numbers, according to the rules above. Your goal is to maximize the total quantity of odd numbers. For instance, the figure proves that 7 odd numbers are possible for n = 4. In fact, 7 is the maximum for n = 4.
Input
Input consists of several cases, each one with a natural number n between 1 and 28.
Output
For every n, print the maximum number of odd numbers that a heap with n boxes at the bottom can contain according to the given rules.
Input
1 4 25
Output
1 7 217
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++