JOIN
Get Time

   Problem Statement  

 Problem Statement for TrafficCongestionDivTwo

Problem Statement

    

There are some cities and some roads connecting them together. The road network has the topology of a perfect binary tree (see below for a picture), in which the cities are nodes and the roads are edges.



You are given the int treeHeight giving the height of the tree. (The height of a perfect binary tree is the number of edges on the path between the root node and any leaf node.) Thus, there are 2^(treeHeight+1)-1 cities and 2^(treeHeight+1)-2 roads in total.



The picture below shows how the road network looks like when treeHeight = 2.





We want to send some cars into the road network. Each car will be traveling from its starting city to its destination city without visiting the same city twice. (Note that the route of each car is uniquely determined by its starting and its destination city.) It is possible for the starting city to be equal to the destination city, in that case the car only visits that single city.



Our goal is to send out the cars in such a way that each city will be visited by exactly one car. Compute and return the smallest number of cars we need in order to do so.

 

Definition

    
Class:TrafficCongestionDivTwo
Method:theMinCars
Parameters:int
Returns:long
Method signature:long theMinCars(int treeHeight)
(be sure your method is public)
    
 

Notes

-The answer will always fit into a 64-bit signed integer data type.
 

Constraints

-treeHeight will be between 0 and 60, inclusive.
 

Examples

0)
    
1
Returns: 1

In this case, one car can visit all the cities.



1)
    
2
Returns: 3

Here is one way to visit all cities exactly once by three cars:



2)
    
3
Returns: 5
3)
    
10
Returns: 683
4)
    
60
Returns: 768614336404564651

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 585 Round 1 - Division II, Level Two