Statistics

Problem Statement for "TrafficCongestion"

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. Let X be the smallest number of cars we need in order to do so. Compute and return the value X modulo 1,000,000,007.

Definition

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

Constraints

  • treeHeight will be between 0 and 1,000,000, inclusive.

Examples

  1. 1

    Returns: 1

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

  2. 2

    Returns: 3

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

  3. 3

    Returns: 5

  4. 585858

    Returns: 548973404

  5. 0

    Returns: 1

  6. 4

    Returns: 11

  7. 5

    Returns: 21

  8. 6

    Returns: 43

  9. 7

    Returns: 85

  10. 8

    Returns: 171

  11. 9

    Returns: 341

  12. 10

    Returns: 683

  13. 11

    Returns: 1365

  14. 12

    Returns: 2731

  15. 13

    Returns: 5461

  16. 14

    Returns: 10923

  17. 15

    Returns: 21845

  18. 16

    Returns: 43691

  19. 17

    Returns: 87381

  20. 18

    Returns: 174763

  21. 19

    Returns: 349525

  22. 20

    Returns: 699051

  23. 25

    Returns: 22369621

  24. 30

    Returns: 715827883

  25. 35

    Returns: 906492091

  26. 40

    Returns: 7746720

  27. 45

    Returns: 247895029

  28. 50

    Returns: 932640890

  29. 55

    Returns: 844508266

  30. 60

    Returns: 24264334

  31. 70

    Returns: 846677507

  32. 80

    Returns: 997760765

  33. 90

    Returns: 707015872

  34. 100

    Returns: 984247526

  35. 200

    Returns: 999630053

  36. 300

    Returns: 548033842

  37. 500

    Returns: 260322005

  38. 700

    Returns: 120478547

  39. 1000

    Returns: 458948807

  40. 3000

    Returns: 443800320

  41. 5000

    Returns: 573461717

  42. 10000

    Returns: 270407868

  43. 30000

    Returns: 777260071

  44. 50000

    Returns: 12110301

  45. 100000

    Returns: 71815678

  46. 500000

    Returns: 311754146

  47. 1000000

    Returns: 490028042

  48. 999999

    Returns: 745014024

  49. 679379

    Returns: 19761069

  50. 191807

    Returns: 565569761

  51. 590524

    Returns: 789815123

  52. 730706

    Returns: 862680469

  53. 606763

    Returns: 438659788

  54. 531434

    Returns: 322697396

  55. 206743

    Returns: 548124278

  56. 260716

    Returns: 134950712

  57. 80188

    Returns: 302907143

  58. 309019

    Returns: 305102876

  59. 850657

    Returns: 419343001

  60. 10464

    Returns: 874709788

  61. 577394

    Returns: 187290663

  62. 756092

    Returns: 954114375

  63. 460375

    Returns: 30653388

  64. 25693

    Returns: 520134322

  65. 855602

    Returns: 263216797

  66. 454356

    Returns: 756144638

  67. 53077

    Returns: 235894722

  68. 110324

    Returns: 46881352

  69. 388295

    Returns: 520690119

  70. 347315

    Returns: 909029981

  71. 514547

    Returns: 893500017

  72. 101646

    Returns: 704924855

  73. 372640

    Returns: 298024908

  74. 627719

    Returns: 484506965

  75. 257690

    Returns: 257076174

  76. 79948

    Returns: 7888535

  77. 30915

    Returns: 32206084

  78. 265009

    Returns: 378700405

  79. 747474

    Returns: 822915066

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: