## CCC '18 S4 - Balanced Trees

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
##### 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 always consists of a single node. Otherwise, if the weight of a perfectly balanced tree is and , then the tree consists of a root node with branches to subtrees, such that . In this case, all subtrees must be completely identical, and be perfectly balanced themselves.

In particular, all subtrees must have the same weight. This common weight must be the maximum integer value such that the sum of the weights of all subtrees does not exceed , the weight of the overall tree. For example, if a perfectly balanced tree of weight has subtrees, then each subtree would have weight , since .

Given , find the number of perfectly balanced trees with weight .

#### Input Specification

The input will be a single line containing the integer .

For of the marks available, .

For an additional of the marks available, .

For an additional of the marks available, .

#### Output Specification

Output a single integer, the number of perfectly balanced trees with weight .

#### Sample Input 1

4

#### Sample Output 1

3

#### Explanation for Sample Output 1

One tree has a root with four subtrees of weight ; a second tree has a root with two subtrees of weight ; the third tree has a root with three subtrees of weight .

#### Sample Input 2

10

#### Sample Output 2

13

• elliss  commented on Feb. 4, 2019, 11:25 a.m.

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

• spatarel  commented on Feb. 18, 2019, 8:42 a.m. edit 3

Let F(w) = number of trees of wight w

Then:
F(1) = 1
F(2) = F(2/2)
= F(1) = 1
F(3) = F(3/3) + F(3/2)
= F(1) + F(1) = 2
F(4) = F(4/4) + F(4/3) + F(4/2)
= F(1) + F(1) + F(2) = 1 + 1 + 1 = 3
F(10) = F(10/10) + F(10/9) + F(10/8) + F(10/7) + F(10/6) + F(10/5) + F(10/4) + F(10/3) + F(10/2)
= F(1) + F(1) + F(1) + F(1) + F(1) + F(2) + F(2) + F(3) + F(5)
= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 4 = 13

Good luck solving the problem!

• Summertony717  commented on Jan. 27, 2019, 10:43 p.m.

I don't know why I get seg fault on the last batch... I doubled checked my indexing, and nothing seems to be wrong..

• Plasmatic  commented on Jan. 27, 2019, 11:02 p.m.

You're running out of memory

• albertlai431  commented on March 6, 2018, 7:57 p.m. edit 2

Slow judge? Or is my code just too slow

Edit: Nvm passed

• kenxshiba  commented on Feb. 20, 2018, 5:52 p.m.

Please give an explanation to Sample Output 2. I tried it on a whiteboard and got 17.

• rickywen12345  commented on Feb. 3, 2019, 7:24 p.m.

u can have subtrees in subtrees, so for example if u had 2 trees with the weight of 5, each subtree has 4 different variations (11111,222,4,5)

• aeternalis1  commented on Feb. 20, 2018, 6:05 p.m.

If you would like a detailed explanation, please go to https://slack.dmoj.ca/ and reach me in direct messages. (This could end up being a long conversation so I would prefer it not be in comments)