FoxAndMountain
SRM 557 · 2012-06-05 · by cgy4ever
Problem Statement
Her trip can be described as a sequence of (n+1) integers: h[0], h[1], ..., h[n]. These values represent altitudes visited by Fox Ciel during the trip, in order. Fox Ciel does not remember the precise sequence, but she remembers the following:
- for each i, h[i] >= 0
- h[0] = 0
- h[n] = 0
- for each i, abs(h[i+1]-h[i]) = 1
The last condition means that in each step the altitude of Fox Ciel either increased by 1, or decreased by 1. We will call the two types of steps "steps up" and "steps down", respectively. Steps up will be denoted 'U' and steps down will be denoted 'D'.
You are given the
Let X be the number of different trips that match everything that Fox Ciel remembers. (Note that she may be mistaken, hence X may also be zero.) Compute and return the value (X modulo 1,000,000,009).
Constraints
- n will be between 1 and 50, inclusive.
- history will contain between 1 and n characters, inclusive.
- Each character in history will be either 'U' or 'D'.
4 "UUDD" Returns: 1
Fox Ciel remembers the entire history of her trip. The corresponding sequence of altitudes is {0, 1, 2, 1 ,0}.
4 "DUUD" Returns: 0
Fox Ciel is mistaken. As n=4 and history="DUUD", the corresponding sequence of altitudes has to be {0, -1, 0, 1, 0}. However, all altitudes must be non-negative, so there is no matching trip.
4 "UU" Returns: 1
The complete history must be "UUDD".
49 "U" Returns: 0
It is not hard to see that for an odd n the answer has to be 0.
20 "UUUDUUU" Returns: 990
50 "U" Returns: 946357703
Don't forget to use the modulo operations during the calculation.
Submissions are judged against all 145 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoxAndMountain with a public method int count(int n, string history) · 145 test cases · 2 s / 256 MB per case