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

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 \ge 2~, then the tree consists of a root node with branches to $k$ ~k~ subtrees, such that $2 \le k \le w$ ~2 \le k \le 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 \le 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 \le N \le 10^9)~.

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

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

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

Output Specification

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

Sample Input 1

Sample Output 1

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

Sample Output 2

Comments

7

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

SPOLIER ALERT!

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!

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

7

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

5

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.

-4

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)

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)