历届程序设计acm试题
- 格式:doc
- 大小:649.50 KB
- 文档页数:18
搜集的南开大学的ACM试题与你共享
[A]南开大学Onlinejudge 在线判题系统
A.Lucy的新难题
时间限制:2秒内存限制:32000KB
不知不觉,南开大学第三届“我为程序狂”又要拉开帷幕了。这天,Lucy也来到南开大学ACM协会,与大家共同欢庆NKPC的三周岁的日子。
谈笑间,ACM协会的主席拿了圆形的生日蛋糕。大伙开心地唱完了生日歌,一起吹灭了蜡烛。
要分蛋糕了,大家都很兴奋。本着公平的原则,每位到场的人员都要在蛋糕上切一刀。ACM协会的主席事先知道有n位朋友会参与这个欢庆宴会。为了方便大家切蛋糕,主席在订蛋糕的时候就嘱咐在蛋糕的边缘布置上2n朵小花。
每个人切蛋糕都会从蛋糕的边缘的一朵小花笔直地切到蛋糕的另一端的小花,来表达自己对NKPC的祝福。为了尊重其他同学,每个人在切蛋糕一定不会和蛋糕上已有的切痕相交,也不会从别人已切过的小花作为切蛋糕的起点或终点。同时,每位同学在切蛋糕的时候,都要保证后面所有的同学都能够按照上述的规则切蛋糕。这样,蛋糕上就留下n条切痕。
Lucy眨巴眨巴眼睛,问,要是不考虑切蛋糕的先后顺序和谁切的哪一刀,这蛋糕切完了共有多少种切法呢?
大家听了呵呵一笑,说,那就把这个问题留给NKPC3,作为《Lucy的新难题》吧。
相信聪明的你,一定能够帮Lucy解答她的难题的,对吗?
输入包括多组测试数据,你应当处理到输入结束为止。
每组输入数据中,都只有一行,仅包含一个正整数n,且0 对于每组输入数据,输出两行。对于第i组输入数据,输出的第一行为”Case i:”,输出的第二行为切蛋糕的方法数。 [B]南开大学Onlinejudge 在线判题系统 B.保龄球 时间限制:2秒内存限制:32000KB 南开大学ACM协会的一个元老毕业后,开了家保龄球馆。他需要为他的保龄球馆的计算机写一个记分的程序。 一局(GAME)保龄球分为10格,每格里有两次投球机会,如在第一次投球时没能全中,就有需要投第二球。 每一格可能出现三种情况: 1.失球(MISS) 无论何种情况,在一格的两次投球时,未能击倒10个瓶,此格的分数为击倒的瓶数。如果一次击球中未击倒一个瓶,则用一个’-’标记。 2.补中(SPARE) 要一次击倒十个瓶子并非那么容易的!如果在第一次掷球后,你还有一次机会来击倒该格第一球所留下的情致。当第二次投球击倒该格第一球余下的全部瓶子,称为补中,用一个‘/’符号表示。补中的记分是10分加上下一次投球击倒的瓶数。 3.全中(STRIKE) 当每一格的第一次投球击倒全部竖立的十个瓶时,称为全中,用一个(×)符号表示。全中的记分是10分(击倒的瓶)加该球员下两次投球击倒的瓶数。 但在第十格中情况比较特殊: (1)如第二次投球未补中,则第十格得分为第九格得分加上第十格所击倒瓶数。 (2)如第二次投球补中,则追加一次投球机会,第十格得分为第九格得他加上10加上追加一次投球击倒瓶数。 (3)如第一球为全中,则追上加二次投球机会,第十格得分为第九格得分加上10加追加二次投球击倒的瓶数。因此从第一格到第十格的两次追加投球,都为全中,则为12个全中,得分为满分300分。 每组输入数据中,都只有一行,包含一局的记分符号,相邻的两个符号之间以一个空格隔开。记分的符号仅包括…-‟(不含 对于每组输入数据,输出两行。对于第i组输入数据,输出的第一行为”Case i:”,输出的第二行为10个整数,表示每格的累计得分。相邻的两个得分以一个空格隔开。 [C]南开大学Onlinejudge 在线判题系统 C.计算机硬件评分系统 时间限制:2秒内存限制:32000KB 小C听说微软新推出的一款操作系统Windows Vista可以对电脑的配置进行评分,很感兴趣。由于小C对硬件软件方面都很了解,就通过一系列的市场调查与实践,制作了一款自己的计算机硬件评分系统。此系统可以对CPU、内存、硬盘、主板、显卡五部分分别进行评分,分数为不超过100的正整数,并以这五个分数中的最低分作为对计算机的总体评分。 同寝室的小D打算最近购置一台新电脑,他请小C给他当参谋,小C就提供了一些当前的CPU、内存、硬盘、主板、显卡五种硬件的品牌、价格以及每个硬件由他所制作的系统所评价出来的分数。小D准备至多用N元来购买这五种硬件并且他还希望能够得到一台电脑有尽量高的总体评分。 作为寝室长的你主动要写一个程序来帮助小D购买电脑。 表示资料中所提供的这种硬件品种数目M。下面M行每一行都描述了一个品种的情况,包括两个整数,以空格隔开。第一个 费。 [D]南开大学Onlinejudge 在线判题系统 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 得到的信息,希望你能告诉他最远的地方有多少公里,是谁在那里。 会超过26。接下来n 行是这n 个在线ID,每行一个。按照我爱南开BBS 站的规定,ID 由2-12 个英文字母组成,大小写不敏感。再往下n 行是从各人回信中得到的信息。 方便起见,Butterfly0923 把每条信息写成等式的形式。等号两边有一些项,每一项都是num*ID 的形式,num 是一个正整数,没有符号,多项之间以加号分隔,最后一项可能是一个常数。Butterfly0923 自己也可能出现在等式中,注意它不是一个ID ——它太长了。Butterfly0923 保证在一个等式中不会出现相同的ID,每个人的距离(如果能算得出的话)都是整数。