ACM-ICPC及算法示例说明

竞赛规则


ACM-ICPC是团队形式的比赛,每队由至多3名队员组成。队员必须是来自本校研一及以下的学生,同时需要注意每位选手最多可以参加2次全球总决赛和5次区域赛,每个赛季最多参加2次区域赛

比赛期间,每队使用1台电脑,需要在5个小时内使用C、C++或Java中的一种,编写程序解决7到13个问题,题目均为英文题面。近年来,随着选手水平的提高,区域赛题目数量有增多的趋势。


题目规格

以一道例题来讲解常规的ACM赛题组成部分:

A + B Problem 题目标题
Time Limit: 2000/1000 MS (Java/Others) 运行时间限制
Memory Limit: 65536/32768 K (Java/Others) 内存空间限制
Problem Description 问题描述
Calculate A + B.
Input 输入格式
Each line will contain two integers A and B. Process to end of file.
Output 输出格式
For each case, output A + B in one line.
Sample Input 测试样例
1 1
Sample Output
2

需要注意的是:

  • 只有当你的程序能在规定的运行时间内,申请使用的内存空间不超过限制,并且按照正确的输入输出格式正确通过所有的测试数据,你的程序才会被认为正确通过
  • 通常C/C++与Java会有不同的时间空间限制。在正规的比赛中,有时并不会给出明确的时间空间限制数值。
  • 其中样例仅仅是为了明确题意与格式给出的一个例子,并不是全部的测试数据,也即是说即便你的程序能够成功通过样例,也不一定能通过所有的测试数据。

选手在程序完成之后提交裁判运行,运行的结果会判定为正确或错误两种并及时通知参赛队。当你向裁判提交你的程序时,通常有以下几种返回结果:


程序正确(Yes):

  • Accepted. —通过!(AC)

程序错误(No):

  • Wrong Answer. —答案错误。(WA)
  • Runtime Error. —程序运行出错,意外终止等。(RE)
  • Time Limit Exceeded. —超时。程序没在规定时间内得到答案。(TLE)
  • Presentation Error. —格式错。程序没按规定的格式输出答案。(PE)
  • Memory Limit Exceeded. —超内存。程序使用的内存空间超限。(MLE)
  • Compile Error. —编译错。程序编译不通过。(CE)

评判标准

当裁判认定某只队伍在正确通过一题后,组织者将在其位置上升起一只代表该题颜色的气球。有些赛区会准备一些特殊的“FIRST PROBLEM SOLVED”(俗称FB,First Blood)气球,奖励给每道题目第一个通过它的队伍。

比赛的排名依据每个队伍通过的题目数量,对于通过题数相同的队伍,将比较他们的总用时
每道试题的用时指的是从竞赛开始到试题解答被判定为正确为止所用的时间,但需要额外注意的是,其间每一次提交运行结果被判错误的话,将被增加20分钟的罚时。每队的总用时为该参赛队所有正确解答的试题用时之和,未正确解答的试题罚时不会被计入总用时

例如:A、B两队都正确完成两道题目,其中A队提交这两题的时间分别是比赛开始后 1:00 和 2:45 ,B队为 1:20 和 2:00 ,但B队有一题提交了2次。这样A队的总用时为 1:00 + 2:45 = 3:45 而B队为 1:20 + 2:00 + 0:20 (罚时) = 3:40 ,所以B队以总用时少而获胜。
再次强调,未通过的题目不会被算入罚时

比赛的前四个小时,选手可以通过榜单看到实时排名。最后一小时封榜,无法看到排名变化,但现场选手仍可以通过气球数了解赛场上的大体情况,最终榜单在比赛结束后才会公布。

ACM比赛重点考察选手的算法和程序设计能力,因而不会涉及实际工程中常用的系统编程,多线程编程等内容。特别需要注意的是,选手可携带任何非电子类资料,包括书籍和打印出来的程序等。通常ACM选手会预先准备好某些可能会用到的代码打印下来带入赛场,俗称模板。

就获奖情况而言,一般的区域赛会分别按10%,20%,30%的比例颁发金,银,铜奖,即一般情况(120队伍)有12支队伍获金牌,24支队伍获银牌,36支队伍获铜牌,其余为优胜奖。同时对于所有达成“FIRST PROBLEM SOLVED”成就的队伍,会颁发特别的FB奖。为了鼓励女选手参赛,有的赛区特别设立了最佳女队奖,颁发给成绩最佳的女队(三名选手均为女性)。