ACM-ICPC比赛介绍及相关参考

ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest – ACM-ICPC）由国际计算机学界著名的ACM学会（Association for Computer Machinery）主办，是世界上规模最大、水平最高的国际大学生程序竞赛。每年举办一次。ACM成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织。

ACM国际性大学生程序设计竞赛自1970年开始，其宗旨是使大学生能通过计算机充分展示自己分析问题和解决问题的能力。参加本项比赛的选手至少需要掌握计算机科学的常用算法，基本的计算理论，（如：离散数学，具体数学，组合数学基础），数据结构基础，程序设计语言（规定是C/C++或者是Java）。在本项比赛中考察学生的不仅仅是能够完成指定任务的程序，更要求在完成程序的功能的基础之上提高程序的运行效率与空间占用率。我在浙江大学ACM在线测试组参加测试的最深体会就是你时时刻刻都应当去考虑如何去最大限度的优化，改善你的程序结构，已达到用最小的空间，最优的算法实现程序的功能。从数学角度考虑，题目主要的方向集中在工程数学，抽象数学很少涉及。一般题目都会给出要求和几组输入和输出作为程序设计的参考，也是检验程序正确性的标准之一。

整个竞赛分为地区预赛(Regional Contest)和决赛（Final Contest）两个阶段进行。今年（2003）在中国大陆地区举行的ACM-ICPC区赛共有两个赛区，分别由北京清华大学和广州中山大学承办。我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛，取得了较好的成绩，我们学院在明年也要有组织的参加这项国际性的大赛，希望有志于此的同学加入我们的行列。我们会定期的举办相关的讲座以使同学们对ACM-ICPC比赛有更多地了解。鉴于我院学生对这项比赛了解的实际情况，下面我就从浙江大学的在线题库中选择了Volume I当中的第一个题目向大家展示一下这项比赛的特点。

Calculate a + b

Input

The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line.

Output

For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input.

Sample Input

1 5

Sample Output

6

Hint

Use + operator

如果选用的程序设计语言是 C++:

#include

int main()

{

int a,b;

while(cin >> a >> b)

cout << a+b << endl;

}

如果选用的程序设计语言是C:

#include

int main()

{

int a,b;

while(scanf("%d %d",&a, &b) != EOF)

printf("%d\n",a+b);

}

如果选用的程序设计语言是PASCAL

program p1001(Input,Output);

var

a,b:Integer;

begin

while not eof(Input) do

begin

Readln(a,b);

Writeln(a+b);

end;

end.

程序的功能中文描述是这样的：在一行输入两个整型数，换行输出结果，循环执行，直到用户中止。

三个程序代码都摆出来了，虽然这个程序极其简单，但是可以说明很多语言的特点以及程序设计的思想，大家可以清楚地看到与一般的思路最大不同点就是没有使用循环语句for,而是选择while,结合程序设计语言自身的特点，从而大大的减少了代码量，而且不易出错。下面我把这个程序关键点的原理阐述一下：

针对题目的要求，要保证无数次输入下程序的健壮性，而while语句这点的优势就是及其突出的，此种情况下，我们通常采用在while循环结构的首部使用流读取运算符输入一系列值。当遇到文件结束符或者是非法输入时运算符返回0（false）这种结构非常适合事先并不知道有多少组输入时，那么下面我们在着重说一下cin在这里的用法.

上面的C++算法描述中，程序的跳出我们采用输入非法字符，一旦输入非法字符，则返回值为0（false）则，while循环结束，也就是输入输出流当中初学者不太常使用的流错误。

下面我们做一个简单的介绍：

对于输入输出流的状态，我们可以用类ios中的位测试流的状态。类ios是输入/输出类istream,ostream和iostream的基类。当遇到文件结束符时，输入流中自动设置eofbit.可以在程序中使用成员函数eof确定是否已经到达文件尾。如果cin遇到了文件的结束符，那么函数调用：

cin.eof()

返回true,否则返回false

当流中发生格式错误的时候，虽然会设置failbit,但是字符并未丢失。成员函数fail判断流操作是否失败，这种错误通常可恢复。

当发生导致数据丢失的错误时，设置badbit.成员函数bad判断流操作是否失败，这种严重错误通常不可恢复。

如果eofbit,failbit,badbit都没有设置，则设置goodbit

如果函数eo,fail,bad都没有设置，则成员函数good返回true.成员函数中应当只对合法流进行I/O操作。

下面是为说明问题专门写的一个测试代码，

#include

int main()

{

int a;

cin << a;

cout >>cin.eof();

cout >>cin.fail();

cout >>cin.bad();

cout >>cin.good();

}

大家可以试一试，分别输入合法的整型数和非法的字符型数，比较结果就能够比较好的领会这部分内容了。另外两种语言的原理很容易看懂，就不傲述了，总之就想通过这个问题说明：问题看似简单，实则包含着很多内容，再简单的程序我们都要结合语言的自身特点，以一种最优化的结构去表达他， 不要忽视任何的小问题。