SP22532 COOLPROB - Cool Problem

Prem Kamal went to Tokyo, where one day he decided to tour the city. He will be visiting a number of regions. In each region, there are N buildings of heights H $ _{1,} $ H $ _{2...} $ H $ _{N} $ . A region is represtented across x-axis with buildings placed at positions 1..N, next to each other in a _random_ order (let the order be represented as h $ _{1,} $ h $ _{2...} $ h $ _{N} $ ). Prem Kamal, known for his cool acts, decides to calculate the coolness of the region. Each position has some coolness score (C(i)) associated with it. But that coolness score is added only if there is a cool building at that position. A building is cool if it is _strictly taller_ than its left and right neighbor (_first and last buildings are not considered cool_). Moreover, since it gets boring going through the same region, the coolness score of later positions is lesser. **See the formal definitions carefully.** _Formal Definitions:_ C(1) = 1 C(i) = C(i-1)\*0.99 The heights H $ _{i} $ are generated as follows: H $ _{1} $ = X H $ _{i} $ = (H $ _{i-1} $ \* X) mod **10007** Given N and X, what is the expected overall coolness of the region. **Constraints** T = 2000 1

N/A

N/A