UVA 679 Dropping Balls 由小见大，分析思考 二叉树放小球，开关翻转，小球最终落下叶子编号。

A number of
K
balls are dropped one by one from the root of a fully binary tree structure FBT. Each
time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows
the path of the left subtree, or follows the path of the right subtree, until it stops at one of the leaf
nodes of FBT. To determine a ball’s moving direction a flag is set up in every non-terminal node with
two values, either
false
or
true
. Initially, all of the flags are
false
. When visiting a non-terminal node
if the flag’s current value at this node is
false
, then the ball will first switch this flag’s value, i.e., from
the
false
to the
true
, and then follow the left subtree of this node to keep moving down. Otherwise,
it will also switch this flag’s value, i.e., from the
true
to the
false
, but will follow the right subtree of
this node to keep moving down. Furthermore, all nodes of FBT are sequentially numbered, starting at
1 with nodes on depth 1, and then those on depth 2, and so on. Nodes on any depth are numbered
from left to right.
For example, Fig. 1 represents a fully binary tree of maximum depth 4 with the node numbers 1,
2, 3, ..., 15. Since all of the flags are initially set to be
false
, the first ball being dropped will switch
flag’s values at node 1, node 2, and node 4 before it finally stops at position 8. The second ball being
dropped will switch flag’s values at node 1, node 3, and node 6, and stop at position 12. Obviously,
the third ball being dropped will switch flag’s values at node 1, node 2, and node 5 before it stops at
position 10.
Fig. 1: An example of FBT with the maximum depth 4 and sequential node numbers.
Now consider a number of test cases where two values will be given for each test. The first value is
D
, the maximum depth of FBT, and the second one is
I
, the
I
-th ball being dropped. You may assume
the value of
I
will not exceed the total number of leaf nodes for the given FBT.
Please write a program to determine the stop position
P
for each test case.
For each test cases the range of two parameters
D
and
I
is as below:
2

D

20
;
and
1

I

524288
:
Input
Contains
l
+ 2
lines.
Line 1
l
the number of test cases
Line 2
D
1
I
1
test case #1, two decimal numbers that are separated by one blank
...
Line
k
+ 1
D
k
I
k
test case #
k
Line
l
+ 1
D
l
I
l
test case #
l
Line
l
+ 2
-1
a constant ‘
-1
’ representing the end of the input file
Output
Contains
l
lines.
Line 1   the stop position
P
for the test case #1
...
Line
k
the stop position
P
for the test case #
k
...
Line
l
the stop position
P
for the test case #
l
Sample Input
5
4  2
3  4
10  1
2  2
8  128
-1
Sample Output
12
7
512
3
255

/**
题目：UVA 679 Dropping Balls
链接：https://vjudge.net/problem/UVA-679
题意：lrj算法竞赛入门经典P148. eg6-6
分析：深度为d， 小球书为n。

d=1     ○
d=2   ○   ○
d=3  ○ ○ ○ ○

第一个小球：编号1节点关闭状态，所以向左子树走。编号1节点开启。
第二个小球：编号1节点开启状态，所以向右子树走。编号1节点关闭。
第三个小球：编号1节点关闭状态，所以向左子树走。编号1节点开启。
第四个小球：编号1节点开启状态，所以向右子树走。编号1节点关闭。
。
。
。
容易发现，对于编号1节点，要放入1-n个小球。那么奇数编号的小球往左子树走，偶数编号的小球往右子树走。
到达了左子树编号为2的节点，有若干个小球重新编号为1-m。那么又可以这样处理。

由于我们要判断第n个小球最终的叶子位置。
k表示答案，初始k=1.
if(n%2==0) k = 2*k+1, n = n/2;
else k = 2*k, n = n/2+1;

if(n==1) return k;

思路：
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int maxn = 1e5+100;
const int mod = 1e9+7;
int main()
{
    int T;
    int d, n;
    LL k;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&d,&n);
        k = 1;
        d--;
        while(n>0&&d--){
            if(n%2==0) k = 2*k+1, n = n/2;
            else k = 2*k, n = n/2+1;
        }
        printf("%lld
",k);
    }
    cin>>T;
    return 0;
}