Round B的成绩主要失利在多次提交，罚时太重肯定拉了我很多名次。 # Bick Tour

## 原题

### Problem

Li has planned a bike tour through the mountains of Switzerland. His tour consists of N checkpoints, numbered from 1 to N in the order he will visit them. The i-th checkpoint has a height of Hi.

A checkpoint is a peak if:

• It is not the 1st checkpoint or the N-th checkpoint, and
• The height of the checkpoint is strictly greater than the checkpoint immediately before it and the checkpoint immediately after it.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The i-th integer is Hi.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of peaks in Li’s bike tour.

### Limits

Time limit: 10 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Hi ≤ 100.

3 ≤ N ≤ 5.

3 ≤ N ≤ 100.

### Sample

Input

4
3
10 20 14
4
7 7 7 7
5
10 90 20 90 10
3
10 3 10

Output

Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 0

• In sample case #1, the 2nd checkpoint is a peak.
• In sample case #2, there are no peaks.
• In sample case #3, the 2nd and 4th checkpoint are peaks.
• In sample case #4, there are no peaks.

## 题目大意

N个检查点，如果一个检查点不是第一个也不是最后一个，而且它比前后检查点高度都要高，那么这就是一个山峰。问有几个山峰？

# Bus Route

## 原题

### Problem

Bucket is planning to make a very long journey across the countryside by bus. Her journey consists of N bus routes, numbered from 1 to N in the order she must take them. The buses themselves are very fast, but do not run often. The i-th bus route only runs every Xi days.

More specifically, she can only take the i-th bus on day Xi, 2Xi, 3Xi and so on. Since the buses are very fast, she can take multiple buses on the same day.

Bucket must finish her journey by day D, but she would like to start the journey as late as possible. What is the latest day she could take the first bus, and still finish her journey by day D?

It is guaranteed that it is possible for Bucket to finish her journey by day D.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and D. Then, another line follows containing N integers, the i-th one is Xi.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the latest day she could take the first bus, and still finish her journey by day D.

### Limits

Time limit: 10 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ XiD.
1 ≤ N ≤ 1000.
It is guaranteed that it is possible for Bucket to finish her journey by day D.

1 ≤ D ≤ 100.

1 ≤ D ≤ 1012.

### Sample

Input

3
3 10
3 7 2
4 100
11 10 5 50
1 1
1

Output

Case #1: 6
Case #2: 99
Case #3: 1

In Sample Case #1, there are N = 3 bus routes and Bucket must arrive by day D = 10. She could:

• Take the 1st bus on day 6 (X1 = 3),
• Take the 2nd bus on day 7 (X2 = 7) and
• Take the 3rd bus on day 8 (X3 = 2).

In Sample Case #2, there are N = 4 bus routes and Bucket must arrive by day D = 100. She could:

• Take the 1st bus on day 99 (X1 = 11),
• Take the 2nd bus on day 100 (X2 = 10),
• Take the 3rd bus on day 100 (X3 = 5) and
• Take the 4th bus on day 100 (X4 = 50),

In Sample Case #3, there is N = 1 bus route and Bucket must arrive by day D = 1. She could:

• Take the 1st bus on day 1 (X1 = 1).

# Robot Path Decoding

## 原题

### Problem

Your country’s space agency has just landed a rover on a new planet, which can be thought of as a grid of squares containing $10^9$ columns (numbered starting from 1 from west to east) and $10^9$ rows (numbered starting from 1 from north to south). Let (w, h) denote the square in the w-th column and the h-th row. The rover begins on the square (1, 1).

The rover can be maneuvered around on the surface of the planet by sending it a program, which is a string of characters representing movements in the four cardinal directions. The robot executes each character of the string in order:

• N: Move one unit north.
• S: Move one unit south.
• E: Move one unit east.
• W: Move one unit west.

There is also a special instruction , whereXis a number between 2 and 9 inclusive andYis a non-empty subprogram. This denotes that the robot should repeat the subprogramYa total ofXtimes. For example:

Since the planet is a torus, the first and last columns are adjacent, so moving east from column $10^9$ will move the rover to column 1 and moving south from row $10^9$ will move the rover to row 1. Similarly, moving west from column 1 will move the rover to column $10^9$ and moving north from row 1 will move the rover to row $10^9$ . Given a program that the robot will execute, determine the final position of the robot after it has finished all its movements.

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains a single string: the program sent to the rover.

### Output

For each test case, output one line containing Case #x: w h, where x is the test case number (starting from 1) and w h is the final square (w, h) the rover finishes in.

### Limits

Time limit: 10 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
The string represents a valid program.
The length of each program is between 1 and 2000 characters inclusive.

#### Test set 1

The total number of moves the robot will make in a single test case is at most $10^4$ .

### Sample

Input

4
SSSEEE
N
N3(S)N2(E)N
2(3(NW)2(W2(EE)W))

Output

Case #1: 4 4
Case #2: 1 1000000000
Case #3: 3 1
Case #4: 3 999999995

In Sample Case #1, the rover moves three units south, then three units east.

In Sample Case #2, the rover moves one unit north. Since the planet is a torus, this moves it into row $10^9$ .

In Sample Case #3, the program given to the rover is equivalent to NSSSNEEN.

In Sample Case #4, the program given to the rover is equivalent to NWNWNWWEEEEWWEEEEWNWNWNWWEEEEWWEEEEW.

## 分析

Note：这题注意要及时对$10^9$取模，不然很可能会数值溢出。

# Wandering Robot

## 原题

### Problem

Jemma is competing in a robotics competition. The challenge for today is to build a robot that can navigate around a hole in the arena.

The arena is a grid of squares containing W columns (numbered 1 to W from left to right) and H rows (numbered 1 to H from top to bottom). The square in the x-th column and y-th row is denoted (x, y). The robot begins in the top left square (1,1) and must navigate to the bottom right square (W, H).

A rectangular subgrid of squares has been cut out of the grid. More specifically, all the squares that are in the rectangle with top-left square (L, U) and bottom-right square (R, D) have been removed.

Jemma did not have much time to program her robot, so it follows a very simple algorithm:

• If the robot is in the rightmost column, it will always move to the square directly below it. Otherwise,
• If the robot is in the bottommost row, it will always move to the square directly right of it. Otherwise,
• The robot will randomly choose to either move to the square directly to the right, or to the square directly below it with equal probability.

Jemma passes the challenge if her robot avoids falling into the hole and makes it to the square (W, H). What is the probability she passes the challenge?

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing W, H, L, U, R and D.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a real number between 0 and 1 inclusive, the probability that Jemma passes the challenge.

y will be considered correct if it is within an absolute or relative error of $10^{-5}$ of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

### Limits

Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ UDH.
1 ≤ LRW.
Neither the top-left nor bottom-right squares will be missing.

1 ≤ W ≤ 300.
1 ≤ H ≤ 300.

#### Test set 2

1 ≤ W ≤ $10^5$.
1 ≤ H ≤ $10^5$.

Input

4
3 3 2 2 2 2
5 3 1 2 4 2
1 10 1 3 1 5
6 4 1 3 3 4

Output

Case #1: 0.5
Case #2: 0.0625
Case #3: 0.0
Case #4: 0.3125

## 官方解答

### Test Set 1

We can solve this test set using dynamic programming. Let f(x, y) be the probability Jemma passes the challenge if she is currently in the square (x, y). The base case of this function is f(W, H) = 1. Also, if the square (x, y) has been removed, then f(x, y) = 0.

If there is only one possible square to go to from square (x, y) (i.e. either x = W or y = H), then f(x, y) = f(x’, y’), where (x’, y’) is the possible next square. Otherwise, let (x1’, y1’) and (x2’, y2’) be the possible next squares. Since they have the same probability to become the next square, f(x, y) = 0.5 × f(x1’, y1’) + 0.5 × f(x2’, y2’).

The running time and space of this solution is O(W × H).

### Test Set 2

The first observation to solve this problem is to realize that there are two ways to avoid the hole: either going to the left and the bottom of the hole (illustrated by the red path in the figure below), or going to the top and the right of the hole (illustrated by the blue path in the figure below). It can be seen that the set of paths in the red path and the blue path are disjoint–there is no path that goes both to the left of the hole and to the top of the hole simultaneously. Therefore, we can compute the probability that Jemma passes the challenge by taking the red path and the blue path separately and compute the sum of both probabilities.

Since the probability of passing the challenge by taking the blue path can be computed similarly, we only focus on computing the probability of passing the challenge by taking the red path for the rest of the discussion. The next observation to solve this problem is that we can choose a set of squares diagonally from the bottom-left corner of the hole (illustrated by the green squares below) such that Jemma has to pass exactly one of the squares to pass the challenge by taking the red path. Also, by landing on one of the squares, it is no longer possible that Jemma will fall to the hole, thus passing the challenge by taking the red path is now guaranteed. Therefore, computing the probability of passing the challenge by taking the red path is equivalent to computing the probability that Jemma will land on one of the green squares. Similar to the red and blue paths discussion, since Jemma cannot pass two green squares simultaneously, we can compute the probability that Jemma lands on each square separately and compute the sum of all probabilities.

Let us take square X for an example. Consider all paths that go to the square X. For each move in the path, there is a 0.5 probability that the move will follow the path. Since the number of moves to square X is (L + D - 2), there is a $(0.5)^{(L + D - 2)}$ probability that this path will be taken. This number has to be multiplied with the number of paths to go to square X, which can be computed using a single binomial coefficient. The probability of reaching any particular green square is the same for all but the green square in the last row, which is left to the reader as an exercise.

To handle floating point issues, we can store every huge number in their log representation (i.e. storing $log_2(x)$ instead of x). We can then compute the value of $C(n, k) / 2^n$ using $2^{log_2(n! / (k! × (n - k)!) / 2^n)} = 2^{log_2(n!) - log_2(k!) - log_2((n - k)!) - n}$, which takes constant time to compute if we have precomputed every value of $log_2(x!)$. Since there can be at most O(N) green squares, where N is the larger length of the grid (i.e. N = max(H, W)), the total running time of this solution is O(N).

### 题解大意   $$P(Z) = 0.5 \times P(A) + P(Z’)$$

$$P(Z’) = 0.5 \times P(B) + P(Z’’)$$

$$P(Z’’) = 0.5 \times P(Y)$$

## AC代码

======================

====================== (>来评分吧<)