HillHike
SRM 145 · 2003-05-06 · by schveiguy
Problem Statement
A hiker has set out to conquer a hill. The trail guide for the hill lists information known about the hill. First, it lists how tall the hill is, and how far it is to the other side of the hill. Next, it gives a list of landmarks that will be encountered while hiking the hill. The only things that are known about these landmarks are their height, and the order in which they appear along the trail. Finally, on this hill, there are three types of terrain:
_____
/: :\
/ : : \
/ : : \
/ 1 : 2 : 3 \
Type 1: rising terrain. In this type of terrain, the elevation of the hill rises one meter vertically for every meter that is traveled horizontally.
Type 2: level terrain. In this type of terrain, the elevation of the hill remains constant.
Type 3: falling terrain. This terrain's elevation falls one meter vertically for every meter that is traveled horizontally.
All three types of terrain can last for only multiples of one horizontal meter.
You will be given an
Given all of this information, you must return how many different valid paths that the hiker could be facing. A path on the hill is a sequence consisting only of the three types of terrain for the entire distance of the hill. Two paths are different if and only if for at least one horizontal meter, the terrain type of one path is not the same as the terrain type of another path. A path is valid if and only if the path:
1. Starts at height 0 and ends at height 0
2. Has no other locations with height 0, or height below 0 (otherwise it would be two hills, or a valley)
3. Has at least one point where the height is equal to maxHeight (otherwise, the hill would be smaller)
4. Does not go above maxHeight (otherwise, it would be taller)
5. Is laid out such that the landmarks could be placed in the order given at points on the trail. Note that two landmarks cannot appear at the same point on the trail, even if they are at the same height. they must be at least 1 meter apart
If no valid paths exist, return 0.
Notes
- The C++ 64 bit data type is long long
Constraints
- distance will be between 2 and 100, inclusive.
- maxHeight will be between 1 and 50, inclusive.
- landmarks will contain between 0 and 50 elements, inclusive.
- Each element of landmarks will be between 1 and maxHeight, inclusive.
- The return value will be less than or equal to 2^63 - 1 (it will fit into a long)
5
2
{}
Returns: 3
There are three paths with a distance of 5 and a height of 2: _ / \ _/\ /\_ / \ / \ / \ Distance: 12345 12345 12345 Notice that the 2nd and 3rd paths are mirror images, but are considered different. The following path cannot be used because it does not have a height of 2, even though it has a length of 5. ___ / \ 12345 The following path has a height of 2 and a length of 5, but the beginning and ending points are not the only points at height 0: /\ / \_ 12345
2
45
{}
Returns: 0
5
2
{2,2}
Returns: 1
The only path which could contain both landmarks is: _ / \ / \ Distance: 12345
8
3
{2,2,3,1}
Returns: 7
11
3
{3,1,3}
Returns: 9
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HillHike with a public method long long numPaths(int distance, int maxHeight, vector<int> landmarks) · 68 test cases · 2 s / 256 MB per case