把灯关上

题目

有一颗二叉树, 最大深度为 D(1 <= D <= 26), 且所有叶子的深度都相同. 所有的节点从上到下从左到右编号为1, 2, 3, … , 2^D - 1. D 的意思是二叉树的高度, 比如当 D = 1 时, 二叉树只有一个节点, 当 D = 2 时, 二叉树有两层, 节点为1, 2, 3, 当 D = 3 时, 节点为 1, 2, 3, 4, 5, 6, 7. 以此类推. 在节点 1 处放一个小球, 它会往下落. 每个内节点上都有一个开关, 初始全部关闭, 当每次有小球落到一个开关上时, 它的状态都会改变. 当小球到达一个内节点时, 如果该节点上的开关关闭, 则往左走, 否则往右走, 直到走到叶子节点.

输入包括两个数, 树的深度D和小球的个数I(1 <= N <= 500000), 并用空格隔开

提示

题目意思很简单, 但是小数据可以模拟, 但是大数据模拟会超时. 试着换一种思路, 每个小球都会落在根节点上, 因此前两个小球必然是一个在左子树, 一个在右子树. 一般的,
只需看小球编号的奇偶性, 就能知道他是最终在哪棵子树中. 对于那些落入根节点左子树的小球来说, 只需知道该小球是第几个落在根的左子树里的, 就可以知道它下一步往左还是往右走.
以此类推, 直到小球落到叶子上. 使用题目中给出的编号 n,则当 n 为奇数时, 它是往左走的第(n + 1)/ 2 个小球, 当 n 为偶数时, 它是往右走的第 n / 2 个小球.
这样就可以直接模拟最后一个小球的路线.

找规律

public class OJ326 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()) {
            int depth = sc.nextInt(), numOfBalls = sc.nextInt() - 1;
            int results = 1;

            for (int i = 1; i < depth; i++) {
                int dir = numOfBalls % 2;
                results = results * 2 + dir;

                numOfBalls /= 2;
            }

            System.out.println(results);
        }
    }
}