UVa 679 Dropping Balls

给定一棵二叉树，其最大深度为D，所有叶子节点的深度一致。树中节点按照从上至下、从左至右的顺序进行编号，依次为1, 2, 3, 4……直到2^D - 1。初始时，在节点1放置一个小球，小球将沿着树向下移动。每个内部节点均配备一个开关，初始状态为关闭。每当小球经过某个开关时，该开关的状态会发生翻转：若当前开关处于关闭状态，则小球向左移动；若处于开启状态，则向右移动。这一过程持续到小球抵达叶子节点为止。

多个小球依次从节点1开始下落，最终第I个小球会落在哪一个叶子节点上？输入参数包括叶子节点的深度D和小球总数I，输出第I个小球最终所在的叶子编号。假设I不超过整棵树的叶子数量，并且D≤20。输入数据最多包含1000组。

关键点：

• 是否可以采用模拟方法进行求解？显然不可行。原因在于当I达到最大值2^20 - 1时，结合最多需要走过的层数（即D-1），计算量将非常庞大。对于单组数据而言已经存在较高的时间复杂度，在处理多达1000组数据的情况下必然会导致超时问题。因此必须寻找规律以优化算法。
• 题目描述存在一定的模糊之处：具体而言，在小球通过某节点后才会触发该节点的开关状态变化。

以下是在层数等于4、总共有8个叶子的情况下，各小球下落路径示例：

• 1 - 2 - 4 - 8
• 1 - 3 - 6 - 12
• 1 - 2 - 5 - 10
• 1 - 3 - 7 - 14