CCC '18 S4 - Balanced Trees

View as PDF

Submit solution


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 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


  • 0
    zhenga1  commented on Feb. 12, 2021, 4:58 a.m.

    lmAO you cant even use int in this question cus it will integer overflow. I found out whilst debugging. r/todayilearned


  • 8
    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


  • 0
    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..


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

      You're running out of memory


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

    Slow judge? Or is my code just too slow

    Edit: Nvm passed


  • 6
    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.


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

      This comment is hidden due to too much negative feedback. Click here to view it.


    • 6
      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)