# Category Archives: pku

## 滑雪

Time Limit: 1000MS Memory Limit: 65536K

### Description

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

``` 1 2 3 4 5   16 17 18 19 6   15 24 25 20 7   14 23 22 21 8   13 12 11 10 9```

### Sample Input

```5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9```

`25`

### Source

`SHTSC 2002`

......

## Sliding Window

Time Limit: 12000MS Memory Limit: 65536K
Case Time Limit: 5000MS

### Description

An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position Minimum value Maximum value
[1  3  -1] -3  5  3  6  7  -1 3
1 [3  -1  -3] 5  3  6  7  -3 3
1  3 [-1  -3  5] 3  6  7  -3 5
1  3  -1 [-3  5  3] 6  7  -3 5
1  3  -1  -3 [5  3  6] 7  3 6
1  3  -1  -3  5 [3  6  7] 3 7

Your task is to determine the maximum and minimum values in the sliding window at each position.

### Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

### Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

## Largest Rectangle in a Histogram

Time Limit: 1000MS Memory Limit: 65536K

### Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

### Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,...,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

### Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

## PKU 3006 解题报告

### Description

If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, ..., contains infinitely many prime numbers. This fact is known as Dirichlet's Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837.

For example, the arithmetic sequence beginning with 2 and increasing by 3, i.e.,

`2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, ...,`

contains infinitely many prime numbers

`2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, ... .`

Your mission, should you decide to accept it, is to write a program to find the nth prime number in this arithmetic sequence for given positive integers a, d, and n.

### Input

The input is a sequence of datasets. A dataset is a line containing three positive integers a, d, and n separated by a space. a and d are relatively prime. You may assume a <= 9307, d <= 346, and n <= 210.

The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.

### Output

The output should be composed of as many lines as the number of the input datasets. Each line should contain a single integer and should never contain extra characters.

The output integer corresponding to a dataset a, d, n should be the nth prime number among those contained in the arithmetic sequence beginning with a and increasing by d.

FYI, it is known that the result is always less than 106 (one million) under this input condition.