历届程序设计acm试题

搜集的南开大学的ACM试题与你共享

[A] 南开大学Onlinejudge 在线判题系统 http://acm.nankai.edu.cn

A. Lucy的新难题

时间限制：2秒 内存限制：32000KB

不知不觉，南开大学第三届“我为程序狂”又要拉开帷幕了。这天，Lucy也来到南开大学ACM协会，与大家共同欢庆NKPC的三周岁的日子。

谈笑间，ACM协会的主席拿了圆形的生日蛋糕。大伙开心地唱完了生日歌，一起吹灭了蜡烛。

要分蛋糕了，大家都很兴奋。本着公平的原则，每位到场的人员都要在蛋糕上切一刀。ACM协会的主席事先知道有n位朋友会参与这个欢庆宴会。为了方便大家切蛋糕，主席在订蛋糕的时候就嘱咐在蛋糕的边缘布置上2n朵小花。

每个人切蛋糕都会从蛋糕的边缘的一朵小花笔直地切到蛋糕的另一端的小花，来表达自己对NKPC的祝福。为了尊重其他同学，每个人在切蛋糕一定不会和蛋糕上已有的切痕相交，也不会从别人已切过的小花作为切蛋糕的起点或终点。同时，每位同学在切蛋糕的时候，都要保证后面所有的同学都能够按照上述的规则切蛋糕。这样，蛋糕上就留下n条切痕。

Lucy眨巴眨巴眼睛，问，要是不考虑切蛋糕的先后顺序和谁切的哪一刀，这蛋糕切完了共有多少种切法呢？ 大家听了呵呵一笑，说，那就把这个问题留给NKPC3，作为《Lucy的新难题》吧。 相信聪明的你，一定能够帮Lucy解答她的难题的，对吗？ 输入 （请使用标准输入输出，而不要读写文件） 输入包括多组测试数据，你应当处理到输入结束为止。

每组输入数据中，都只有一行，仅包含一个正整数n，且0

1

样例输入 1 2 样例输出 Case 1: 1 Case 2: 2 2

[B] 南开大学Onlinejudge 在线判题系统 http://acm.nankai.edu.cn

B. 保龄球

时间限制：2秒 内存限制：32000KB

南开大学ACM协会的一个元老毕业后，开了家保龄球馆。他需要为他的保龄球馆的计算机写一个记分的程序。 一局(GAME)保龄球分为10格,每格里有两次投球机会,如在第一次投球时没能全中,就有需要投第二球。 每一格可能出现三种情况： 1.失球(MISS)

无论何种情况,在一格的两次投球时,未能击倒10个瓶,此格的分数为击倒的瓶数。如果一次击球中未击倒一个瓶，则用一个’-’标记。

2.补中(SPARE)

要一次击倒十个瓶子并非那么容易的！如果在第一次掷球后，你还有一次机会来击倒该格第一球所留下的情致。当第二次投球击倒该格第一球余下的全部瓶子,称为补中,用一个‘/’符号表示。补中的记分是10分加上下一次投球击倒的瓶数。

3.全中(STRIKE)

当每一格的第一次投球击倒全部竖立的十个瓶时,称为全中,用一个(×)符号表示。全中的记分是10分(击倒的瓶)加该球员下两次投球击倒的瓶数。

但在第十格中情况比较特殊：

(1)如第二次投球未补中,则第十格得分为第九格得分加上第十格所击倒瓶数。

(2)如第二次投球补中,则追加一次投球机会,第十格得分为第九格得他加上10加上追加一次投球击倒瓶数。

(3)如第一球为全中,则追上加二次投球机会,第十格得分为第九格得分加上10加追加二次投球击倒的瓶数。因此从第一格到第十格的两次追加投球,都为全中,则为12个全中，得分为满分300分。

输入 （请使用标准输入输出，而不要读写文件） 输入包括多组测试数据，你应当处理到输入结束为止。 每组输入数据中，都只有一行，包含一局的记分符号，相邻的两个符号之间以一个空格隔开。记分的符号仅包括?-?（不含引号）、?/?（不含引号）、?X?（不含引号）及阿拉伯数字1到9。 输出 （请使用标准输入输出，而不要读写文件） 对于每组输入数据，输出两行。对于第i组输入数据，输出的第一行为”Case i:”，输出的第二行为10个整数，表示每格的累计得分。相邻的两个得分以一个空格隔开。

3

样例输入 X X X X X 5 / 7 1 - - X X X X 4 4 3 3 2 2 1 7 7 1 2 - 9 / 2 2 6 3 2 / 1 样例输出 Case 1: 30 60 90 115 135 152 160 160 190 220 Case 2: 8 14 18 26 34 36 48 52 61 72 4

[C] 南开大学Onlinejudge 在线判题系统 http://acm.nankai.edu.cn

C. 计算机硬件评分系统

时间限制：2秒 内存限制：32000KB

小C听说微软新推出的一款操作系统Windows Vista可以对电脑的配置进行评分，很感兴趣。由于小C对硬件软件方面都很了解，就通过一系列的市场调查与实践，制作了一款自己的计算机硬件评分系统。此系统可以对CPU、内存、硬盘、主板、显卡五部分分别进行评分，分数为不超过100的正整数，并以这五个分数中的最低分作为对计算机的总体评分。

同寝室的小D打算最近购置一台新电脑，他请小C给他当参谋，小C就提供了一些当前的CPU、内存、硬盘、主板、显卡五种硬件的品牌、价格以及每个硬件由他所制作的系统所评价出来的分数。小D准备至多用N元来购买这五种硬件并且他还希望能够得到一台电脑有尽量高的总体评分。

作为寝室长的你主动要写一个程序来帮助小D购买电脑。

输入 （请使用标准输入输出，而不要读写文件）

第一行是一个正整数，不大于50000，表示上述的N。

之后共有五部分的数据，分别代表CPU、内存、硬盘、主板、显卡部分的资料描述。每一部分的第一行均为一个正整数，表示资料中所提供的这种硬件品种数目M。下面M行每一行都描述了一个品种的情况，包括两个整数，以空格隔开。第一个整数介于1于10000，表示该品种的价格，第二个正整数表示该硬件所得到的分数。假定所列出的硬件相互都是兼容的。 输出 （请使用标准输入输出，而不要读写文件） 输出两行，每行一个正整数。第一行表示所购电脑的总体评分最大值。第二行表示要购买上述总体评分的电脑所需最少花费。

如果小D的钱不足以购置这些硬件，则输出的两个数字均为0 样例输入 样例输出 3000 4 880 80 400 60 495 72 240 55 3 635 78 345 59 785 86 2 800 88 603 71 2 499 72 71 2820 5

590 79 3 588 76 999 84 289 51 6

[D] 南开大学Onlinejudge 在线判题系统 http://acm.nankai.edu.cn

D. 朋友们的距离

时间限制：2秒 内存限制：32000KB

要放假了，考完了所有试就等着上火车回家的 Butterfly0923 面对着自己心爱的计算机，无聊的逛着我爱南开 BBS，眼看着在线好友列表的长度一天天减少。“来自”一栏中的 IP 都还是校内的，大多以 10 开头。Butterfly0923 看到大部分人跟自己同在 21 宿，还有 15 宿的老乡、13 宿的狐朋狗友们、西区的研究生、12 宿的音乐狂人和 8 宿的可爱小女生。虽然现在大家仅仅相隔几百米，但是很快彼此将远隔万水千山，分散在祖国各地。如果那时大家一起上线，各地 IP 大展览，一定有趣，Butterfly0923 这样想。不过祖国这么大，不知道大家到底相距多远。于是 Butterfly0923 给所有在线的 ID寄语信鸽，询问他／她的家乡与学校之间的距离，他想知道自己的朋友中谁离学校最远。

Butterfly0923 知道自己的家距学校 520km，seaeagle 也知道，所以他回信说：我家离学校的距离比你的四倍还多 200km。不过 doraemonok 不知道，他比较务实，直接回信说：12km，公交 1hour。迷糊的 Butterfly0923 想了想，觉得 seaeagle 比较远一点。但是随着问的人越来越多，问题变得复杂起来。unusualwater 说：我的距离是你的十三分之一。aliao 说：我刚问过 gnr，你们的旅途合在一起比我少 194km。而 gnr 老师的回信说：我的路程正好是你的两倍。这回，Butterfly0923 算了好大一会，才知道 aliao 最远。

Butterfly0923 最后寄语信鸽了爱好编程的你，不过不是问距离，他告诉你他从各个 ID 得到的信息，希望你能告诉他最远的地方有多少公里，是谁在那里。

输入 （请使用标准输入输出，而不要读写文件） 输入数据有多组。每组数据的第一行是在线 ID 的数目 n，Butterfly0923 的好友列表里一共 26 个 ID，所以 n 不会超过 26。接下来 n 行是这 n 个在线 ID，每行一个。按照我爱南开 BBS 站的规定，ID 由 2-12 个英文字母组成，大小写不敏感。再往下 n 行是从各人回信中得到的信息。

方便起见，Butterfly0923 把每条信息写成等式的形式。等号两边有一些项，每一项都是 num*ID 的形式，num 是一个正整数，没有符号，多项之间以加号分隔，最后一项可能是一个常数。Butterfly0923 自己也可能出现在等式中，注意它不是一个 ID ——它太长了。Butterfly0923 保证在一个等式中不会出现相同的 ID，每个人的距离（如果能算得出的话）都是整数。所有 ID 和等式中都不会出现任何前导、后缀以及符号两侧的空格。 输出 （请使用标准输入输出，而不要读写文件）

对于每一组输入，首先输出一行 Case #，这里 # 是按组从 1 开始的编号。

如果朋友们给 Butterfly0923 的信息不足以确定全部人的距离，就在第二行输出 “I?m not sure about someone?s

distance.” 否则第二行输出你计算出的最远距离，第三行输出跟最远距离对应的 ID，如果这样的 ID 不止一个，按照它们在输入中出现的顺序每行输出一个。 样例输入 样例输出 2 seaeagle doraemonok 1*seaeagle=4*Butterfly0923+200 1*doraemonok=12 3 unusualwater

Case 1: 2280 seaeagle Case 2: 1754 aliao 7

aliao gnr 13*unusualwater=1*Butterfly0923 1*aliao=1*Butterfly0923+1*gnr+194 1*gnr=2*Butterfly0923 提示 ⒈ 留意 n 的下限。 ⒉ ID 不区分大小写，但是大写字母是允许的。 ⒊ 常数项只会出现在最右边。 ⒋ 等式中的 Butterfly0923 实际上相当于常数，注意它可能会重复出现。 ⒌ 注意并列最远的情形。 ⒍ 注意不能确定的情形。 ⒎ 虽然系数及最后结果都是整数，但是计算过程中可能需要浮点数。 8

[E] 南开大学Onlinejudge 在线判题系统 http://acm.nankai.edu.cn

E. 羽毛球轨迹估算

时间限制：2秒 内存限制：32000KB

Butterfly0923 喜欢打羽毛球，尽管打得不是很好。某节杨明老师的羽毛球课上，刚刚打赢了 Butterfly0923 的英语系老陈得意的问：“嘿，你知道羽毛球的英文叫做什么？”“嗯?? feather ball 吧??”“No, badminton. Do you know why? 这是羽毛球起源的地方，是英国的一个小镇。”这时杨老师开始讲课：“大家看，羽毛球的飞行轨迹是很有特点的，跟排球篮球足球不一样，羽毛球向上升到最高点，然后几乎垂直落下来。”

Butterfly0923 突然对老陈说：“告诉我初始的速度，高度和角度，我可以告诉你这个球可以飞多远。”Butterfly0923 的想法是这样的：

假定飞行的羽毛球只受到竖直向下的重力G，和与飞行速度v方向相反的空气阻力f，且空气阻力的大小f = k v，其中k为常数。

设 t = 0 时球具有初速度v0，速度与水平方向夹角为 α，击球高度为y0。

比如，当 k = 0.018 时，一只重 10g 的羽毛球在离地面 2m的地方斜向上与水平方向成 45°角，以20m/s 的速度飞出，按照这个模型，经过 2.34 秒，羽毛球会落在大约 7.74m 远的地方，如下图所示：

9

Butterfly0923 对自己的模型还和力度打一些不同的球，老陈帮忙测下按照这个模型，Butterfly0923 打出

是很满意的，他正在尝试以不同的角度量实际距离。OK，你的任务是计算一去的球会落在离他多远的地方。

输入 （请使用标准输入输出，而不要读写文件）

输入由多组测试数据组成，每组测试数据一行，请一直处理到文件结束。

每组数据由五个数组成。第一个数是击球的角度 α，杨老师刚刚教了 Butterfly0923 如何扣杀，所以 α 可能是 [-90, 90] 内的任何整数。接下来是球的初速 v0 (m/s)、击球点的高度 y0 (m)、球的质量 m (kg) 和 阻力系数 k，都是非负的浮点数，m≥0，g=9.8 N/kg。 输出 （请使用标准输入输出，而不要读写文件） 对于每一组测试数据，输出两行，第一行为 “Case #:”，这里 # 是按组从 1 开始的编号，第二行为你计算出的落地距离，保留两位小数。 样例输入 样例输出 45 20 2 0.01 0.018 提示 ⒈ 注意输入数据的边界，有些情况可能需要特殊处理。 ⒉ 记得舍入到小数点后两位。 Case 1: 7.74 10

[I] 南开大学Onlinejudge 在线判题系统 http://acm.nankai.edu.cn

I. 有趣的纸牌游戏

Special Judge

时间限制：2秒 内存限制：32000KB

南开大学ACM参赛队要到外地参加现场赛的时候，为了在火车上解乏，带了纸牌。

游戏的规则很简单，首先将纸牌中的大、小王取出；然后，在剩余的牌中，每次取出4张牌，并规定A代表1，J代表11，，Q代表12，K代表13。而后，所有的玩家使用?+?、 ?-?、 ?*?、 ?/?、 ?(?、 ?)?将这四张牌所代表的数字连接起来，谁能够最快说出一种能够得到24的四则运算的表达式，或者最快确认这4张牌不可能组成结果为24的四则运算表达式谁就算赢。当然，每张牌都必须要使用，且只能使用一次。

为方便起见，大家约定?-?只代表减号，不代表负号。

现在，你能设计一个程序，来赢取这个纸牌游戏的胜利吗？ 输入 （请使用标准输入输出，而不要读写文件） 输入包括多组测试数据，你应当处理到输入结束为止。 每组输入数据只包括一行，这一行中有4个介于1和13的正整数（含1和13），代表这一轮游戏中所抽出的四张牌。这些数之间以一个空格相隔开。

输出 （请使用标准输入输出，而不要读写文件）

对于每组输入数据，输出两行。 对于第i组输入数据，输出的第一行为： Case i:

在输出的第二行，若按照游戏规则，这四张牌不能通过一个四则运算的表达式得到24，请输出： No Solution!

否则，请输出一个满足这样条件的表达式，允许带多余的括号。例如，对于四张牌：1 2 3 4，以下三种输出都是正确的： (1+2+3)*4 (((1+2)+3)*4) 1*2*3*4 样例输入 样例输出 1 2 3 4 Case 1: 1 1 1 1 (1+2+3)*4 Case 2: No Solution! 16

[J] 南开大学Onlinejudge 在线判题系统 http://acm.nankai.edu.cn

J. 自己当回裁判

时间限制：2秒 内存限制：32000KB

有的人认为，在程序竞赛中当裁判肯定比选手轻松。其实未必。为了让大家过一回当裁判的瘾，本次竞赛的最后一道题目就是让大家自己当一回裁判。

大家应该都接触过南开大学的在线判题系统（http://acm.nankai.edu.cn）了吧。相信细心地你应该注意到有的题目被标记上”Special Judge”的字样，比如，本次竞赛的第I题。

一般的题目，对于每组测试数据的输入，都会有唯一确定的输出。这样，在线判题系统就可以对于能通过编译，并且在满足题目时间限制和内存使用等限制的条件下正常运行结束的程序进行判断输出是否和预计的输出完全一致，并给予相应的判断结果。而标有”Special Judge”字样的题目，满足题目条件的结果可能并不唯一，这就需要裁判针对这个题目另外写一个程序，来判断程序的结果。

南开大学在线判题系统的评判结果一共有以下几种类型：Accepted、Wrong Answer、Compiling、Judging、Rejudging、

Time Limit Exceeded、Memory Limit Exceeded、Function Limit Exceeded、Runtime Error、Compile Error、Output limit Exceeded、Presentation Error。对于各种评判结果的说明，详见http://acm.nankai.edu.cn/faq.php 。 对于一个标有”Special Judge”的题目，在线判题系统仍然能够正确给出上述绝大多数的评判结果，但是对于结果是Accepted、Wrong Answer、Presentation Error的判决结果必须由”Special Judge”的程序给出。对于这三种评判

结果的说明如下：

Accepted Wrong Answer Presentation Error 程序的输出完全满足题意，通过了全部的测试数据的测试。 程序顺利地运行完毕并正常退出，但是输出的结果却是错误的。 程序输出格式不对，且如果输出去掉所有的空格，则和正确答案去掉所有的空格是完全一致的。 现在，请你为本次竞赛的第I题《有趣的纸牌游戏》写一个”Special Judge”的程序，来评判一个提交了的程序的结果。 输入 （请使用标准输入输出，而不要读写文件） 输入包括多组测试数据，你应当处理到输入结束为止。 每组输入数据包括3行，第一行是一个字符串，希望得到选手的程序给出的四则运算表达式或者”No Solution!” （不含引号），第二行是本组测试用例所要求使用的四个正整数（即第I题的一组测试数据的输入数据），相互之间以一个空格隔开，第三行为辅助答案，若测试用例无解，则该行为”No Solution!”，（不含引号）否则，该行为一个空行。 输出 （请使用标准输入输出，而不要读写文件） 对于每组输入数据，输出两行。对于第i组输入数据，输出的第一行为 “Case i:”。输出的第二行为你根据第I题的题意所给出的评判结果，即或为Accepted，或为Wrong Answer，或为Presentation Error。 样例输入

样例输出 17

(1+2+3)*4 1 2 3 4 1+2+3+4 1 2 3 4 (1 + 2 + 3)* 4 1 2 3 4 No Solution! 1 1 1 1 No Solution! Case 1: Accepted Case 2: Wrong Answer Case 3: Presentation Error Case 4: Accepted

18

本文来源：https://www.bwwdw.com/article/ohip.html