题目名称	1643. [UVa 679]小球下落
输入输出	`fballs.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	sywgz 于2014-05-24加入
开放分组	全部用户
提交状态
分类标签	树二叉树 UVa
	分享题解

通过：97，提交：152，通过率：63.82%
521	100	0.000 s	0.00 MiB	C++
大秦帝国	100	0.000 s	0.00 MiB	C++
Richard	100	0.000 s	0.00 MiB	C++
Twilight_Dark	100	0.000 s	0.00 MiB	C++
ZZZ	100	0.000 s	0.00 MiB	C++
dsn	100	0.000 s	0.00 MiB	C
dsn	100	0.000 s	0.00 MiB	C
syzhaoss	100	0.000 s	0.00 MiB	C++
┭┮﹏┭┮	100	0.000 s	0.00 MiB	C++
Adam	100	0.000 s	0.00 MiB	C++

本题关联比赛
图论练习和一些常规题
图论练习和一些常规题

关于小球下落的近10条评论(全部评论)
弄了半天才一个A ZZZ 2021-12-23 21:27 10楼
测试点这么水的吗…… 夜莺 2021-08-04 00:09 9楼
那个点居然真的是样例。。。雨季 2017-11-07 19:51 8楼
刷过水题！！虽然蒟蒻找规律用了好久…… 浮生随想 2016-11-13 16:02 7楼
已经刷了两个只有1个测试点的题了这_不错 2016-04-17 20:18 6楼
这种题目。。。。要么只有-1结束要么就输入n搞什么飞机。。。。害得我纠结了好半天啊啊啊 Twist Fate 2016-03-26 15:33 5楼
数学方法（凑公式）过掉的。。 liu_runda 2016-02-16 19:11 4楼
为何就一个点测试点只有一个的题，都是冷门题。 ————神兽 NVIDIA 2015-11-24 11:49 3楼
QwQ居然只有一个点，话说这个点不会就是样例吧→_→ devil 2015-03-20 10:37 2楼
只有一个点是怎么回事 HouJikan 2014-08-30 20:10 1楼

1643. [UVa 679]小球下落

★★ 输入文件：fballs.in 输出文件：fballs.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

许多的小球一个一个的从一棵满二叉树上掉下来组成一个新满二叉树，每一时间，一个正在下降的球第一个访问的是非叶子节点。然后继续下降时，或者走右子树，或者走左子树，直到访问到叶子节点。

决定球运动方向的是每个节点的布尔值。最初，所有的节点都是false，当访问到一个节点时，如果这个节点是false，则这个球把它变成 true，然后从左子树走，继续它的旅程。如果节点是true，则球也会改变它为false，而接下来从右子树走。满二叉树的标记方法如下图。

因为所有的节点最初为false，所以第一个球将会访问节点 $1$，节点 $2$ 和节点 $4$，转变节点的布尔值后在在节点 $8$ 停止。第二个球将会访问节点 $1、3、6$，在节点 $12$ 停止。明显地，第三个球在它停止之前，会访问节点 $1、2、5$，在节点 $10$ 停止。

现在你的任务是，给定新满二叉树的深度 $d$ 和下落的小球的编号 $i$ ，可以假定 $i$ 不超过给定的新满二叉树的叶子数，写一个程序求小球停止时的叶子序号 $p$。

【输入格式】

第一行一个整数$n$，表示询问的个数。

接下来$n$行，每行两个整数$d,i(2\leq d\leq 20,1\leq i\leq 524288)$，表示二叉树的深度和下落的小球的编号。

接下来一行一个整数$-1$表示输入结束。

【输出格式】

输出包含$n$行，每行一个整数表示对应询问的小球停止时的叶子序号。

【样例输入】

【样例输出】

【来源】

uva679