## 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<=10^3

2<=X<=10^3

**Input**First line consists of the number of test cases

**T**.

**T**test cases follow. Each test cases consist of a space separated integers

**N**and

**X**.

**Output**For each teste case, print the expected overall coolness score of the region. Round the results and print

**exactly**6 decimal places. ('%.6lf' format specifier for double in C)

Sample Input2

3 3

2 10

Sample Output0.330000

0.000000

**Explanation**

For first sample case, the heights are (3, 9, 27) and position scores are (1, 0.99, 0.99*0.99)

However there are only two possible configurations out of 6 where there exists a cool building.

Coolness of (3, 27, 9) = 0.99 (there is a cool building at position 2)

Coolness of (9, 27, 3) = 0.99

Expected coolness = 0.99*1/6 + 0.99*1/6 = 0.33

hide comments

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
2015-02-25 04:52:14
Amazing problem, there are many ways/approach to solve this problem, and one of them is very funny math, just like my AVMG1 ;-) |

Added by: | VV |

Date: | 2015-01-28 |

Time limit: | 0.5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 JS-MONKEY |

Resource: | Own problem (CQM 7, BIT Mesra) |