九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1425-九度Online Judge,用代码记录你的成长之路!

题目1425:How Many Nodes

时间限制:2 秒

内存限制:32 兆

特殊判题:

提交:86

解决:30

题目描述:

        Given one binary tree, whose nodes are regarded as "section". 

        The root is regarded as the section [0,n] where n is one positive integer.

        Then for any single node who has section [L, R] (L+1 is less than R), its left son is assigned with the section [L, (L+R) DIV 2] and its right son is assigned with the [ (L+R) DIV 2, R] one. For example, the node with section [0,4] will assign section [0,2] and [2,4] for its left and right son respectively.

        Then for any integer pair (x,y) where x<y and 0<=x,y<=n,we could find a unique way to choose some nodes out of the tree and satisfied the following conditions:

        (1) All nodes are distinct;

        (2) For any chosen node, [x,y] must completely cover the section [L,R] the node has, where x<=L<R<=y;

        (3) The number of node must be minimized.

        Now hwh( a "SB" in ACM_DIY) randomly gives one integer pair(x,y) , what is the expectation of the nodes we choose ? Suppose all the integer pair(x,y) are equally likely to be chosen.

输入:

        The first line is one integer T indicates the number of the test cases. (T <= 100)

        Then for every case, only one line containing a positive integers n .(1 ≤n≤10^6 )

输出:

        Output one line,the expectation of the nodes we choose. You must output the fraction in lowest terms.

样例输入:
4
1
2
3
4
样例输出:
1/1
1/1
7/6
13/10
提示:

        In the second sample, n=2, then the root has section[0,2], the tree is:

        [0,2]

         /    \

    [0,1]   [1,2]

        For pair(0,2) , we choose the Node with section [0,2].

        For pair(0,1), we choose the Node with section [0,1].

        For pair(1,2), we choose the Node with section [1,2].

        As hwh may choose all the 3 pairs in the probability of 1/3 , then the expectation of node we choose is 1*(1/3)+1*(1/3)+1*(1/3)=1


        In the third sample, n=3, then the root has section[0,3], the tree is:

        [0,3]

         /    \

  [0,1]   [1,3]

              /  \

       [1,2]   [2,3]


        For pair(0,3) , we choose the Node with section [0,3].

        For pair(0,2), we choose the Node with section [0,1] and the Node with section[1,2].

        For pair(0,1), we choose the Node with section [0,1].

        For pair(1,3), we choose the Node with section [1,3](Since [1,2] [2,3] is not valid with condition (3) ).

        For pair(1,2), we choose the Node with section [1,2].

        For pair(2,3), we choose the Node with section [2,3].

        As hwh may choose all the 6 pairs in the probability of 1/6 , then the expectation of node we choose is 1*(1/6)+2*(1/6)+1*(1/6)+1*(1/6)+1*(1/6)+1*(1/6)=7/6

来源:
第四届ACM_DIY群程序设计竞赛