2021年全国大学生程序设计竞赛训练题.doc

(2) 联集
读入2个正整数a,b，请输出介于a,b之间（包括a,b）2,3,5倍数联集大小。
Input（输入也许包括了好几列测试资料，每一列有2个整数a,b。
a=0 b=0 代表输入结束。）
Output（对每一列输入，请输出联集大小。请参照Sample Output ）
Sample Input（1 10 ；10 20；0 0；）
Sample Output（8；7）
（3）Q100：The 3n + 1 problem
考虑如下演算法：

1.         输入 n
2.         印出 n
3.         如果 n = 1 结束
4.         如果 n 是奇数 那么 n=3*n+1
5.         否则 n=n/2
6.         GOTO 2
例如输入 22，得到数列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
据推测此演算法对任何整数而言会终结 (当列印出 1 时候)。虽然此演算法很简朴，但以上推测与否真实却无法懂得。然而对所有n ( 0 < n < 1,000,000 )来说，以上推测已经被验证是对的。 
给一种输入 n ,透过以上演算法咱们可以得到一种数列（1作为结尾）。此数列长度称为ncycle-length。上面提到例子，22 cycle length为 16. 
问题来了：对任意2个整数i，j咱们想要懂得介于i，j（包括i，j）之间数所产生数列中最大cycle length是多少。
Input:输入也许包括了好几列测试资料，每一列有一对整数资料 i，j 。 ( 0< i，j < 10000 )
Output：对每一对输入 i ，j你应当要输出 i，j和介于i，j之间数所产生数列中最大cycle length。
Sample Input：1 10；10 1；100 200；201 210；900 1000；
Sample Output
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174
（4）Q101：The Blocks Problem
在初期人工智慧领域中经常会用到机器人，在这个问题中有一支机器手臂接受指令来搬动积木，而你任务就是输出最后积木情形。一开始在一平坦桌面上有n块积木（编号从0到n-1）0号积木放在0号位置上，1号积木放在1号位置上，依此类推，如下图。
机器手臂有如下几种合法搬积木方式（a和b是积木编号）：
move a onto b
在将a搬到b上之前，先将a和b上积木放回本来位置（例如：1就放回1最开始位罝）
· move a over b
在将a搬到b所在那堆积木之上之前，先将a上积木放回本来位罝（b所在那堆积木不动）
· pile a onto b
将a自身和其上积木一起放到b上，在搬之前b上方积木放回原位
· pile a over b
将a自身和其上积木一起搬到到b所在那堆积木之上
· quit
动作结束
· 前四个动作中若a=b，或者a，b在同一堆积木中，那么这样动作算是不合法。所有不合法动作应当被忽视，也就是对各积木均无变化。
Input输入具有多组测试资料，每组测试资料第一列有一种正整数n（0 < n < 25），代表积木数目（编号从0到n-1）。接下来为机器手臂动作，每个动作一列。如果此动作为 quit ，代表此组测试资料输入结束。你可以假设所有动作都符合上述样式。请参照Sample Input。
Output每组测试资料输出桌面上各位置积木情形（每个位置一列，也就是共有n列），格式请参照Sample Output。
Sample Input10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
4
pile 0 over 1
pile 2 over 3
move 1 onto 3
quit
Sample Output
0：0
1：1 9 2 4
2:
3：3
4:
5：5 8 7 6
6:
7:
8:
9:
0：0
1:
2：2
3：3 1
（5）Q102：Ecological Bin Packing
有3个桶子用来装回收玻璃瓶，玻璃瓶颜色有三种：棕色（Brown）、绿色（Green）、透明色（Clear）。在这个问题里咱们会告诉你每个桶子里玻璃瓶颜色及数量，当前要搬移桶子里玻璃瓶使得最后每个桶子里都只有单一颜色玻璃瓶，以以便回收。你任务就是要算出最小搬移瓶子数。你可以假设每个桶子容量无限大，并且总共搬移瓶子数不会超过231。
Input每笔测试资料一行，每行有9个整数.前3个代表第1个桶子里Brown，Green，Clear颜色瓶子数。接下来3个数代表 第2个桶子里Brown，Green，Clear颜色瓶子数。最后3个数代表第3个桶子里Brown，Green，Clear颜色瓶子数。
例如：10 15 20 30 12 8 15 8 31 
表达有20个Clear色玻璃瓶在第1个桶子里，12个Green色玻璃瓶在第2个桶子里，15个Brown色玻璃瓶在第3个桶子里。
Output对每一笔测试资料，输出3个桶子内最后存储之玻璃瓶颜色，以及最小搬移瓶子数。请以大写'G'、'B'、'C' 分别代表绿色（Green）、棕色（Brown）、透明色（Clear）。
例如：BCG 30
代表最后搬移成果第1个桶子内玻璃瓶颜色为Brown，第2个桶子内玻璃瓶颜色为Clear，第3个桶子内玻璃瓶颜色为Green.并且总共搬移了30个玻璃瓶。
如果最小搬移瓶子数有一组以上组合，请输出字典顺序最小那一组答案。
Sample input
1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10
Sample Output
BCG 30
CBG 50
（6）Q103：Stacking Boxes
在数学或电脑科学里，有些概念在一维或二维时还蛮简朴，但到 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 < k） 考虑两个盒子 D =（ d1，d2，......,dn ）， E =（ e1，e2，......,en ）。如果盒子 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) < ei，则咱们说盒子 D 能“放入”盒子 E 。
Input输入包括多组测试资料。每组测试资料第一列有两个数字：第一种是盒子数量 k ，然后是盒子维数 n ； 接下来有 k 列，每列有n个整数表达一种盒子 n 个维量度，量度之间由一种以上空白做区隔。第一列表达第一种盒子，第二列表达第二个盒子，依此类推； 此问题里，盒子维数最小是 1 ，最大是 10 ， 并且每组测试资料中盒子个数最多为 30 个。
Output对于每一组测试资料，你必要输出两列数字：第一列是“最长套入串列”长度，第二列是按照内外顺序，印出“最长套入串列”里盒子编号（其中编号是按照在输入档案每组数列里所浮现顺序，例如第一种盒子就是 1 号 . . . 等等。）最里面盒子（或是最小）摆在第一种，再来是次小，依此类推； 如果对于每一组盒子，存在两个以上“最长套入串列”，输出任何一种均可。
Sample Input
5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
Sample Output
5
3 1 2 4 5
4
7 2 5 6
（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种外币各多少元。请参照Sample Input。
Output：对每组测试资料输出一列，代表一连串币种转换动作，并且套汇获利需不不大于 1%（ > 0.01）。如果有不止一种转换可以获取超过 1%利益，请输出转换次数至少。如果转换次数至少不止一种，那么任何一种都可以。请注意：在这里只规定转换次数至少，并没有规定获利要最大，只要能不不大于 1% 就可以了。
此外，国税局还规定最多只能转换 n 次（n 是币种数目）。像 1，2，1 这样转换次数为 2。 如果在 n 次转换内都无法获利超过 1%，请输出 no arbitrage sequence exists。
Sample Input
Sample Output
3
1.2 .89
.88 5.1
1.1 0.15
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111
2
2.0
0.45
1 2 1
1 2 4 1
no arbitrage sequence exists

（8）Q105：The Skyline Problem
由于高速绘图电脑工作站浮现，CAD（computer-aided design）和其她领域（CAM,VLSI设计）都充分使用这些电脑长处。而在本问题中，你必要协助建筑师，依照她所提供应你都市中建筑物位置，你得帮她找出这些建筑物空中轮廓（skyline）。为了使问题容易解决某些，所有建筑物都是矩形，并且都建筑在同一种平面上。你可以把这都市当作一种二度平面空间。每一栋建筑物都以(Li Hi Ri)这样序列来表达。其中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。
Sample Input
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
Sample Output
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
（9）Q107：The Cat in the Hat
一只神奇聪颖猫走进了一间乱七八糟房间，她不想自己动手收拾，她决定要找帮手来工作。于是她从她帽子中变出了N只小猫来帮她（变出来猫，高度为本来猫 1/(N+1) ）。这些小猫也有帽子，因此每一只小猫又从她帽子中变出N只小小猫来帮她。如此始终下去，直到这些小小小....猫小到不能再小（高度＝1），她们帽子无法再变出更小猫来帮忙，而这些最小猫只得动手打扫房间。注意：所有猫高度都是正整数。在这个问题中，给你一开始那只猫高度，以及最后动手工作猫数目（也就是高度为1猫数目）。要请你求出有多少只猫是没有在工作，以及所有猫高度总和。
Input每组测试资料一列，有2个正整数分别代表一开始那只猫高度，以及最后动手工作猫数目。0 0代表输入结束。
Output每组测试资料输出一列，包括2个正整数分别代表有多少只猫是没有在工作，以及所有猫高度总和。
Sample Input
216 125
5764801 1679616
64 1
0 0
Sample Output
31 671
335923 30275911
6 127
（10）Q108：Maximum Sum
给你一种NxN阵列，请你找出有最大和子区域（sub-rectangle）其和为多少。一种区域和指是该区域中所有元素值和。一种区域是指相连任意大小子阵列。例如，对如下二维阵列：

其最大和子区域位于左下角，并且其和为15。如下所示：

Input只有一组测试资料，第一列有一种正整数N（N <= 100），代表此二维阵列大小为NxN。从第二列起有N2个整数，代表此阵列内容。每个整数都介于-127到127之间，且以列为主（row-major）顺序排列。Sample Input即为上图所示阵列。
Output输出有最大和子区域其和是多少。
Sample Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
Sample Output
15
（11）Q111：History Grading
在资讯科学中有某些是关于在某些条件限制下，找出某些计算最大值。以历史考试来说好了，学生被规定对某些历史事件依照其发生年代顺序来排列。所有事件顺序都对的学生无疑可以得满分。但是那些没有全对人又该如何给分呢？如下有2种也许给分方式：每个与原则答案顺序相似事件得1分 1。每个在最长（但不一定要持续）序列事件中，其相对顺序亦可以在原则答案发现者，每个事件得1分。
举例阐明：如果有4个事件其发生时间顺序依次是1 2 3 4（就是原则答案啦，意思是第1个事件发生顺序为1，第2个事件发生顺序为2，......）。因此如果学生回答此4个事件发生顺序依次是1 3 2 4话，依照上面第1种办法可以得2分（第1个及第4个事件）。但是如果以上面第2种办法可以得3分（1 2 4或者1 3 4其相对顺序可以在原则答案发现）在本问题中，请你写一种程式以第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对每一学生答案，输出其所得分数。
Sample Input
10
3 1 2 4 9 5 10 6 8 7
1 2 3 4 5 6 7 8 9 10
4 7 2 3 10 6 9 1 5 8
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6
Sample Output6 5 10 9

（12）Q112：Tree Summing
LISP是最早高阶程式语言之一，而Lists则是LISP中最重要资料构造。Lists可以很简朴用来表达其她资料构造，例如：tree。在这个问题中，给你LISP中S表达式（S-expression），请你写一种程式判断这表达式（整数二元树）与否存在一条由根节点到树叶途径，且途径上各节点值和为某一特定数 n。例如：在如下树中共有4条从根到树叶途径。而各途径和分别为27,22,26以及18。

在LISP中S表达式有如下格式empty tree ::= () ；tree ::= empty tree | (integer tree tree)
上图中树若以S表达式表达为：(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )注意：在树中所有叶节点为 (integer () () )既然空树不存在任何根到叶途径，任何对空树与否有某个和询问，其答案都与否定。
Input输入具有多组测试资料。每组测试资料开头有一种整数 n。接下来为一S表达式。所有S表达式一定是合法，但是也许会跨多列，并且也许具有空白字元。请参照Sample Input。
Output对每一组测试资料输出一列。如果S表达式所表达树存在一条由根到叶途径，且途径上节点值和为n话，则输出yes，否则输出no。
Sample Input
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 ()
Sample Output
Yes yes
No no
Q113：Power of Cryptography
给你两个整数 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。
Sample Input
2
16
3
27
7

Sample Output
4
3
1234
Q115：Climbing Trees
原翻译者：untitled
这个问题目地在讨论两个人在所谓“家庭树”（family tree 即族谱）里，她们关系为什么。给你两组名字：第一组里有若干对名字，就是所谓“孩子，家长 对”（child-parent pairs），也就是一对名字，前面名字是孩子名字，而背面名字为其家长名字；第二组则也有若干对名字，是“欲查询 对”（query pairs），其表达格式跟前面“孩子，家长 对”同样有两个名字。给你这两组若干对名字，你必要写个程式来判断在“欲查询 对”里，每对那两个人彼此关系为什么。在这里咱们设定一种人只会有一种家长（虽然咱们都懂得每个人均有父、妈妈两者，但是在本问题中，咱们仅以其中一人代表）
在此问题里，咱们说“孩子，家长 对”p、q 表达 p 是 q 孩子。咱们为了要表达出所谓关系，咱们先看下面定义：
· 当在输入档案“孩子，家长 对”里有 p q （或者 q p），咱们说 p 是 q 0 级子孙 （或者 0 级祖先）
· 当在输入档案“孩子，家长 对”里有 p r （或者 q r），并且 r 是 q (k-1) 级子孙（或者 p 是 r (k-1) 级祖先），则称 p 是 q k 级子孙 （或者 k 级祖先）
在这个问题里，任两个人 p ，q 之间关系一定可归类到下列四种其中之一（如果她们关于系话）
1. 直系子孙类（child）： child、grand child、great grand child、great great grand child，依此类推。（即：孩子、孙子、曾孙、曾曾孙 ...）
依照定义，当输入档案里“孩子，家长 对”有 p q 存在（也就是 p 是 q 0 级子孙），则这时 p 是 q “child”─即是“孩子”；而当 p 是 q 1 级子孙时，咱们就称 p 是 q “grand child”─即是“孙子”；当 p 是 q (n+1) 级子孙，则 p 是 q “great great ... great grand child”，其中有 n 个 " great "，然后背面接 " grand child "，也就是“曾曾...曾孙”意思（其中有 p 个 " 曾 " ）。

2. 直系长辈类（parent）： parent、grand parent、great grand parent、great great grand parent，依此类推。（即：父（母）、祖父（母）、曾祖父（母）、曾曾祖父（母））
（注意：无论是男是女，每一种人如果有家长，则必然是恰有一种）
依照定义，当输入档案里“孩子，家长 对”有 q p 存在（也就是 p 是 q 0 级祖先），则这时 p 是 q “parent”─即是“父（母）”；而当 p 是 q 1 级祖先时，咱们就称 p 是 q “grand parent”─即是“祖父（母）”；当 p 是 q (n+1) 级祖先，则 p 是 q “great great ... great grand parent”，其中有 n 个 " great "，然后背面接 " grand parent "，也就是“曾曾...曾祖父（母）”意思（其中有 p 个 " 曾 " ）。

3. 旁系血亲类（就是非直系远亲）（ cousin ）：
依两个人对其同祖先辈分差距，可分为 0th cousin、1st cousin、2nd cousin，依此类推；对于两个人彼此辈分差距又可分为 once removed、twice removed、three times removed，依此类推。（ removed 有类似亲等远近关系之意）
依照定义，只要 p 和 q 有血缘关系，并且她们不是直系血亲关系，那她们就是旁系血亲关系。（或者也可以这样讲，如果把 family tree 当作是一种无向图，则存在一条途径连通 p 与 q）今天将 p 和 q 共同祖先里，辈份最小称作 r （也就是 r 子孙里没有人既是 p 祖先，又是 q 祖先。），然后懂得 p 是 r m 级子孙， q 是 r n 级子孙。 则咱们这样定义：p 和 q 关系有 '' kth cousins ''，其中 k=min(n,m)（也就是 k 是 p ，q 里面较小那一种）；并且 p 和 q 关系尚有 '' cousins removed j times '' ，其中 j=| n-m|（也就是 j 为 n 和 m 差绝对值。）
4. 兄弟姊妹类（sibling）： 0th cousins removed 0 times 就是所谓“兄弟姊妹”。（也就是她们有同一种家长）
Input输入涉及2个某些：第一部某些为“孩子，家长 对”，每对一列。包括孩子和家长名字，名字由小写字母及.构成。若遇到孩子名字为 no.child 代表这某些输入结束。注意 ，" no.child " 开头这一对名字自身并不算在“孩子，家长 对”里，它作用只是拿来分隔“孩子，家长 对”和“欲查询对”而已。此外，这某些输入也不会具有循环矛盾关系，也就是不会有人既是另一人子孙又是其祖先。 接著就是“欲查询对”，其格式与第一组同样，都是每列两个名字，由小写字母或句号构成，中间用一种以上空白隔开。而“欲查询对”是以 end-of-file 作结尾。 在输入中，不同名字不会超过 300 个。每个名字皆不超过 31 个字母长。“欲查询对”里最多不会超过 100 对名字。请参照Sample Input。
Output对于查询对里每对名字 p q，都必要输出 p 是 q什么关系──用下面格式：
· child，grand child，great grand child，great great ...great grand child
· parent，grand parent，great grand parent，great great ...great grand parent
· sibling
· n cousin removed m
· no relation
其中第四项，如果是 " n-cousin is removed 0 times " 则只需输出 n cousin 即可。也就是说不能输出 removed 0 这个东西。此外，不要在数字背面加上 st，nd，rd，th 等字样。请参照Sample Output。
Sample Input
alonzo.church oswald.veblen
stephen.kleene alonzo.church
dana.scott alonzo.church
martin.davis alonzo.church
pat.fischer hartley.rogers
mike.paterson david.park
dennis.ritchie pat.fischer
hartley.rogers alonzo.church
les.valiant mike.paterson
bob.constable stephen.kleene
david.park hartley.rogers
no.child no.parent
stephen.kleene bob.constable
hartley.rogers stephen.kleene
les.valiant alonzo.church
les.valiant dennis.ritchie
dennis.ritchie les.valiant
pat.fischer michael.rabin
mike.paterson dennis.ritchie
Sample Output
parent
sibling
great great grand child
1 cousin removed 1
1 cousin removed 1
no relation
1 cousin
Q116：Unidirectional TSP
给你一种由整数构成 m*n 方阵，你必要要写个程式，来计算出“重量”（ weight ） 最小路线。每条路线都是从第始终行任何一格做为起点，走了若干步之后，至第 n 行（最后一行）其中一格为终点。所谓一步就是从第 i 行走至第 i+1 行，其中移动时候只能走到原本或是相邻一横列（也就是走平或是斜一格）。此外要注意是，第一横列和最后一横列（第 m 列）也算是相邻，也可以这样想，就是整个方阵是上下“包”起来，看起来像一种倒著圆柱体。总之，对于任何一格可以走下一步就如下图所示：

所谓一种途径“重量”（weight）就是此途径通过 n 个格子里，它们整数总和。举个例子，下面有两个不同5*6 方阵。（事实上你可以注意到它们不同只在最后一列而已）

这两个方阵“最小重量途径”（ minimal-weight path ）已经在上面分别标出来了。注意一下右边方阵，其运用了第一列和最后一列是相邻这个性质达到了最小重量。
Input输入里包括多组测试资料，每组代表一种方阵。每组测试资料第一列为2个正整数 m 与 n （1 <= m <=10，1 <= n <= 100），依序表达这方阵有几横列和几直行。而后就是 m*n 个整数，这些整数是按照“列顺序”（ row major order ）来排列，也就是输入里前 n 个数表达方阵第一横列，再下来 n 个数表达第二横列，依此类推。在输入里，同一列数彼此间将会被一种以上空白隔开。值得注意是，这里说整数并不一定是正。输入以及计算过程所浮现数均不会超过长整数（long）范畴。 Sample Input中前2组测试资料所表达方阵就是上方2个图，请参照。
Output对于每个方阵，你必要输出两列东西。第一列是“最小重量途径”（ minimal-weight path ），第二列则是其“重量”。对于第一列，你必要输出 n 个正整数，依序表达在每一行，此途径通过了第几列。如果存在两个以上途径其“重量”皆为最小，则输出按照字典顺序（ lexicographically ）最小那一种途径。请参照Sample Output。
Sample Input
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10 9 10
Sample Output
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19

Q127："Accordian" Patience
你任务是模仿一种叫“Accordian”纸牌游戏，她游戏规则如下：一副扑克牌有52张牌，一方面把纸牌一张一张由左到右排好（不能有重叠，因此共有52堆牌，每堆一张），当某一张牌与她左边那张牌或者左边第三张牌有“Match”时候，就把这张牌移到那张牌上面去。在这里两张牌“Match”指是这两张牌花色（suit）或者点数（rank）同样。当你做了一种移动之后，要察看与否还可以做其她移动。在任何时间，只有最上面那张牌可以被移动。如果由于移动一张牌使得产生一种空格（也就是被移动那堆牌只有一张牌），你必要把右边所有牌堆往左移一格。如此不断寻找可移动牌，直到没有一张牌可以移动游戏就结束了。 在选取可以移动牌时候也许有些状况会发生。如果有两张牌都可以移动，你应当要移动最左边那张牌。当一张牌可以被移动到左边一格，或左边三格时候，你必要移动到左边三格。
Input输入包括多组测试资料。每组测试资料两列，每列有26张牌资料。每张牌以2个字元代表。第一种字元代表牌点数（A=Ace，2~9，T=10，J=Jack，Q=Queen，K=King），第二个字元代表牌花色（C=Clubs，D=Diamonds，H=Hearts，S=Spades）若遇到仅含#一列代表输入结束。请参照Sample Input。
Output对每组测试资料输出游戏结束时剩余几堆牌，以及每堆牌有多少张牌。请注意如果只有1堆牌，pile后没有加s，请参照Sample Output。
Sample input
QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C 6S
8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C 5C
AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD KD
AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS KS
#
Sample Output
6 piles remaining：40 8 1 1 1 1
1 pile remaining：52
Q128：Software CRC
你在一家有诸各种人电脑公司上班。你老板，连一分都省博士，想要把这些个人电脑连线，但是她又不想要花钱买网路卡。由于你不小心告诉老板每台电脑出厂时就有一种非同步串列埠在上面，老板固然把脑筋动到这不用花钱解决方案上。于是可怜你被指派来完毕这工作软体需求，以使这些电脑之间可以连线。
你已经读了许多关于通讯书并且懂得在传送及接受讯息时，保证讯息对的性是一种重点。典型作法是在讯息最后加上额外错误检查码。这个资讯容许接受程式检查出传送资讯与否有错误（在大多数例子）。于是，你跑到图书馆借回了一本关于通讯厚厚书，运用周末（固然没有加班费）研究错误检查某些。
最后，你决定CRC（cyclic redundancy check）是最适合错误检查方式。如下描述这个机制：
CRC Generation
待传递讯息被视为一列长长二元数。讯息第一种位元组（byte）被当作这二元数最重要位元组，第二个位元组被当作第二重要位元组