UVa 679

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

Summary[edit]

The problem requires us to determine the last move leaf node, (i.e dropping 4 balls in a tree of height 3 will have the last ball in leaf 7).

Explanation[edit]

Because each drop will change a node state from being false to true and otherwise, doing a binary search on the tree will lead us to the solution. We can determine the direction at each node by knowing how many balls passed this node, because the state of a node changes alternatively any odd number of balls will will have the node to be F if it's initial state was F, and T otherwise, and to make it more easy we only need to know the sate of a node when we reach it, hence ball one reaches node 1 at state F and ball 2 reaches node 1 at state T, and by knowing how many balls passed this node we simply solve this problem in the recursive BS approach.

Notes[edit]

Solving this problem using the simulation method will lead to a TLE. Note that we know the starting state of each node which is False, and thus choosing the direction is based on how many balls passed a node.

Implementations[edit]

#include <iostream>
#include <stdio.h>
#include <cmath>

using namespace std;

int MAX_NODE;

int BS(int node, int balls)
{
    int left = node * 2, right = left + 1;
    if (left<MAX_NODE && right<MAX_NODE)
    {
        if (balls%2==0) BS(right, balls/2); // if balls were even then the sate of the current node is T, balls/2 balls pass the right node
        else BS(left, balls/2 + 1); // if balls were odd then the state of the current node is F, balls/2 + 1 balls passed the left node
    }
    else return node; // return the node that has no children "leaf"
}

int main()
{
    int T, D, I;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &D, &I);
        MAX_NODE = pow(2.0, D);
        printf("%d\n", BS(1, I));
    }
    return 0;
}

Input[edit]

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

Output[edit]

12
7
512
3
255

Categories here, use the form [[Category:UVa Online Judge|679]] [[Category: Divide & Conquer (Binary Search) ]], see Categories for a list