全国大学生程序设计竞赛训练题.docx
- 文档编号:10817773
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:24
- 大小:54.99KB
全国大学生程序设计竞赛训练题.docx
《全国大学生程序设计竞赛训练题.docx》由会员分享,可在线阅读,更多相关《全国大学生程序设计竞赛训练题.docx(24页珍藏版)》请在冰点文库上搜索。
全国大学生程序设计竞赛训练题
(2)联集
读入2个正整数a,b,请输出介于a,b之间(包含a,b)2,3,5倍数的联集大小。
Input(输入可能包含了好几列测试资料,每一列有2个整数a,b。
a=0b=0代表输入结束。
)
Output(对每一列输入,请输出联集的大小。
请参考SampleOutput)
SampleInput(110;1020;00;)
SampleOutput(8;7)
(3)Q100:
The3n+1problem
考虑以下的演算法:
1. 输入n
2. 印出n
3. 如果n=1结束
4. 如果n是奇数那么n=3*n+1
5. 否则n=n/2
6. GOTO2
例如输入22,得到的数列:
221134175226134020105168421
据推测此演算法对任何整数而言会终止(当列印出1的时候)。
虽然此演算法很简单,但以上的推测是否真实却无法知道。
然而对所有的n(0 给一个输入n,透过以上的演算法我们可以得到一个数列(1作为结尾)。 此数列的长度称为n的cycle-length。 上面提到的例子,22的cyclelength为16. 问题来了: 对任意2个整数i,j我们想要知道介于i,j(包含i,j)之间的数所产生的数列中最大的cyclelength是多少。 Input: 输入可能包含了好几列测试资料,每一列有一对整数资料i,j。 (0 Output: 对每一对输入i,j你应该要输出i,j和介于i,j之间的数所产生的数列中最大的cyclelength。 SampleInput: 110;101;100200;201210;9001000; SampleOutput 11020 10120 100200125 20121089 9001000174 (4)Q101: TheBlocksProblem 在早期人工智慧的领域中常常会用到机器人,在这个问题中有一支机器手臂接受指令来搬动积木,而你的任务就是输出最后积木的情形。 一开始在一平坦的桌面上有n块积木(编号从0到n-1)0号积木放在0号位置上,1号积木放在1号位置上,依此类推,如下图。 机器手臂有以下几种合法搬积木的方式(a和b是积木的编号): moveaontob 在将a搬到b上之前,先将a和b上的积木放回原来的位置(例如: 1就放回1的最开始位罝) ∙moveaoverb 在将a搬到b所在的那堆积木之上之前,先将a上的积木放回原来的位罝(b所在的那堆积木不动) ∙pileaontob 将a本身和其上的积木一起放到b上,在搬之前b上方的积木放回原位 ∙pileaoverb 将a本身和其上的积木一起搬到到b所在的那堆积木之上 ∙quit 动作结束 ∙前四个动作中若a=b,或者a,b在同一堆积木中,那么这样的动作算是不合法的。 所有不合法的动作应该被忽略,也就是对各积木均无改变。 Input输入含有多组测试资料,每组测试资料的第一列有一个正整数n(0 接下来为机器手臂的动作,每个动作一列。 如果此动作为quit,代表此组测试资料输入结束。 你可以假设所有的动作都符合上述的样式。 请参考SampleInput。 Output每组测试资料输出桌面上各位置积木的情形(每个位置一列,也就是共有n列),格式请参考SampleOutput。 SampleInput10 move9onto1 move8over1 move7over1 move6over1 pile8over6 pile8over5 move2over1 move4over9 quit 4 pile0over1 pile2over3 move1onto3 quit SampleOutput 0: 0 1: 1924 2: 3: 3 4: 5: 5876 6: 7: 8: 9: 0: 0 1: 2: 2 3: 31 (5)Q102: EcologicalBinPacking 有3个桶子用来装回收的玻璃瓶,玻璃瓶的颜色有三种: 棕色(Brown)、绿色(Green)、透明色(Clear)。 在这个问题里我们会告诉你每个桶子里的玻璃瓶的颜色及数量,现在要搬移桶子里的玻璃瓶使得最后每个桶子里都只有单一颜色的玻璃瓶,以方便回收。 你的任务就是要算出最小搬移的瓶子数。 你可以假设每个桶子的容量无限大,并且总共搬移的瓶子数不会超过231。 Input每笔测试资料一行,每行有9个整数.前3个代表第1个桶子里Brown,Green,Clear颜色的瓶子数。 接下来的3个数代表第2个桶子里Brown,Green,Clear颜色的瓶子数。 最后的3个数代表第3个桶子里Brown,Green,Clear颜色的瓶子数。 例如: 1015203012815831 表示有20个Clear色的玻璃瓶在第1个桶子里,12个Green色的玻璃瓶在第2个桶子里,15个Brown色的玻璃瓶在第3个桶子里。 Output对每一笔测试资料,输出3个桶子内最后存放之玻璃瓶颜色,以及最小搬移的瓶子数。 请以大写的'G'、'B'、'C'分别代表绿色(Green)、棕色(Brown)、透明色(Clear)。 例如: BCG30 代表最后搬移的结果第1个桶子内的玻璃瓶颜色为Brown,第2个桶子内的玻璃瓶颜色为Clear,第3个桶子内的玻璃瓶颜色为Green.并且总共搬移了30个玻璃瓶。 如果最小搬移瓶子数有一组以上的组合,请输出字典顺序最小的那一组答案。 Sampleinput 123456789 510520105102010 SampleOutput BCG30 CBG50 (6)Q103: StackingBoxes 在数学或电脑科学里,有些概念在一维或二维时还蛮简单的,但到N维就会显得非常复杂。 试想一个n维的“盒子”: 在二维空间里,盒子(2,3)可代表一个长为2个单位,宽为3个单位的盒子;在三维空间里,盒子(4,8,9)则是一个4*8*9(长、宽、高)的盒子。 至于在六维空间里,也许我们不清楚(4,5,6,7,8,9)长得怎样,不过我们还是可以分析这些盒子的特性。 在此问题里,我们要算出一组n维盒子里,它们的“最长套入串列”: b1,b2,......,bk,其中每个盒子 bi都可以“放入”盒子 bi+1中(1<=i 如果盒子D的n个维,能够存在一种重排,使得重排后,D每一维的量度都比E中相对应的维的量度还要小,则我们说盒子D能“放入”盒子E。 (用比较不严谨的讲法,这就好像我们将盒子D翻来翻去,看看能不能摆到E里面去。 不过因为我们考虑的是任一重排,所以实际上盒子不只可转来转去,甚至还可以扭曲。 )(还是看看下面的例子说明好了)。 譬如说,盒子D=(2,6)能够被放入盒子E=(7,3)里,因为D可以重排变为(6,2),这样子D的每个维的量度都比E里对应的维还要小。 而盒子D=(9,5,7,3)就没办法放进盒子E=(2,10,6,8),因为就算再怎摸重排D里的维,还是没办法符合“放入”的条件。 不过F=(9,5,7,1)就可以放入E了,因为F可以重排成(1,9,5,7),这样就符合了放入的条件。 我们今定义“放入”如下: 对于任两个盒子D=(d1,d2,......,dn)和E=(e1,e2,......,en),如果存在一种1..n的重排π,使得对于任何的1<=i<=n,皆有dπ(i) Input输入包含多组测试资料。 每组测试资料的第一列有两个数字: 第一个是盒子的数量k,然后是盒子的维数n;接下来有k列,每列有n个整数表示一个盒子的n个维的量度,量度之间由一个以上的空白做区隔。 第一列表示第一个盒子,第二列表示第二个盒子,依此类推;此问题里,盒子的维数最小是1,最大是10,并且每组测试资料中盒子的个数最多为30个。 Output对于每一组测试资料,你必须输出两列数字: 第一列是“最长套入串列”的长度,第二列是按照内外顺序,印出“最长套入串列”里盒子的编号(其中编号是按照在输入档案的每组数列里所出现的顺序,例如第一个盒子就是1号...等等。 )最里面的盒子(或是最小的)摆在第一个,再来是次小的,依此类推;如果对于每一组的盒子,存在两个以上的“最长套入串列”,输出任何一个均可。 SampleInput 52 37 810 52 911 2118 86 522013010 231579113 40503424144 91011121314 3141882717 443213194119 123456 80374718219 SampleOutput 5 31245 4 7256 (7)Q104: Arbitrage 所谓的“三角套汇(arbitrage)”就是在几种外币中做金钱的交易,期待从汇差中获取少许的利润。 例如: 1元美金可以买0.7英镑,1元英镑可以买9.5法朗,1元法朗可以买0.16美金。 所以如果我们把1元美金换成英镑,再把英镑换成法朗,最后再把法朗换回美金,那么最后得到的美金将是: 1*0.7*9.5*0.16=1.064美元。 也就是说我们可以从中获取汇差0.064美元,相当于赚了6.4%。 请你写一个程式找出是否有这样套汇的情况,可以获取如上所述的利益。 要产生一个成功的套汇,在换外币的过程中,开始的币种一定得等于最后的币种。 但是从哪一种开始都可以。 Input输入含有多组测试资料。 每组测试资料的第一列,有一个整数n(2<=n<=20),代表共有多少种币种。 接下来的n列代表这n种外币之间的汇率转换表。 每列有n-1个数。 这n-1个数分别代表该币种1元可以换取其他币种多少元(自己换自己当然是1,所以不会出现)。 所以第1列的n-1个数依序分别代表第1种外币1元可以换取,第2种外币,第3种外币,第4种外币...第n种外币各多少元。 而第2列的n-1个数依序分别代表第2种外币1元可以换取,第1种外币,第3种外币,第4种外币...第n种外币各多少元。 依此类推,第n列的n-1个数依序分别代表第n种外币1元可以换取,第1种外币,第2种外币,第3种外币...第n-1种外币各多少元。 请参考SampleInput。 Output: 对每组测试资料输出一列,代表一连串币种转换的动作,并且套汇获利需大于1%(>0.01)。 如果有不止一种转换可以获取超过1%的利益,请输出转换次数最少的。 如果转换次数最少的不止一种,那么任何一种都可以。 请注意: 在这里只要求转换次数最少,并没有要求获利要最大,只要能大于1%就可以了。 另外,国税局还规定最多只能转换n次(n是币种的数目)。 像1,2,1这样的转换次数为2。 如果在n次的转换内都无法获利超过1%,请输出noarbitragesequenceexists。 SampleInput SampleOutput 3 1.2.89 .885.1 1.10.15 4 3.10.00230.35 0.210.003538.13 200180.55910.339 2.110.0890.06111 2 2.0 0.45 121 1241 noarbitragesequenceexists (8)Q105: TheSkylineProblem 由于高速绘图电脑工作站的出现,CAD(computer-aideddesign)和其他领域(CAM,VLSI设计)都充分使用这些电脑的长处。 而在本问题中,你必须帮助建筑师,根据他所提供给你都市中建筑物的位置,你得帮他找出这些建筑物的空中轮廓(skyline)。 为了使问题容易处理一些,所有的建筑物都是矩形的,并且都建筑在同一个平面上。 你可以把这城市看成一个二度平面空间。 每一栋建筑物都以(LiHiRi)这样的序列来表示。 其中Li和Ri分别是该建筑物左边和右边的位置,Hi则是建筑物的高度。 下方左图就是(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)这八栋建筑物的位置图。 而你的任务就是画出这些建筑物所构成的轮廓,并且以(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)这样的序列来表示如下方右图的轮廓。 Input只有一组测试资料。 每列有一栋建筑物的资料。 建筑物不会超过50栋。 所有的数字都小于10000。 并且建筑物已按照Li排好序。 Output输出为描述建筑物轮廓的向量。 在轮廓向量(v1,v2,v3,......,vn-1,vn)中,在i为奇数的情形下,vi表示一条垂直线(x座标),在i为偶数的情形下,vi表示一条水平线(高度)。 轮廓向量就像一只虫从最左边建筑物走起,沿著轮廓路径水平及垂直的行走的路径。 所以最后轮廓向量的最后一个数一定为0。 SampleInput 1115 267 3139 12716 14325 191822 231329 24428 SampleOutput 1113139012716319182232313290 (9)Q107: TheCatintheHat 一只神奇聪明猫走进了一间乱七八糟的房间,他不想自己动手收拾,他决定要找帮手来工作。 于是他从他的帽子中变出了N只小猫来帮他(变出来的猫,高度为原来猫的1/(N+1))。 这些小猫也有帽子,所以每一只小猫又从他的帽子中变出N只小小猫来帮他。 如此一直下去,直到这些小小小....猫小到不能再小(高度=1),他们的帽子无法再变出更小的猫来帮忙,而这些最小的猫只得动手打扫房间。 注意: 所有猫的高度都是正整数。 在这个问题中,给你一开始那只猫的高度,以及最后动手工作的猫的数目(也就是高度为1的猫的数目)。 要请你求出有多少只猫是没有在工作的,以及所有猫的高度的总和。 Input每组测试资料一列,有2个正整数分别代表一开始那只猫的高度,以及最后动手工作的猫的数目。 00代表输入结束。 Output每组测试资料输出一列,包含2个正整数分别代表有多少只猫是没有在工作的,以及所有猫的高度的总和。 SampleInput 216125 57648011679616 641 00 SampleOutput 31671 33592330275911 6127 (10)Q108: MaximumSum 给你一个NxN的阵列,请你找出有最大和的子区域(sub-rectangle)其和为多少。 一个区域的和指的是该区域中所有元素值的和。 一个区域是指相连的任意大小的子阵列。 例如,对以下的二维阵列: 其最大和的子区域位于左下角,并且其和为15。 如下所示: Input只有一组测试资料,第一列有一个正整数N(N<=100),代表此二维阵列大小为NxN。 从第二列起有N2个整数,代表此阵列的内容。 每个整数都介于-127到127之间,且以列为主(row-major)的顺序排列。 SampleInput即为上图所示的阵列。 Output输出有最大和的子区域其和是多少。 SampleInput 4 0-2-7092-62 -41-41-1 80-2 SampleOutput 15 (11)Q111: HistoryGrading 在资讯科学中有一些是关于在某些条件限制下,找出一些计算的最大值。 以历史考试来说好了,学生被要求对一些历史事件根据其发生的年代顺序来排列。 所有事件顺序都正确的学生无疑的可以得满分。 但是那些没有全对的人又该如何给分呢? 以下有2种可能的给分方式: 每个与标准答案的顺序相同的事件得1分1。 每个在最长(但不一定要连续)的序列事件中,其相对的顺序亦可以在标准答案发现者,每个事件得1分。 举例说明: 如果有4个事件其发生时间的顺序依次是1234(就是标准答案啦,意思是第1个事件发生顺序为1,第2个事件发生的顺序为2,......)。 所以如果学生回答此4个事件发生的顺序依次是1324的话,根据上面第1种方法可以得2分(第1个及第4个事件)。 但是如果以上面第2种方法可以得3分(124或者134其相对的顺序可以在标准答案发现)在本问题中,请你写一个程式以第2个方法算出学生该得多少分。 Input只考一次试,所以输入的第1列有一个整数n(2<=n<=20)代表此次历史考试有多少个事件要排序。 第2列为标准答案,有n个正整数c1,c2,,(其内容为1到n的某种排列),c1代表第1个事件发生的顺序,c2代表第2个事件发生的顺序,依此类推。 从第3列开始每列为一学生的答案,每列有n个正整数r1,r2,......rn,(其内容亦为1到n的某种排列),r1代表学生回答第1个事件发生的顺序,r2代表学生回答第2个事件发生的顺序,依此类推。 Output对每一学生的答案,输出其所得的分数。 SampleInput 10 31249510687 12345678910 47231069158 31249510687 21013849576 SampleOutput65109 (12)Q112: TreeSumming LISP是最早的高阶程式语言之一,而Lists则是LISP中最重要的资料结构。 Lists可以很简单的用来表达其他的资料结构,例如: tree。 在这个问题中,给你LISP中的S表示式(S-expression),请你写一个程式判断这表示式(整数的二元树)是否存在一条由根节点到树叶的路径,且路径上各节点的值的和为某一特定的数n。 例如: 在以下的树中共有4条从根到树叶的路径。 而各路径的和分别为27,22,26以及18。 在LISP中的S表示式有以下的格式emptytree: : =();tree: : =emptytree|(integertreetree) 上图中的树若以S表示式表达为: (5(4(11(7()())(2()()))())(8(13()())(4()(1()()))))注意: 在树中所有的叶节点为(integer()())既然空树不存在任何根到叶的路径,任何对空树是否有某个和的询问,其答案都是否定的。 Input输入含有多组测试资料。 每组测试资料的开头有一个整数n。 接下来为一S表示式。 所有的S表示式一定是合法的,但是可能会跨多列,并且可能含有空白字元。 请参考SampleInput。 Output对每一组测试资料输出一列。 如果S表示式所表达的树存在一条由根到叶的路径,且路径上节点值的和为n的话,则输出yes,否则输出no。 SampleInput 22(5(4(11(7()())(2()()))())(8(13()())(4()(1()())))) 20(5(4(11(7()())(2()()))())(8(13()())(4()(1()())))) 10(3 (2(4()()) (8()())) (1(6()()) (4()()))) 5() SampleOutput Yesyes Nono Q113: PowerofCryptography 给你两个整数n(n>=1)和p(p>=1),你必须写一个程式来计算出p的正n次方根。 在这个问题里,p皆可表成kn的形式,其中k为整数。 (k也就是你的程式所要求的) Input每组测试资料2列,第1列有1个整数n(1<=n<=200),第2列有1个整数p(1<=p<=10101)。 并且存在一个整数k,(1<=k<=109),使得kn=p。 Output每组测试资料请输出k。 SampleInput 2 16 3 27 7 4357186184021382204544 SampleOutput 4 3 1234 Q115: ClimbingTrees 原翻译者: untitled 这个问题的目地在讨论两个人在所谓的“家庭树”(familytree即族谱)里,他们的关系为何。 给你两组名字: 第一组里有若干对名字,就是所谓的“孩子,家长对”(child-parentpairs),也就是一对名字,前面的名字是孩子的名字,而后面的名字为其家长的名字;第二组则也有若干对名字,是“欲查询对”(querypairs),其表达格式跟前面的“孩子,家长对”一样有两个名字。 给你这两组若干对的名字,你必须写个程式来判断在“欲查询对”里,每对的那两个人彼此关系为何。 在这里我们设定一个人只会有一个家长(虽然我们都知道每个人都有父、母亲二者,但是在本问题中,我们仅以其中一人代表) 在此问题里,我们说“孩子,家长对”p、q表示p是q的孩子。 我们为了要表示出所谓的关系,我们先看下面的定义: ∙当在输入档案的“孩子,家长对”里有pq(或者qp),我们说p是q的0级子孙(或者0级祖先) ∙当在输入档案的“孩子,家长对”里有pr(或者qr),而且r是q的(k-1)级子孙(或者p是r的(k-1)级祖先),则称p是q的k级子孙(或者k级祖先) 在这个问题里,任两个人p,q之间的关系一定可归类到下列四种的其中之一(如果他们有关系的话) 1.直系子孙类(child): child、grandchild、greatgrandchild、greatgreatgrandchild,依此类推。 (即: 孩子、孙子、曾孙、曾曾孙...) 根据定义,当输入档案里的“孩子,家长对”有pq存
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国大学生 程序设计 竞赛 训练