Statistics

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

  1. 0

    Returns: 1

  2. 1

    Returns: 1

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

  3. 2

    Returns: 3

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

  4. 3

    Returns: 5

  5. 4

    Returns: 11

  6. 5

    Returns: 21

  7. 6

    Returns: 43

  8. 7

    Returns: 85

  9. 8

    Returns: 171

  10. 9

    Returns: 341

  11. 10

    Returns: 683

  12. 11

    Returns: 1365

  13. 12

    Returns: 2731

  14. 13

    Returns: 5461

  15. 14

    Returns: 10923

  16. 15

    Returns: 21845

  17. 16

    Returns: 43691

  18. 17

    Returns: 87381

  19. 18

    Returns: 174763

  20. 19

    Returns: 349525

  21. 20

    Returns: 699051

  22. 21

    Returns: 1398101

  23. 22

    Returns: 2796203

  24. 23

    Returns: 5592405

  25. 24

    Returns: 11184811

  26. 25

    Returns: 22369621

  27. 26

    Returns: 44739243

  28. 27

    Returns: 89478485

  29. 28

    Returns: 178956971

  30. 29

    Returns: 357913941

  31. 30

    Returns: 715827883

  32. 31

    Returns: 1431655765

  33. 32

    Returns: 2863311531

  34. 33

    Returns: 5726623061

  35. 34

    Returns: 11453246123

  36. 35

    Returns: 22906492245

  37. 36

    Returns: 45812984491

  38. 37

    Returns: 91625968981

  39. 38

    Returns: 183251937963

  40. 39

    Returns: 366503875925

  41. 40

    Returns: 733007751851

  42. 41

    Returns: 1466015503701

  43. 42

    Returns: 2932031007403

  44. 43

    Returns: 5864062014805

  45. 44

    Returns: 11728124029611

  46. 45

    Returns: 23456248059221

  47. 46

    Returns: 46912496118443

  48. 47

    Returns: 93824992236885

  49. 48

    Returns: 187649984473771

  50. 49

    Returns: 375299968947541

  51. 50

    Returns: 750599937895083

  52. 51

    Returns: 1501199875790165

  53. 52

    Returns: 3002399751580331

  54. 53

    Returns: 6004799503160661

  55. 54

    Returns: 12009599006321323

  56. 55

    Returns: 24019198012642645

  57. 56

    Returns: 48038396025285291

  58. 57

    Returns: 96076792050570581

  59. 58

    Returns: 192153584101141163

  60. 59

    Returns: 384307168202282325

  61. 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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: