CCC '18 S4 - Balanced Trees - DMOJ: Modern Online Judge

CCC '18 S4 - Balanced Trees

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$ $1$ always consists of a single node. Otherwise, if the weight of a perfectly balanced tree is $w$ $w$ and $w \ge 2$ $w \geq 2$ , then the tree consists of a root node with branches to $k$ $k$ subtrees, such that $2 \le k \le w$ $2 \leq k \leq w$ . In this case, all $k$ $k$ subtrees must be completely identical, and be perfectly balanced themselves.

In particular, all $k$ $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$ $k$ subtrees does not exceed $w$ $w$ , the weight of the overall tree. For example, if a perfectly balanced tree of weight $8$ $8$ has $3$ $3$ subtrees, then each subtree would have weight $2$ $2$ , since $2+2+2 = 6 \le 8$ $2 + 2 + 2 = 6 \leq 8$ .

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

Input Specification

The input will be a single line containing the integer $N$ $N$ $(1 \le N \le 10^9)$ $(1 \leq N \leq 10^{9})$ .

For $5$ $5$ of the $15$ $15$ marks available, $N \le 1\,000$ $N \leq 1 000$ .

For an additional $2$ $2$ of the $15$ $15$ marks available, $N \le 50\,000$ $N \leq 50 000$ .

For an additional $2$ $2$ of the $15$ $15$ marks available, $N \le 10^6$ $N \leq 10^{6}$ .

Output Specification

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

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

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

Sample Input 2

Copy

Sample Output 2

Copy

Comments

13

elliss commented on Feb. 4, 2019, 4:25 p.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

2

RAiNcalleER commented on Feb. 3, 2022, 10:07 p.m.

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

0

Summertony717 commented on Jan. 28, 2019, 3:43 a.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..

13

Plasmatic commented on Jan. 28, 2019, 4:02 a.m.

You're running out of memory