2008珠海acm市赛.rar

Zhuhai Contest

Zhuhai, China, April 20, 2008

Problem A. Counting in English

Input file: standard input

Output file: standard output

Time limit: 2 seconds

Memory limit: 64 megabytes

Given two positive integers a and b, count from a to b, in English.

Input

standard input standard output

3

one four

five nine

ten ten

one two three four

five six seven eight nine

ten

Page 1 of 8

Zhuhai Contest

Zhuhai, China, April 20, 2008

Problem B. A Small Shop

Input file: standard input

Output file: standard output

Time limit: 2 seconds

Memory limit: 64 megabytes

You own a small shop with only one checkout. You don’t want to anger your customers, so you hope to

minimize the sum of all customer waiting times, where a customer is considered to be waiting when in

the queue, but not when being served at the checkout. In your shop:

• A waiting customer or even a newly arriving customer can be directed to the checkout regardless

Input

The first line contains t (1 ≤ t ≤ 25), the number of test cases followed. Each test case begins with one in-

teger n(1 ≤ n ≤ 400). Each of the following n lines contains two integers a, b(0 ≤ a ≤ 3000, 1 ≤ b ≤ 600),

the arrival time and time needed be served.

Output

For each test case, print the minimal total waiting time.

Sample input and output

standard input standard output

3

4

100 100

100 200

100 200

3

100 500

100 100

200 100

200

700

Page 2 of 8

Zhuhai Contest

Zhuhai, China, April 20, 2008

Problem C. String Statistics

Input file: standard input

Output file: standard output

Time limit: 5 seconds

Memory limit: 64 megabytes

You have an n × n matrix of lower-case letters. You start from somewhere in the matrix, walk in one

of the eight directions (left, right, up, down, up-left, up-right, down-left, down-right) and concatenate

every letter you meet, in the order you see them, to form a string. You can stop anywhere (possibly not

moving at all!), but you cannot go out of the matrix, or change direction in the middle of the journey.

How many different non-empty strings can you get?

Input

standard input standard output

2

2

aa

bb

3

aba

bcc

daa

6

31

Page 3 of 8