ZeroJudge A249: Dropping Balls

UVa 00679 – Dropping Balls

K balls are dropping one by one from the root of a complete binary tree (CBT). When a ball encounters a non-terminal node, it may go left or right subtree until it reaches a terminal node (i.e., a leaf node). The decision of whether the ball should go left or right at a non-terminal node is controlled by two values: true or false.

If the current value of the non-terminal node is false, the ball will go to the left subtree when it arrives, but the value will change to true. If the current value of the non-terminal node is true, the ball will go to the right subtree when it arrives, but the value will change to false.

Please note: Initially, all non-terminal node values are false. Additionally, in a complete binary tree, all nodes are sequentially numbered from top (depth = 1) to bottom, from left to right. Please refer to the following diagram.

ZeroJudge A249題目解說用圖

For example, in the above tree with depth 4, the first ball dropping will pass through nodes 1, 2, 4, and finally land in node 8. The second ball dropping will pass through nodes 1, 3, 6, and finally land in node 12. The third ball dropping will pass through nodes 1, 2, 5, and finally land in node 10.

Given the depth D of a complete binary tree and the I-th ball dropping, please write a program to calculate the node number where the I-th ball lands in a terminal node.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line of input contains an integer, indicating how many sets of test data will follow.
Each set of test data consists of a single line containing two integers, D and I, where D represents the depth of the complete binary tree (2 <= D <= 20) and I represents the index of the dropping ball (1 <= I <= 524288).		For each set of test data, output a single line containing the node number where the I-th ball lands in a terminal node.
5
4 2
3 4
10 1
2 2
8 128		12
7
512
3
255

Thought Process

Run a for loop for D times. If L is even, move right (current position * 2 + 1), then L /= 2. If L is odd, move left (current position * 2), then L = L / 2 + 1. Output the final position.

Sample Code－ZeroJudge A249: Dropping Balls

#include <iostream>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int D, L;
        cin >> D >> L;
        int pos = 1;
        for (int j = 0; j<D; j++)
        {
            if (L % 2 == 0)
            {
                L /= 2;
                pos = (pos*2)+1;
            }
            else
            {
                L = (L/2)+1;
                pos *= 2;
            }
        }
        cout << pos/2 << "\n";
    }
}

//ZeroJudge A249
//Dr. SeanXD
Tags

Related Posts

Comments