2009年ACM程序设计竞赛试题

计算机学院

第三届大学生程序设计竞赛试题

《数据测试》

1. Matrix

Y ou are given N*M matrix A. Y ou are to find such matrix B, that B[i,j]=min{ A[x,y] : (y>=j) and (x>=i+j-y) }

Input

On the first line of the input there are two integer numbers, N and M (1<=N,M<=1000). Then matrix A follows: next N lines contains M integers each (not greater than 32000 by absolute value). The j-th number on then i-th of this lines is A[i,j].

Output

Write matrix B in the same format as matrix A, but without N and M.

Sample test(s)

Input

3 3 2 3

1 2 3 3 6 5

4 5 6 1 8 9

7 8 9

Output

1 2 3 3 5 5

2 3 6 1 5 9

3 6 9

2. RGB (English)

There are N segments on a plane (0

Input

The first line contains natural number N. Each of the following N lines contains coordinates of the ends of the segments (4 integer delimited by a space) and the letter (R, G, B), determining the color of a segment.

Output

The first line must contain letter R and number SR delimited by a space. The second line must contain letter G and number SG. The third line must contain letter B and number SB. All numbers should be printed with precision 0.01.

Sample test(s)

Input

4 3

1 1 3

2 R 1 2 2 1 R

2 1 4 2 G 2

3

4 3 B

3 1 5 2 B 3 1 6 3 G 2 2 3 5 R 2. RGB(中文)

一个平面上有N条线段(0

输入说明：

第一行为一个自然数N.接下来的N行中的每一行包含线段两个端点的坐标(4个整数,以空格为间隔)和一个字母(R, G, B),从而决定线段的颜色.

输出说明：

第一行必须包括字母R和数字SB,并用空格间隔.第二行必须包括字G和数字SG,并用空格间隔.第三行必须包括字母B和数字SB,并用空格间隔.所有的数字都应该被打印输出,并精确到0.01.

Output

R 1 R 1

G 1 G 3

B 2 B 1

3.剪断的项链

由n个珠子（n<=100）个珠子串成的一条项链，珠子有红、蓝、白三种颜色（分别用r,b,w代表三种颜色），各种颜色珠子的安排顺序由输入数据任意确定。假定从项链的某处剪断，把项链摆成一条直线，从一端收集和第一颗珠子同种颜色的珠子（直到遇到另一种颜色的珠子停止）。然后再从另一端重复上述过程（注意，这一端的第一颗珠子颜色不一定和另一端第一颗颜色相同）。白色既可以看做是红色，也可以作为蓝色，计入总数目中。

请选择项链剪断的位置，使得两端各自颜色相同珠子的数目之和最大。

输入说明（Input）：

输入n个珠子（10<=n<=100）,每个珠子用r/b/w表示。数据中必须包含r和b两种颜色。

输出说明（Output）：

对于每个测试实例，要求输出两端颜色珠子最大数目的总和，以及断点处前后两颗珠子的序号。输出格式为:“总和， between断点前一颗珠子序号and断点后一颗珠子序号”。每个测试实例的输出占一行。

输入示例（Sample Input）：

brbrrrbbbrrrrrbbrbbbbrrrrb

bbwbrrrwbrbrrrrrb

输出示例（Sample Output）：

8，between 9 and 10

10, between 16 and 17