spoj ⟿ classical ⟿ treenum2 ⟿ The art of tree numbers

you can get the problem statement from here.

nice little problem.

tree_num is the sum of distinct powers of 3 with natural exponent. we can solve this problem easily if we can realize that any natural number is sum of distinct powers of 2 with natural exponent.

one illustration that any natural number is the sum of distinct powers of 2 with natural exponent is the binary representation of natural numbers. as with natural numbers we can also represent the tree numbers in binary representation and the conversion’s also similar, instead of sum of powers of 2, it is sum of powers of 3.

https://gist.github.com/2a89c52b3bef33edb85a

PS: be careful with IO. i got tle for cin/cout with ios::sync_with_stdio(0);cin.tie(0);. so either use fast io or scanf, printf

Screenshot from 2015-05-29 19:26:37

Advertisements

3 thoughts on “spoj ⟿ classical ⟿ treenum2 ⟿ The art of tree numbers

    1. Try to solve how to
      find the sum of natural number upto n i.e (n*(n + 1)) / 2(without using the formula of-course) by using the binary representation of n;
      then you can easily understand it;

      how to solve the sum of first n natural numbers using binary representation; think about at each place of binary representation how many 1’s appear upto that number

      for example:
      take n = 10
      the numbers are
      0000
      0001
      0010
      0011
      0100
      0101
      0110
      0111
      1000
      1001
      1010
      —————– adding numbers in binary representation
      3*(2**3) + 4*(2**2) + 5(2**1) + 5*(2**0)

      binx = ‘1010’
      All we have to do is find those coefficients.
      number of one’s in 1st place = 3 which is actually int(binx[1: ]) and as there are one’s then it is implied that there are a whole set of numbers (0 – 8) we have to sum up; as they are complete in the sense number of 1’s are equal(log2(n) + 1) like wise you can continue..

      as you just solved for natural numbers it is quite easy how to sum up tree numbers
      reply me, If you still have any doubts..

      note: in case of tree numbers the answer for 10 is
      3*(3**3) + 4*(3**2) + 5*(3**1) + 5*(3**0)

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s