华南理工大学第一届程序设计竞赛比赛试题

华南理工大学首届大学生程序设计竞赛

SCUTCPC

试题

Problem A

IP Address

Problem description

Suppose you are reading byte stream s from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of '1's and '0's (bits) to a dotted decim al format. A dotted decim al format for an IP address is form by grouping 8 bits at a tim e and converting the binary representation to decim al representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decim al numbers rem ember that both are positional numerical system s, where the first 8 positions of the binary system s are:

2726252423222120

128 64 32 16 8 4 2 1

Input

You should read input data from the file of “ipaddress.in”.

The input will have a number N (1<=N<=9) in its first line representing the number of stream s to convert. N lines will follow.

Output

Output your result to the standard output device.

The output must have N lines with a doted decim al IP address. A dotted decim al IP address is formed by grouping 8 bit at the tim e and converting the binary representation to decim al representation.

Sample Input

4

00000000000000000000000000000000 00000011100000001111111111111111 11001011100001001110010110000000 01010000000100000000000000000001

Sample Output

0.0.0.0

3.128.255.255

203.132.229.128

80.16.0.1

Problem B

The Greatest Common Divisor in

Ancient Rome

Problem description

You m ust have retrieved the GCD (Greatest Common Divisor) of two positive integers before. Do you want to have a try, to do that in Ancient Rom e Times?

The Ancient Rom an, who lived hundreds of years ago, used a kind of symbols called “Roman numerals” for arithm etic.The following are 7 basic Rom an num erals:

These 7 sym bols form all the other numbers. All the numbers are written from left to right. Usually, their values equal to the sum of the basic num erals. For example, seventeen can be represented by:

X + V + I + I = XVII

10 + 5 + 1 + 1 = 17

But when the sam e Roman numerals appear continuously m ore than 4 tim es, they must be simplified by using the Subtraction Law. For example, “IX” replaces “VIIII” representing 9, and “CD” represents 400 instead of “CCCC”.

Roman numerals are easy for Additions and Subtractions, but difficult for multiplication and division. That is the reason why Roman numerals are seldom used today.

Now, we will have a try to calculate the GCD of the Rom an Numerals. All the numbers must be in the form of Roman Numerals. And the Subtraction Law is also required.

Input

You should read input data from the file of “roman.in”.

The input file consists of n lines (0 < n < 1000). Each line consists of two Roman Numerals, a and b, separate by a space. (0 < a < 4000, 0 < b < 4000)

Process to End Of File.

Output

Output your result to the standard output device.

Print the GCD in the form of Roman Numerals, in separate lines

Sample Input

XXIV XVI

Sample Input

VIII

Bangla Numbers

Problem description

Bangla numbers normally use 'kuti'(10000000), 'lakh'(100000), 'hajar' (1000), 'shata' (100) while expanding and converting to text. You are going to write a program to convert a given number to text with them.

Input

You should read input data from the file of “bangla.in”.

The input file may contain several test cases. Each case will contain a non-negative number <= 999999999999999.

Output

Output your result to the standard output device.

For each case of input, you have to output a line starting with the case num ber with four digits adjust m ent followed by the converted text.

Sample Input

23764

45897458973958

Sample Output

1. 23 hajar 7 shata 64

2. 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58

Output format example

The Net

Problem description

Taking into account the present interest in the Internet, a sm art information routing becom es a must. This job is done by routers situated in the nodes of the network. Each router has its own list of routers which are visible for him (so called ``routing table"). It is obvious that the inform ation should be directed in the way which minimizes number of routers it has to pass (so called “hop count").

Your task is to find an optim al route (m inimal hop count) for the given network form the source of the inform ation to its destination.

Input

You should read input data from the file of “net.in”.

First line contains number of routers in the network (n). Next n lines contain description of the network. Each line contains router ID, followed by a hyphen and comma separated list of ID s of visible routers. The list is sorted in ascending order. Next line contains a number of routes (m) you should determine. The consecutive m lines contain starting and ending routers for the route separated by a single space. Input data m ay contain descriptions of many networks.

Output

Output your result to the standard output device.

For each network you should output a line with 5 hyp hens and then, for each route, a list of routers passed by information sent from starting to destination routers.

In case passing of information is impossible (no connection exists) you should output a string ``connection im possible". In case of m ultiple routes with the sam e

`hop count' the one with lower ID s should be outputted (in case of route form router 1 to 2 as 1 3 2 and 1 4 2 the 1 3 2 should be outputted).

Assumptions: A number of routers is not greater than 300 and there are at least 2 routers in the network. Each routers ``sees" no more than 50 routers.

Sample Input

6

1-2,3,4

2-1,3

3-1,2,5,6

4-1,5

5-3,4,6

6-3,5

6

1 6

1 5

2 4

2 5

3 6

2 1

10

1-2

2-

3-4

4-8

5-1

6-2

7-3,9

8-10

9-5,6,7

10-8

3

9 10

5 9

9 2

Sample Output

-----

1 3 6

1 3 5

2 1 4

2 3 5

3 6

2 1

-----

9 7 3 4 8 10

connection impossible

9 6 2

Problem E

Delta-wave

Problem description

On the triangular field shown on the picture, sm all

triangles are numbered from1 to ∞(infinity). Traveller

wants to go from triangle M to triangle N. Traveller can

move only through the sides of triangles, not vertices. The

number of sides he crosses is called the path length.

You are to determine the shortest path from M to N.

Input

You should read input data from the file of “wave.in”.

The first line is the number of test cases, followed by a blank line. Each test case of the input contains integers M and N (1<=M,N<=1000000000), separated by som e spaces. Each test case will be separated by a single line.

Output

Output your result to the standard output device.

For each test case, your programm should print the length of the shortest path from M to N. Print a blank line between the outputs for two consecutive test cases.

Sample Input

1

6 12

Sample Output

3

Problem F

Best Sequence

Problem description

The twenty-first century is a biology-technology developing century. One of the most attractive and challenging tasks is on the gene project, especially on gene sorting program. Recently we know that a gene is made of DNA. The nucleotide bases from which DNA is built are A(adenine), C(cytosine), G(guanine), and T(thym ine). Given several segm ents of a gene, you are asked to m ake a shortest sequence from them. The sequence should use all the segm ents, and you cannot flip any of the segm ents.

For example, given 'TCGG', 'GCAG', 'CCGC', 'GATC' and 'ATCG', you can slide the segm ents in the following way and get a sequence of length 11. It is the shortest sequence (but m ay be not the only one).

Input

You should read input data from the file of “best.in”.

The first line is an integer T (1 <= T <= 20), which shows the number of the cases. Then T test cases follow. The first line of every test case contains an integer N (1 <= N <= 10), which represents the number of segments. The following N lines express N segm ents, respectively. Assum ing that the length of any segm ent is between 1 and 20.

Output

Output your result to the standard output device.

For each test case, print a line containing the length of the shortest sequence that can be m ade from these segm ents.

Sample Input

1

5

TCGG

GCAG

CCGC

GATC

ATCG

Sample Output

11

Problem G

Divisibility

Problem description

Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithm etical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions:

17 + 5 + -21 + 15 = 16

17 + 5 + -21 - 15 = -14

17 + 5 - -21 + 15 = 58

17 + 5 - -21 - 15 = 28

17 - 5 + -21 + 15 = 6

17 - 5 + -21 - 15 = -24

17 - 5 - -21 + 15 = 48

17 - 5 - -21 - 15 = 18

We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.

You are to write a program that will determine divisibility of sequence of integers. Input

You shoul d read input data from the file of “divisibility.in”.

The first line of the input file contains a integer M indicating the number of cases to be analyzed. Then M couples of lines follow.

For each one of this couples, the first line contains two integers, N and K

(1 <= N <= 10000, 2 <= K <= 100) separated by a space. The second line

contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.

Output

Output your result to the standard output device.

For each case in the input file, write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.

Sample input

2

4 7

17 5 -21 15

4 5

17 5 -21 15

Sample Output

Divisible

Not divisible

Problem H

How Many Calls?

Problem description

The fibonacci number is defined by the following recurrence:

?fib(0) = 0

?fib(1) = 1

?fib(n) = fib(n-1)+fib(n-2)

But we're not interested in the fibonacci num bers here. We would like to know how many calls does it take to evaluate the n th fibonacci num ber if we follow the given recurrence. Since the num bers are going to be quite large, we'd like to m ake the job a bit easy for you. We'd only need the last digit of the num ber of calls, when this number is represented in base b.

Input

You shoul d read input data from the file of “calls.in”.

Input consists of several test cases. For each test you'd be given two integers n (0 <= n <= 2147483647), b (0 < b <= 10000). Input is terminated by a test case where n=0 and b=0, you must not process this test case.

Output

Output your result to the standard output device.

For each test case, print the test case number first. Then print n, b and the last digit (in base b) of the number of calls. There would be a single space in between the two numbers of a line. Note that the last digit has to be represented in decimal number system.

Sample Input

0 100

1 100

2 100

3 100

10 10

0 0

Sample Output

Case 1: 0 100 1

Case 2: 1 100 1

Case 3: 2 100 3

Case 4: 3 100 5

Case 5: 10 10 7

华南理工大学教授简介

附件2： 华南理工大学教授简介 1、汪晓军 博士，华南理工大学环境与能源学院教授，博士生导师。主要从事废水处理及其相关的生物技术开发研究工作；首创化学氧化与曝气生物滤池技术，在垃圾渗滤液处理及废水深度处理得到广泛工程化应用；目前正开展以亚硝化-厌氧氨氧化为主导的废水新型节能降耗脱氮技术研发及工程应用工作；已发表学术论文超200篇，获国家授权专利超60项，相关成果已广泛应用工程项目中；曾获国家发明展览金奖、广东省环境保护技术二等奖、环保部环境保护技术三等奖。 2、姚顺春 博士，华南理工大学电力学院副教授，硕士生导师，广东省能源高效低污染转化工程技术研究中心副主任，广东特支计划科技创新青年拔尖人才，中国光学工程学会LIBS青年科学家，中国光学工程学会激光诱导击穿光谱（LIBS）专业委员会委员，广东省能源基础与管理标准化技术委员会委员，广东省碳普惠专家委员会委员，广东省发改委钢铁行业淘汰落后产能专家委员会委员。主要从事能源清洁转化与系统优化研究，重点开展燃烧诊断、排放监测及其控制技术研究；主持2项国家自然科学基金、6项省部级项目，承担华电集团、广东电网公司、粤电集团等单位委托项目多项；发表论文60余篇，SCI/EI 收录50余篇；授权发明专利10件、实用新型专利17件；相关成果

获中国南方电网公司科技进步三等奖、广东省科技进步奖三等奖等。 3、马邕文 工学博士，教授，博士生导师。2001年进入广东省“千百十人才工程”，长期致力于工业污染控制及清洁生产新技术的研究，提出了“造纸废水封闭循环技术”及“工业废水处理系统的嵌入式三层网络控制方法”和“造纸废水的物化-生化一体化处理方法”，在国内外发表了一系列的研究论文及获得中国发明专利授权并在全国八十多家造纸厂应用，每天共处理造纸工业废水七十多万吨，每年通过节水、节电、沉渣回用等直接为社会创经济效益2.07亿元。其“二次纤维造纸废水的封闭循环及其污泥回收利用”清洁生产技术及理论目前已被学术界认可并被越来越多的造纸厂采用，在该领域的研究工作已处于全国领先水平。 4、付名利 博士，副教授，硕士研究生导师, 华南理工大学大气环境与污染控制学术团队成员，挥发性有机物污染治理技术与装备国家工程实验室、广东省大气环境与污染控制重点实验室、广东省环境应急与风险防范工程研究中心等科研平台核心骨干。研究方向包括大气环境与污染控制和环境功能材料；有机废气（VOCs）治理与移动源排气净化功能材料、反应机理等。 5、浦跃武 博士，教授，博士生导师。2002年以来，作为项目主持人，已完成技术转让项目13项，现正推广染整污水生化处理、高浓度有机