[抄题报告][UVA]UVA – 679 Dropping Balls – 小球下落

题目地址:

https://cn.vjudge.net/problem/UVA-679

题目描述:

(爱词霸翻译)

Background
背景

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.
K个球一个接一个地从完全二叉树结构的FBT树掉落。每次被丢弃的球首先访问头结点。然后继续向下移动,要么是左子树的路径,或是右子树的路径,直到它停止在一个FBT的叶节点。为了确定一个球的运动方向,每一个非终端节点都设置一个标志,它有两个值,要么是false,要么是true。最初,所有的标志都是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.
当访问非终端节点时,如果该节点上的标志当前值为false,则该球将首先切换该标志的值,即从false到true,然后按照该节点的左子树继续向下移动。否则,它也会切换这个标志的值,即从true到false,但是会按照这个节点的右边子树继续移动。此外,FBT所有节点的顺序编号,从1开始在深度为1的节点,然后在深度2,等等。任何深度上的节点都从左到右编号。

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.
例如,图1表示具有节点号1, 2, 3、……15的最大深度4的完全二叉树。由于所有的标志都被设置为false,所以被丢弃的第一个球将在节点1、节点2和节点4上切换标志值,然后才停止在位置8。被丢弃的第二个球将在节点1、节点3和节点6上切换标志的值,并在位置12处停止。显然,被丢弃的第三个球将在节点1、节点2和节点5停止标志的值,然后在位置10处停止。

搜狗截图20170715201600

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.
现在考虑一些测试用例,其中每个测试将给出两个值。第一个值D,FBT的最大深度,第二个是I,第I个球被丢弃。你可能认为I的值不会超过给定的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.
请编写一个程序来确定每个测试用例的停止位置p。
对于每个测试用例,两个参数d和i的范围如下所示:
2≤D≤20,和1≤I≤524288。

The Input
输入

Contains l + 2 lines.
Line 1 l the number of test cases
Line 2 D1 I1 test case #1, two decimal numbers that are separated by one blank

Line k + 1 Dk Ik test case #k
Line l + 1 Dl Il test case #l
Line l + 2 -1 a constant ‘-1’ representing the end of the input file
输入包含l + 2行。
第1行         l         为测试用例的数量
第2行         D1 I1      测试用例# 1,两个小数,用一个空格隔开

第k + 1行  DK IK     测试用例# K
第L + 1行  DL IL      测试用例# L
第L + 2行    -1          一个常数“-1”表示输入文件的结尾

The 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
输出包含L行。
第1行为停止位置P为测试用例# 1

第k行为停止位置P为测试用例# K

第L行为停止位置P为测试用例# L

Sample Input
输入示例

5
4 2
3 4
10 1
2 2
8 128
-1

Sample Output
输出示例

12
7
512
3
255


 

我的分析

这题很容易想模拟小球下降的过程,不停地循环小球下落的事件,最后到一定次数输出结果。可是这样很容易就超时了。

我尝试将下落次序与叶子节点位置进行对应,能看出一点规律,但无法了解真正的规律,无从下手。

无奈最终看了书,书上的解释是:“每个小球都会落在根节点上,因此前两个小球必然是一个在左子树,一个在右子树。一般地,只需看小球编号的奇偶性,就能知道它是最终在哪棵子中。对于那些落入根节点左子树的小球来说,只需知道该小球是第几个落在根的左子树里的,就可以知道它下一步往左还是往右了。以此类推,直到小球落到叶子上。”

到这里我觉得很惊讶。我知道第奇数个小球往左,第偶数个小球往右。可是我没想过到了左右子树之后,还可以继续遵循这条规律。我只是将I作为一个结束条件,而书中将I不断地修剪:

“如果使用题目中给出的编号I,则当I是奇数时,它是往左走的第(I + 1) / 2个小球;当I是偶数时,它是往右走的第I / 2个小球。”

我对于除以2的理解是,在扔入一个新的球的时候,原先扔过的球,有奇数有偶数,分别走向左右子树(或是一个都没扔过、或是只走过左子树)。那么如果一个奇数号的球当经过头结点,到左子树时,必须除去那些走向右子树的球数,故需要除掉一半。偶数号球同理。

不过为什么要+1再除以2,我想不通,但事实却是需要先+1.因为第一个球只有+1再除以2才能等于1,如果不+1就是0了。

代码

先上一个5分钟内想出来的超时代码:

再上抄书的代码: