第1章 ACM程序设计入门

1.1 ACM/ICPC简介

ACM国际大学生程序设计大赛（ACM International Collegiate Programming Contest, ACM/ICPC）是由世界计算机权威组织——ACM（Association for Computing Machinery，美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，素来被冠以“程序设计的奥林匹克”的尊称。

1.1.1 历史

竞赛的历史可以上溯到1970年，当时在美国得克萨斯A&M大学举办了首届比赛。当时的主办方是the Alpha Chapter of the UPE Computer Science Honor Society。作为一种全新的发现和培养计算机科学顶尖学生的方式，竞赛很快得到美国和加拿大各大学的积极响应。1977年，在ACM计算机科学会议期间举办了首次总决赛，并演变成为目前的一年一届的多国参与的国际性比赛。

最初几届比赛的参赛队伍主要来自美国和加拿大，后来逐渐发展成为一项世界范围内的竞赛。特别是自1997年IBM开始赞助赛事之后，赛事规模增长迅速。1997年，总共有来自560所大学的840支队伍参加比赛。而到了2004年，这一数字迅速增加到840所大学的4109支队伍并以每年10%～20%的速度在增长。

1980年，ACM将竞赛的总部设在位于美国得克萨斯州的贝勒大学。

在赛事的早期，冠军多为美国和加拿大的大学获得。而进入20世纪90年代后期以来，俄罗斯和其他一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代表队则在2002年美国夏威夷第26届和2005年上海举行的第29届全球总决赛上两次夺得冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。赛事的竞争格局已经由最初的北美大学的一枝独秀演变成目前的亚欧对抗的局面。

1.1.2 简要规则

ACM/ICPC以团队的形式代表各学校参赛，每队由3名队员组成。每位队员必须是入校5年内的在校大学生，最多可以参加2次全球总决赛和4次区域选拔赛。比赛期间，每队使用1台电脑，在5个小时内使用C、C++、Pascal或Java中的一种语言编写程序解决8或10个问题（区域选拔赛通常是8题，全球总决赛是10题）。程序完成之后提交给在线评测（Online Judge, OJ）系统去运行，运行的结果会判定为正确或错误并及时通知参赛队。每队在正确完成一题后，组织者将在其位置上升起一只代表该题颜色的气球。

最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次提交运行结果被判错误的话将被加罚20分钟时间，未正确解答的试题不记时。例如：A、B两队都正确完成两道题目，其中A队提交这两题的时间分别是比赛开始后1h和2h45min, B队为1h20min和2h，但B队有一题提交了两次（其中一次是错误的提交）。这样A队的总用时为3h45min，而B队为3h40min，所以B队以总用时少而获胜。

1.1.3 区域和全球决赛

与其他计算机程序竞赛（例如国际信息学奥林匹克，IOI）相比，ACM/ICPC的特点在于其题量大，每队需要5小时内完成8道题目，甚至更多。另外一支队伍3名队员却只有1台电脑，使得时间显得更为紧张。因此除了扎实的专业水平外，良好的团队协作和心理素质同样是获胜的关键。

赛事由各大洲区域预赛和全球总决赛两个阶段组成。各预赛区第一名自动获得参加全球总决赛的资格。决赛安排在每年的3～4月举行，而区域预赛一般安排在上一年的9～12月举行。一个大学可以有多支队伍参加区域预赛，但只能有一支队伍参加全球总决赛。

全球总决赛第一名将获得奖杯一座。另外，成绩靠前的参赛队伍也将获得金、银和铜牌。而解题数在中等以下的队伍会得到确认但不会进行排名。

1.1.4 历届冠军

下表列出了自1977年以来，截至2005年历年全球总决赛的冠军。

1.1.5 源程序在线评测系统（Online Judge）

源程序在线评测（Online Judge, OJ）系统上有大量的试题，只需在OJ系统上免费注册一个账号即可做题。

竞赛试题涵盖的范围很广，大致划分如下：Direct（简单题）, Computational Geometry（计算几何）, Number Theory（数论）, Combinatorics（组合数学）, Search Techniques（搜索技术）, Dynamic Programming（动态规划）, Graph Theory（图论）, Other（其他）。

比较著名的OJ系统有：

RealOJ:http://www.realoj.com，中文题目较多，题目增加速度很快，特别适合初学者。

浙江大学ZOJ:http://acm.zju.edu.cn/，是国内最早的OJ，题目数量众多且质量较高。

俄罗斯乌拉尔大学的ACM网站：http://acm.timus.ru，是一个老牌的OJ，题目不多，但比较经典。

ICPC官方网站：http://cm.baylor.edu/welcome.icpc，上面会公布每年世界总决赛的排名及试题。

1.1.6 试题样例

题目名称：A + B Problem

链接地址：http://www. realoj.com /网上第1题

Time Limit: 1000 ms Resident Memory Limit: 1024 KB Output Limit: 1024 B

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