Construction of Chand Baori
Time limit1sMemory limit1024 MB
Count the descent routes along one face of an N-level stepped well and report whether that count is below the pilgrim number M.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Math
- Solved
- No attempts yet
Problem
The Indian stepped well Chand Baori is, with some simplifications, a pyramid tapering down. The faces of the pyramid are made up of rows of trapezoid stairs, which can be used to descend to the water. The first (lowest) level is a single stairway with two flights of stairs, one on the left and one on the right. The second level has two such stairways, and so on.
To visit the "Harshat Mata" shrine, dedicated to the goddess of happiness and joy, pilgrims need to cleanse themselves in the waters of the well. That means descending to the very bottom. Pilgrims on their way to the water can only descend or walk horizontally along the current level. They cannot climb up.
The builders of the well want the number of possible ways to descend to be no less than the number of pilgrims. Two paths are different if there is a level with a different stairway used for descending, or if the same stairway is used with a different flight.
Input
The first line contains two integers and , the number of levels in the well and the number of pilgrims descending along a single face, respectively (, ).
Output
The output must contain "Harshat Mata" if the number of possible ways to descend along one face of the well is less than the given number of pilgrims (also for one face). Otherwise, the output must contain "Nope".
Hint
For a two-level well there are eight different ways of descent, shown in the picture. Parts of the same route are marked with the same digit.
