TrafficCongestion
SRM 585 · 2013-06-25 · by wrong
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
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.
Constraints
- treeHeight will be between 0 and 1,000,000, inclusive.
1 Returns: 1
In this case, one car can visit all the cities.
2 Returns: 3
Here is one way to visit all cities exactly once by three cars:
3 Returns: 5
585858 Returns: 548973404
0 Returns: 1
Submissions are judged against all 79 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TrafficCongestion with a public method int theMinCars(int treeHeight) · 79 test cases · 2 s / 256 MB per case