作业2 2011年安徽省第二届“达内杯”大学生程序设计竞赛题.doc

2011年安徽省第二届“达内杯”大学生程序设计竞赛题Problem A 幸运数字Description有的人喜欢收集邮票，有的人喜欢收集CD，有的人喜欢收集书Gardon也有收集癖，然而他收集的是数字，而且是那些在他看来非常幸运的数字。Gardon觉得，如果一个数字模它的各个数位上的数字之和为0的话，那它就是一个幸运数字。比如说数字18就是一个幸运数字。因为它各个数位上的数字之和为1+8=9，18模9等于0。Gardon是个怕麻烦的人，他不想自己去计算一个数字是不是幸运数字。所以作为Gardon的好朋友，你必须写个程序帮助他。Input有多组测试数据，每组数据输入一个整数n(1=n=1000000000)，输入以文件结束。Output如果数字n是幸运数字，输出”yes”，否则输出”no”。Sample Input1118Sample OutputnoyesProblem B 转换二叉树DescriptionDJ非常痴迷于数据结构，二叉树是他最喜欢的结构模型。这种每个顶点的度不大于2的简单的图总是能激发他的灵感。然而，二叉树的表示方法是一个困扰他已久的问题。如果用链表表示，不直观；画成图形，计算机又难以存储。好在他现在发现了一种既直观，计算机又便于存储的表示方法。该方法定义如下：1、如果二叉树中节点X是叶子节点，则该节点直接表示为X。2、如果二叉树中节点X有左子树，则该节点表示为(.)X，括号内为X的左子树。3、如果二叉树中节点X有右子树，则该节点表示为X(.)，括号内为X的右子树。4、如果二叉树中节点X有左右子树，则该节点表示为(.)X(.)，左边括号内为左子树，右边括号内为右子树。现在DJ有许多二叉树的先序序列和中序序列，DJ要你写个程序帮他把这些二叉树转换为上述表示方法。Input输入第一行为一个整数N，表示有N个待转换的二叉树。接下来有N行，每行由两个字符串组成，中间用空格分开。每行的第一个字符串为二叉树的先序序列，第二个字符串为二叉树的中序序列。输入字符串由大写字母组成，每个字母代表二叉树的一个节点，不会有两个相同的字母。你可以假设不会输入无效数据。Output每组数据输出占一行，输出转换后的二叉树。Sample Input2AB ABABCD BCADSample OutputA(B)(B(C)A(D)Problem C 取石子DescriptionCydorniaKnight和Yarmu都是传说中的高智商ACMer。两人关系就如高山流水、伯牙子期，然而都自诩自己智商比对方高。某日，他们相会于长江淮河之间、承东启西、接连中原、贯通南北的历史重镇合肥。决定通过经典取石子游戏一较高下。游戏规则为：1.给定n个石子；2.两人轮流取，CydorniaKnight先取；3.第一次不能把所有石子都取完；4.每次至少取一个并且下一次取的石子数不能比上一次取的多；5.先取完所有石子者获胜。CydorniaKnight和Yarmu都会采用最优策略取石子。你的任务是计算出如果给定的石子数为n，CydorniaKnight能否取胜，以及如果CydorniaKnight可以取胜，那他第一次应该取多少石子。Input有多组测试数据，每组数据输入一个整数n(2=n=1000000000)，输入以文件结束。Output如果CydorniaKnight可以取胜，输出win，并且输出第一次至少应该取多少石子，中间用一个空格分开。否则输出”lose”。Sample Input23Sample Outputlosewin 1Problem D 关键词统计Description搜索引擎需要计算关键词在文章中的相关性，请你写一个程序统计一个单词（不区分大小写）在文章中出现的次数（单词指一个小写的英文单词，全部由小写英文字母组成。单词的前后必须是字母字符或空字符）。以上是上一届省赛的第一题统计赛后，小盆友们尝试把自己的程序安插到自己的搜索引擎时却发现一个问题：当服务器遇到大量访问时，实验室仅有的一台老爷机式服务器显得十分不给力。于是希望能让服务器在一秒钟内顶住庞大的关键词查询压力，你能帮助他们吗？Input仅一组测试数据 第一行是一些句子，表示一篇文章。（文章长度不超过200000个字符）第二行是一个数字N(1=N=10162)，代表查询的数目。以下每行一个单词(单词由小写字母组成，长度不超过20)Output每组测试数据输出一行，表示这个单词在文章中出现的次数。Sample InputDavid:hello,lily. Lily:oh,david!hello,how are you?4hellodavellodavidSample Output2002Problem E 搬书Description学校的新图书馆建好了，于是要把老图书馆的书搬到新馆。老图书馆的书非常多，而且都分门别类排放好了。搬书就成了个大问题，不仅要把所有书都搬过去，而且不能把顺序弄乱了。大家商量决定，先用箱子把书按顺序装好后再搬过去。每本书都有一定的体积，一个箱子只能装体积之和不大于它容积的书。箱子要从市场上买，大家都不想浪费。所以就有了一个问题，如果要用m个箱子把所有书装好，那么每个箱子容积至少要是多少呢？假设每个箱子的大小是一样的。Input输入第一行为两个整数n和m(1=n=10000,1=m=100)，表示一共有n本书，使用m个箱子。接下来一行有n个整数表示每本书的体积v(1=v=10000)。注：书要按顺序装进箱子，所以只有连续的几本书才能装进一个箱子。Output每组数据输出占一行，输出每个箱子容积至少是多少。Sample Input2 11 3Sample Output4Problem F 水晶球Description在国王的城堡中，有一个能够预言未来的水晶球。王国中的少女都去城堡中预言自己的未来。水晶球会告诉每个少女，她在未来能有多么漂亮的相貌，有多么高的智慧以及有多么多的财富。但是除此之外，水晶球还会告诉她王国中是否有少女无论是相貌、智慧还是财富都超过她。女人是奇怪的动物，如果她得知有其他人在所有方面都超过自己时，她就会从城堡中跳下去- -#。现在告诉你王国中有N个少女，以及每个少女在未来所能达到的相貌、智慧以及财富。你的任务是计算出有多少少女会从城堡中跳下。相貌、智慧以及财富都用整数表示，数值越大越好。Input有多组测试数据，输入以文件结束。每组数据第一行为一个整数N(N = 50000)，表示有N个少女。接下来有3行，每行分别有N个整数，每行第i个数对应的是第i个少女的值。第1个是相貌值，第2是智慧值，第3是财富值。所有数字的绝对值小于1000000000。 Output每组数据输出一个整数，占一行。Sample Input31 4 23 3 22 5 3Sample Output1Problem G 星际航行Description船长木木驾着飞船开往木星，期间要穿过小行星带，为了安全起见，飞船上装有微波扫描系统，可获知前方小行星的位置和速度，飞船根据信息计算出是否会与之相撞，并警告船长，船长根据警告调整飞船的位置，避免发生机毁人亡的悲剧。飞船的形状视为长方形，小行星的形状视为圆形。当前方发现一颗小行星时，扫描系统会向飞船提供一张二维平面图，上面标注那颗小行星的坐标、速度，以及飞船的坐标、速度，飞船上的警告程序计算出是否会相撞，并通知船长。Input输入包含多组测试数据，每组测试数据占一行，包含13个浮点数：AX AY BX BY CX CY VX VY OX OY R VOX VOY其中AX AY BX BY CX CY表示长方形飞船顺时针给出的左上角、右上角、右下角坐标；VX VY表示飞船的速度矢量；OX OY表示那颗小行星的圆心坐标；R表示小行星的半径；VOX VOY表示小行星的速度矢量；输入以文件结束符EOF结束。 Output对于每组测试数据，输出飞船是否会与小行星相撞。 如果飞船不会与小行星相撞，输出NO，否则输出YES。浮点数精确到1e-8。Sample Input0 1 1 1 1 0 1 0 3 0 1 -1 00 1 1 1 1 0 1 0 3 0 1 2 0Sample OutputYESNO提示：本题属于标准数学题解法，需要建立好合适的模型Problem H 技术员BangFuDescriptionBangFu是通讯公司的技术员。某个星期一刚去上班，BOSS就给了他一个任务，去非洲检查通讯设备！这让他感觉非常不爽，他非常讨厌这项工作。更让他感觉不爽的是去的路费还得自己掏！但是最最最让他感觉不爽的是，如果完成任务后在工作日回来，万恶的BOSS肯定还会给他新的任务！连休息的机会都没有！这实在是太糟糕了。BangFu多么希望完成任务后能在周六或者周末回来。如果在这个基础上能够省点路费，那就更好了。作为BangFu的好朋友，你必须帮助他。假设BangFu一共要去N-1个地方检查设备，分别编号为1 到N-1。起始地点在公司，编号为0，完成检查后他要返回公司。BangFu在每个地方要花1天时间检查，他不会去已经检查过的地方，检查完所有设备前也不会返回公司。而且他不愿意把时间浪费在非洲，就是说完成检查他立马会去另外一个地方。现在告诉你这N个地点之间路线情况，帮他选择一条最佳路线吧。Input有多组测试数据，每组数据第一行为两个整数N和M。N表示一共有N个地点，M表示这N的地点之间有M条路线。接下来有M行，每行4个整数x、y、p、t。表示从x到y有一条路线，走这条路线要花p块钱和t天时间。所有路线都是单向的，两个地方可能有多条路线。(1N=10,0=M=200,x!=y)。Output每组数据输出占一行。如果BangFu不能完成任务，输出”Its not my thing!”； 如果BangFu可以完成任务，但是不能周六或者周日回来，输出”Oh, My god!”；如果BangFu可以完成任务，并且能够周六或者周日回来，输出他最少要花销的车费。Sample Input2 20 1 1 31 0 1 12 20 1 1 21 0 1 13 40 1 2 31 0 1 40 2 2 52 0 1 7 Sample Output2Oh, My god!Its not my thing! Hint第一组数据中，BangFu去地点1检查设备。去的路上花了3天，维修花了1天，回来路上花了1天，一共花了5天。去的时候是星期一，所以正好星期六回来。Problem I 百头百脚Time Limit: 1000 MS Memory Limit: 65536 KBTotal Submissions: 7 Accepted: 5Description兔子野鸡九头鸟，百头百脚朝下跑。这个是著名的百头百脚问题。这里有一个类似的问题，假设一只兔子有一个头四只脚，一只鸡有一个头两只脚。现在告诉你一共有n个头m只脚。你能用程序计算出一共有多少只兔子，多少只鸡吗？Input有多组测试数据，输入两个整数n和m，表示有n个头m只脚。数据保证有解。输入以文件结束。Output每组数据输出占一行，输出有多少只兔子多少只鸡，中间用一个空格分开。Sample Input3 8Sample Output1 2转载说明：本资源来源于异域世界网www.yangli89.lingd.n