搜集的南开大学的ACM试题与你共享[A]南开大学Onlinejudge 在线判题系统A.Lucy的新难题时间限制：2秒内存限制：32000KB不知不觉，南开大学第三届“我为程序狂”又要拉开帷幕了。

这天，Lucy也来到南开大学ACM协会，与大家共同欢庆NKPC的三周岁的日子。

谈笑间，ACM协会的主席拿了圆形的生日蛋糕。

大伙开心地唱完了生日歌，一起吹灭了蜡烛。

要分蛋糕了，大家都很兴奋。

本着公平的原则，每位到场的人员都要在蛋糕上切一刀。

ACM协会的主席事先知道有n位朋友会参与这个欢庆宴会。

为了方便大家切蛋糕，主席在订蛋糕的时候就嘱咐在蛋糕的边缘布置上2n朵小花。

每个人切蛋糕都会从蛋糕的边缘的一朵小花笔直地切到蛋糕的另一端的小花，来表达自己对NKPC的祝福。

为了尊重其他同学，每个人在切蛋糕一定不会和蛋糕上已有的切痕相交，也不会从别人已切过的小花作为切蛋糕的起点或终点。

同时，每位同学在切蛋糕的时候，都要保证后面所有的同学都能够按照上述的规则切蛋糕。

这样，蛋糕上就留下n条切痕。

Lucy眨巴眨巴眼睛，问，要是不考虑切蛋糕的先后顺序和谁切的哪一刀，这蛋糕切完了共有多少种切法呢？大家听了呵呵一笑，说，那就把这个问题留给NKPC3，作为《Lucy的新难题》吧。

相信聪明的你，一定能够帮Lucy解答她的难题的，对吗？输入包括多组测试数据，你应当处理到输入结束为止。

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

对于每组输入数据，输出两行。

对于第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，每个人的距离（如果能算得出的话）都是整数。

所有ID 和等式中都不会出现任何前导、后缀以及符号两侧的空格。

如果朋友们给Butterfly0923 的信息不足以确定全部人的距离，就在第二行输出“I‟m not sure about someone‟s distance.”否则第二行输出你计算出的最远距离，第三行输出跟最远距离对应的ID，如果这样的ID 不止一个，按照它们在[E]南开大学Onlinejudge 在线判题系统E.羽毛球轨迹估算时间限制：2秒内存限制：32000KBButterfly0923 喜欢打羽毛球，尽管打得不是很好。

某节杨明老师的羽毛球课上，刚刚打赢了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 远的地方，如下图所示：Butterfly0923 对自己的模型还是很满意的，他正在尝试以不同的角度和力度打一些不同的球，老陈帮忙测量实际距离。

OK，你的任务是计算一下按照这个模型，Butterfly0923 打出去的球会落在离他多远的地方。

每组数据由五个数组成。

第一个数是击球的角度α，杨老师刚刚教了Butterfly0923 如何扣杀，所以α 可能是[-90, 90] 内的任何整数。

接下来是球的初速v0 (m/s)、击球点的高度y0 (m)、球的质量m (kg) 和阻力系数k，都是非负的浮点数，[F]南开大学Onlinejudge 在线判题系统F．找出公共区域时间限制：2秒内存限制：32000KBBetty喜欢玩剪纸。

现在她有两张已经剪好的凸多边形需要粘在一起。

她打算在两张纸的公共区域涂满浆糊，你能计算出这个公共区域有多大吗？输入由两部分组成，每部分的第一行为一个整数介于3和30之间，表示该凸多边形的顶点数目。

下面各行每行包含两个实数，表示凸多边形顶点的横纵坐标。

实数的小数部分为六位且绝对值均小于1000。

顶点顺序按逆时针给出。

请输出一个包含两位小数的实数，表示两个凸多边形的公共区域面积。

[G]南开大学Onlinejudge 在线判题系统G．游戏时间限制：2秒内存限制：32000KB我们在休闲娱乐的时候常常会去玩一些益智小游戏，像扫雷、祖玛、俄罗斯方块之类的恐怕已经没有几个人没玩过了吧。

像这样的游戏能让我们在学习的紧张过后得到一点放松，而且又能活动一下脑子。

现在许多RPG风格的游戏也逐渐的加入一些小游戏的元素来丰富游戏内容，像GBA游戏《被狙击的名侦探》，PC游戏《双星物语》等等就都出现了类似于下面这种样式的小游戏：在一个n×n的方格中，每个方格有一个棋子，棋子或为黑色、或为白色，如图中所示。

现在对棋盘进行操作，每步操作只能选中一个方格，之后这个方格及其上下左右四个相邻的方格（如果有的话）中的棋子均变为相反的颜色。