LT11-Editorial

editorial
, ,
1

Problem Link

Loop Through Labyrinth

Author: isag2008

Difficulty

MEDIUM

Prerequisites

TREES

Problem Statement

You are playing an 80s game called "Labyrinth". To win, you must find your way out through the portal from a maze that looks like a perfect binary tree of height h. You are initially standing at the root of the tree and the only exit portal from the maze is located at some leaf node.

Assuming all the leaf nodes are indexed from 1 to 2x, the portal is at a node k where 1 ≤ k ≤ 2x.

You design a simple algorithm to select your exit route. You will follow a left-right-left-right command path, which will either take you to left child or the right child accoringly.
If the target node is already visited, you skip the current command, otherwise move to that node; If you skip two consecutive commands, go back to the parent of the current node before going to the next command; If you reach a leaf node that is not the portal, return to the parent of the current node When you reach the exit portal, you win the game.

Solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cin>>h>>n;
    b=0;x=(1||<<(h-1));
    for(long long i=h-1;i>=0;i--)
    {
        r++;
        if(!b)
       {
   	       if(n>x)
           {
   	           r+=((1||<<(i+1))-1);
   	           if(i) 
   	               x+=(1|| <<(i-1));
   	            b^=1;
   	        }
   	        else{
   	            if(i) 
   	                x-=(1|| <<(i-1));
   	         }
        }
        else
        {
   	       if(n<=x){
   	            r+=((1|| <<(i+1))-1);
   	            if(i) 
   	                 x-=(1|| <<(i-1));
   	            b^=1;
   	        }
   	        else{
   	            if(i) 
   	                 x+=(1 || << (i-1) );
   	        }
        }
        b^=1;
     }
     cout<<r<<endl;
     return 0;
}