Canadian Computing Competition: 2018 Stage 1, Senior #4
Trees have many fascinating properties. While this is primarily true for trees in nature, the concept of trees in math and computer science is also interesting. A particular kind of tree, a perfectly balanced tree, is defined as follows.
Every perfectly balanced tree has a positive integer weight. A perfectly balanced tree of weight 
~1~ always consists of a single node. Otherwise, if the weight of a perfectly balanced tree is 
~w~ and 
~w \ge 2~, then the tree consists of a root node with branches to 
~k~ subtrees, such that 
~2 \le k \le w~. In this case, all ~k~ subtrees must be completely identical, and be perfectly balanced themselves.
In particular, all ~k~ subtrees must have the same weight. This common weight must be the maximum integer value such that the sum of the weights of all ~k~ subtrees does not exceed ~w~, the weight of the overall tree. For example, if a perfectly balanced tree of weight 
~8~ has 
~3~ subtrees, then each subtree would have weight 
~2~, since 
~2+2+2 = 6 \le 8~.
Given 
~N~, find the number of perfectly balanced trees with weight ~N~.
Input Specification
The input will be a single line containing the integer ~N~ 
~(1 \le N \le 10^9)~.
For 
~5~ of the 
~15~ marks available, 
~N \le 1\,000~.
For an additional ~2~ of the ~15~ marks available, 
~N \le 50\,000~.
For an additional ~2~ of the ~15~ marks available, 
~N \le 10^6~.
Output Specification
Output a single integer, the number of perfectly balanced trees with weight ~N~.
Sample Input 1
4
Sample Output 1
3
Explanation for Sample Output 1
One tree has a root with four subtrees of weight ~1~; a second tree has a root with two subtrees of weight ~2~; the third tree has a root with three subtrees of weight ~1~.
Sample Input 2
10
Sample Output 2
13
Comments
I still have questions about the second sample input. I tried and got the same result as that guy got--17. Can anyone specify what the situation is when input is 10? ty
For all trees with a weight of 10 and # of branches in the range of [4,10], we +1 each time to the total number of perfect trees.
With 3 branches (each branch will have a weight of 10/3=3), we add 2 to our answer(since 3->1,1 and 3->1,1,1).
With 2 branches (each branch will have a weight of 10/2=5), we add 4 to our answer(since 5->1,1,1,1,1; 5->1,1,1,1; 5->1,1,1; 5->2,2).
I don't know why I get seg fault on the last batch... I doubled checked my indexing, and nothing seems to be wrong..
You're running out of memory