Problem1631--猜数字 (10分)

1631: 猜数字 (10分)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MB

Description

老师手里有一个数字x
小明不知道老师手里的数字是多少,小明要猜测老师手中的数字是多少。
最开始,老师告诉小明这个数字是[1,n]范围内的一个整数。
接下来,小明会重复下面的步骤直到猜对为止:
1. 假设小明当前知道老师手中的数字是一个范围在[l,r]内的整数,则小明会取y=\frac{(l+r)}{2}(向下取整)
2. 小明告诉老师:“我猜老师手里的数字是y
3. 老师做出回答:
    (1)如果y<x,老师会告诉小明:“小了”
    (2)如果y=x,老师会告诉小明:“猜对了”
    (3)如果y>x,老师会告诉小明:“大了”
4. 小明根据老师的回答进行分析:
    (1)如果老师告诉小明“小了”,则说明x不是[l,y]范围内的整数,小明知道了x一定是[y+1,r]范围内的整数,随后回到步骤1,开始下一轮猜数
    (2)如果老师会告诉小明“猜对了”,则结束猜数
    (3)如果老师会告诉小明“大了”,则说明x不是[y,r]范围内的整数,小明知道了x一定是[x,y-1]范围内的整数,随后回到步骤1,开始下一轮猜数
实际上,按照上面的步骤,只要确定了xn,就可以确定小明的猜数轮数,以及小明每一轮猜的数字。
现在给出x,n,求小明的猜数轮数,以及小明每一轮猜的数字。

Input

第一行一个整数T(1\le T\le 100),表示测试用例的组数
接来来T行每行两个整数x,n(1\le x\le n\le 10^9)表示一组测试用例

Output

对于每组测试用例:
第一行输出一个整数num表示小明的猜数轮数
接下来一行输出num个数字,表示小明每轮猜的数字。

Sample Input Copy

5
1 1
2 10
5 10
8 1000000
666 1000000000

Sample Output Copy

1  
1
2
5 2
1
5
20
500000 250000 125000 62500 31250 15625 7812 3906 1953 976 488 244 122 61 30 15 7 11 9 8
30
500000000 250000000 125000000 62500000 31250000 15625000 7812500 3906250 1953125 976562 488281 244140 122070 61035 30517 15258 7629 3814 1907 953 476 714 595 654 684 669 661 665 667 666

HINT

注意,第一组测试用例,即使[1,1]范围内的整数只有1,但小明也需要进行一次猜测才会结束步骤。

Source/Category