全國大學(xué)生程序設(shè)計競賽訓(xùn)練題

程序設(shè)計大賽訓(xùn)練題」Q）請寫一個程式求出2個數(shù)的GCD（最大公因數(shù)加InputandOutpul+J輸入包含好幾筆資料,每筆資料一行，包含2個整數(shù)即b口（Q<a:b<10DQQ000）^00代表輸入結(jié)束。/對每行輸入，輸出這2個數(shù)的GCDuSampleInpw112如'252400SampleOuipuTuGCD（1Z先）=1.%GCD（25:24>1）/⑵聯(lián)集讀入2個正整數(shù)a,b,請輸出介于a,b之間（包含a,b）2,3,5倍數(shù)的聯(lián)集大小。Input（輸入可能包含了好幾列測試資料，每一列有2個整數(shù)a,b。a=0b=0代表輸入結(jié)束。）Output（對每一列輸入，請輸出聯(lián)集的大小。請參考SampleOutput）SampleInput（110；1020；00；）SampleOutput（8；7）Q100:The3n+1problem考慮以下的演算法：輸入n印出n如果n=1結(jié)束如果n是奇數(shù)那么n=3*n+1否則 n=n/2GOTO 2例如輸入22,得到的數(shù)列：221134175226134020105168421據(jù)推測此演算法對任何整數(shù)而言會終止（當(dāng)列印出1的時候）。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的n（0<n<1,000,000）來說，以上的推測已經(jīng)被驗證是正確的。給一個輸入n,透過以上的演算法我們可以得到一個數(shù)列（1作為結(jié)尾）。此數(shù)列的長度稱為n的cycle-length。上面提到的例子，22的cyclelength為16.問題來了：對任意2個整數(shù)i，j我們想要知道介于i，j（包含i，j）之間的數(shù)所產(chǎn)生的數(shù)列中最大的cyclelength是多少。Input:輸入可能包含了好幾列測試資料，每一列有一對整數(shù)資料i，j。 （0<i，j<10000）Output：對每一對輸入i,j你應(yīng)該要輸出i,j和介于i,j之間的數(shù)所產(chǎn)生的數(shù)列中最大的cyclelength。SampleInput：110；101；100200；201210；9001000；SampleOutput1102010120100200125201210899001000174Q101:TheBlocksProblem在早期人工智慧的領(lǐng)域中常常會用到機器人，在這個問題中有一支機器手臂接受指令來搬動積木，而你的任務(wù)就是輸出最后積木的情形。一開始在一平坦的桌面上有n塊積木（編號從0到n-1）0號積木放在0號位置上，1號積木放在1號位置上，依此類推，如下圖。0 1 2 3 4 …上1 _ I I機器手臂有以下幾種合法搬積木的方式（a和b是積木的編號）：moveaontob在將a搬到b上之前，先將a和b上的積木放回原來的位置（例如：1就放回1的最開始位置）moveaoverb在將a搬到b所在的那堆積木之上之前，先將a上的積木放回原來的位置（b所在的那堆積木不動）pileaontob將a本身和其上的積木一起放到b上，在搬之前b上方的積木放回原位pileaoverb將a本身和其上的積木一起搬到到b所在的那堆積木之上quit動作結(jié)束?前四個動作中若@=，或者a,b在同一堆積木中，那么這樣的動作算是不合法的。所有不合法的動作應(yīng)該被忽略，也就是對各積木均無改變。Input輸入含有多組測試資料，每組測試資料的第一列有一個正整數(shù)n（0<n<25），代表積木的數(shù)目（編號從0到n-1）。接下來為機器手臂的動作，每個動作一列。如果此動作為quit，代表此組測試資料輸入結(jié)束。你可以假設(shè)所有的動作都符合上述的樣式。請參考SampleInput。Output每組測試資料輸出桌面上各位置積木的情形（每個位置一列，也就是共有n列），格式請參考SampleOutput。SampleInput10move9onto1move8over1move7over1move6over1pile8over6pile8over5move2over1move4over9quit4pile0over1pile2over3move1onto3quitSampleOutput0:01924358760:0231Q102:EcologicalBinPacking有3個桶子用來裝回收的玻璃瓶，玻璃瓶的顏色有三種：棕色（Brown）、綠色（Green）、透明色（Clear）。在這個問題里我們會告訴你每個桶子里的玻璃瓶的顏色及數(shù)量，現(xiàn)在要搬移桶子里的玻璃瓶使得最后每個桶子里都只有單一顏色的玻璃瓶，以方便回收。你的任務(wù)就是要算出最小搬移的瓶子數(shù)。你可以假設(shè)每個桶子的容量無限大，并且總共搬移的瓶子數(shù)不會超過23。Input每筆測試資料一行，每行有9個整數(shù).前3個代表第1個桶子里Brown,Green,Clear顏色的瓶子數(shù)。接下來的3個數(shù)代表第2個桶子里Brown,Green,Clear顏色的瓶子數(shù)。最后的3個數(shù)代表第3個桶子里Brown,Green,Clear顏色的瓶子數(shù)。例如：1015203012815831表示有20個Clear色的玻璃瓶在第1個桶子里，12個Green色的玻璃瓶在第2個桶子里，15個Brown色的玻璃瓶在第3個桶子里。Output對每一筆測試資料，輸出3個桶子內(nèi)最后存放之玻璃瓶顏色，以及最小搬移的瓶子數(shù)。請以大寫的'G'、’B'、'C'分別代表綠色（Green）、棕色（Brown）、透明色（Clear）。例如：BCG30代表最后搬移的結(jié)果第1個桶子內(nèi)的玻璃瓶顏色為Brown,第2個桶子內(nèi)的玻璃瓶顏色為Clear,第3個桶子內(nèi)的玻璃瓶顏色為Green.并且總共搬移了30個玻璃瓶。如果最小搬移瓶子數(shù)有一組以上的組合，請輸出字典順序最小的那一組答案。Sampleinput123456789510520105102010SampleOutputBCG30CBG50Q103:StackingBoxes在數(shù)學(xué)或電腦科學(xué)里，有些概念在一維或二維時還蠻簡單的，但到N維就會顯得非常復(fù)雜。試想一個n維的“盒子”：在二維空間里，盒子（2,3）可代表一個長為2個單位，寬為3個單位的盒子；在三維空間里，盒子(4,8,9)則是一個4*8*9(長、寬、高)的盒子。至于在六維空間里，也許我們不清楚(4,5,6,7,8,9)長得怎樣，不過我們還是可以分析這些盒子的特性。在此問題里，我們要算出一組n維盒子里，它們的“最長套入串列”：b,%,bk，其中每個盒子bi都可以“放入”盒子bi+1中(1<=i1<k)考慮兩個盒子D=(d,d, ,d)，E=(e,e, ,e)。如果盒子D的n個維，能夠存在一種重排，使得重排后；D每一維的量度都比E中相對應(yīng)的維的量度還要小，則我們說盒子D能“放入”盒子E。(用比較不嚴(yán)謹(jǐn)?shù)闹v法，這就好像我們將盒子D翻來翻去，看看能不能擺到E里面去。不過因為我們考慮的是任一重排，所以實際上盒子不只可轉(zhuǎn)來轉(zhuǎn)去，甚至還可以扭曲。)(還是看看下面的例子說明好了)。譬如說，盒子D=(2,6)能夠被放入盒子E=(7,3)里，因為D可以重排變?yōu)?6,2)，這樣子D的每個維的量度都比E里對應(yīng)的維還要小。而盒子D=(9,5,7,3)就沒辦法放進盒子E=(2,10,6,8),因為就算再怎摸重排D里的維，還是沒辦法符合“放入”的條件。不過F=(9,5,7,1)就可以放入E了，因為F可以重排成(1,9,5,7)，這樣就符合了放入的條件。我們今定義“放入”如下：對于任兩個盒子D=(d,d, ,d)和E=(e,e, ,e)，如果存在一種1..n的重排、：使得對于任何的1<二i<=1n「皆有d〃i)%ei,則我們說盒子D能“放入”盒子E。Input輸入包含多組測試資料。每組測試資料的第一列有兩個數(shù)字：第一個是盒子的數(shù)量k,然后是盒子的維數(shù)n；接下來有k歹列，每列有n個整數(shù)表示一個盒子的n個維的量度，量度之間由一個以上的空白做區(qū)隔。第一列表示第一個盒子，第二列表示第二個盒子，依此類推；此問題里，盒子的維數(shù)最小是1,最大是10,并且每組測試資料中盒子的個數(shù)最多為30個。Output對于每一組測試資料，你必須輸出兩列數(shù)字：第一列是“最長套入串列”的長度，第二列是按照內(nèi)外順序，印出“最長套入串列”里盒子的編號(其中編號是按照在輸入檔案的每組數(shù)列里所出現(xiàn)的順序，例如第一個盒子就是1號...等等。)最里面的盒子(或是最小的)擺在第一個，再來是次小的，依此類推； 如果對于每一組的盒子，存在兩個以上的“最長套入串列”，輸出任何一個均可。SampleInput5237810529112118865220130102315791134050342414491011121314314188271744321319411912345680374718219SampleOutput53124547256Q104:Arbitrage所謂的“三角套匯（arbitrage）”就是在幾種外幣中做金錢的交易，期待從匯差中獲取少許的利潤。例如：1元美金可以買0.7英鎊，1元英鎊可以買9.5法朗，1元法朗可以買0.16美金。所以如果我們把1元美金換成英鎊，再把英鎊換成法朗，最后再把法朗換回美金，那么最后得到的美金將是：1*0.7*9.5*0.16=1.064美元。也就是說我們可以從中獲取匯差0.064美元，相當(dāng)于賺了6.4%。請你寫一個程式找出是否有這樣套匯的情況，可以獲取如上所述的利益。要產(chǎn)生一個成功的套匯，在換外幣的過程中，開始的幣種一定得等于最后的幣種。但是從哪一種開始都可以。Input輸入含有多組測試資料。每組測試資料的第一列，有一個整數(shù)n（2<=n<=20），代表共有多少種幣種。接下來的n列代表這n種外幣之間的匯率轉(zhuǎn)換然每列有n-1個數(shù)。這n-1個數(shù)分別代表該幣種1元可以換取其他幣種多少元（自己換自己當(dāng)然是1，所以不會出現(xiàn)）。所以第1列的n-1個數(shù)依序分別代表第1種外幣1元可以換取，第2種夕卜幣，第3種夕卜幣，第4種外幣...第n種外幣各多少元。而第2列的n-1個數(shù)依序分別代表第2種外幣1元可以換取，第1種外幣，第3種外幣，第4種外幣.??第n種外幣各多少元。依此類推，第n列的n-1個數(shù)依序分別代表第n種外幣1元可以換取，第1種外幣，第2種外幣，第3種外幣.一第n-1種外幣各多少元。請參考SampleInput。Output：對每組測試資料輸出一列，代表一連串幣種轉(zhuǎn)換的動作，并且套匯獲利需大于1%(>0.01)。如果有不止一種轉(zhuǎn)換可以獲取超過1%的利益，請輸出轉(zhuǎn)換次數(shù)最少的。如果轉(zhuǎn)換次數(shù)最少的不止一種，那么任何一種都可以。請注意:在這里只要求轉(zhuǎn)換次數(shù)最少，并沒有要求獲利要最大，只要能大于1%就可以了。另外，國稅局還規(guī)定最多只能轉(zhuǎn)換n次(n是幣種的數(shù)目)。像1,2,1這樣的轉(zhuǎn)換次數(shù)為2。 如果在n次的轉(zhuǎn)換內(nèi)都無法獲利超過1%，請輸出noarbitragesequenceexists。SampleInputSampleOutput31.2.89.885.11.10.1543.1 0.0023 0.350.21 0.00353 8.13200 180.559 10.3392.11 0.089 0.0611122.00.451211241noarbitragesequenceexists（8）Q105:TheSkylineProblem由于高速繪圖電腦工作站的出現(xiàn)，CAD(computer-aideddesign)和其他領(lǐng)域(CAM,VLSI設(shè)計)都充分使用這些電腦的長處。而在本問題中，你必須幫助建筑師，根據(jù)他所提供給你都市中建筑物的位置，你得幫他找出這些建筑物的空中輪廓(skyline)。為了使問題容易處理一些，所有的建筑物都是矩形的，并且都建筑在同一個平面上。你可以把這城市看成一個二度平面空間。每一棟建筑物都以(LHR)這樣的序列來表示。其中L和R分別是該建筑物左邊和右邊的位置，H則是建筑物的高度。下方左圖就是(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)這八棟建筑物的位置圖。而你的任務(wù)就是畫出這些建筑物所構(gòu)成的輪廓，并且以(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)這樣的序列來表示如下方右圖的輪廓。0：j10 -5如潮30 0 5 0 15漪95 30Input只有一組測試資料。每列有一棟建筑物的資料。建筑物不會超過50棟。所有的數(shù)字都小于10000。并且建筑物已按照“排好序。Output輸出為描述建筑物輪廓的向量。在輪廓向量（v,v,v, ,v,v）中，在i為奇數(shù)的情形下，v表示一條垂直線（X座標(biāo)）「茬i為偶數(shù)的情形下，v表示一條水平線（高度）i。輪廓向量就像一只蟲從最左邊建筑物走起，沿著輪廓路徑水平及垂直的行走的路徑。所以最后輪廓向量的最后一個數(shù)一定為0。SampleInput11567139127161432519182223132924428SampleOutput1113139012716319182232313290Q107:TheCatintheHat一只神奇聰明貓走進了一間亂七八糟的房間，他不想自己動手收拾，他決定要找?guī)褪謥砉ぷ?。于是他從他的帽子中變出了N只小貓來幫他（變出來的貓，高度為原來貓的1/（N+1））。這些小貓也有帽子，所以每一只小貓又從他的帽子中變出N只小小貓來幫他。如此一直下去，直到這些小小小....貓小到不能再?。ǜ叨?1）,他們的帽子無法再變出更小的貓來幫忙，而這些最小的貓只得動手打掃房間。注意：所有貓的高度都是正整數(shù)。在這個問題中，給你一開始那只貓的高度，以及最后動手工作的貓的數(shù)目（也就是高度為1的貓的數(shù)目）。要請你求出有多少只貓是沒有在工作的，以及所有貓的高度的總和。Input每組測試資料一列，有2個正整數(shù)分別代表一開始那只貓的高度，以及最后動手工作的貓的數(shù)目。00代表輸入結(jié)束。Output每組測試資料輸出一列，包含2個正整數(shù)分別代表有多少只貓是沒有在工作的，以及所有貓的高度的總和。SampleInput2161255764801167961664100SampleOutput31671335923302759116127Q108:MaximumSum給你一個NxN的陣列，請你找出有最大和的子區(qū)域(sub-rectangle)其和為多少。一個區(qū)域的和指的是該區(qū)域中所有元素值的和。一個區(qū)域是指相連的任意大小的子陣列。例如，對以下的二維陣列：TOC\o"1-5"\h\z0-2-7 09 2-62—4 1—4 1-18 0-2其最大和的子區(qū)域位于左下角，并且其和為15。如下所示:92-41—18Input只有一組測試資料，第一列有一個正整數(shù)N(N<=100)，代表此二維陣列大小為NxN。從第二列起有N2個整數(shù)，代表此陣列的內(nèi)容。每個整數(shù)都介于-127到127之間，且以列為主(row-major)的順序排列。SampleInput即為上圖所示的陣列。Output輸出有最大和的子區(qū)域其和是多少。SampleInput40-2-7092-62—41-41-180-2SampleOutput15Q111:HistoryGrading在資訊科學(xué)中有一些是關(guān)于在某些條件限制下，找出一些計算的最大值。以歷史考試來說好了，學(xué)生被要求對一些歷史事件根據(jù)其發(fā)生的年代順序來排列。所有事件順序都正確的學(xué)生無疑的可以得滿分。但是那些沒有全對的人又該如何給分呢？以下有2種可能的給分方式：每個與標(biāo)準(zhǔn)答案的順序相同的事件得1分1。每個在最長（但不一定要連續(xù)）的序列事件中，其相對的順序亦可以在標(biāo)準(zhǔn)答案發(fā)現(xiàn)者，每個事件得1分。舉例說明：如果有4個事件其發(fā)生時間的順序依次是1234（就是標(biāo)準(zhǔn)答案啦，意思是第1個事件發(fā)生順序為1，第2個事件發(fā)生的順序為2,）。所以如果學(xué)生回答此4個事件發(fā)生的順序依次是1324的話，根據(jù)上面第1種方法可以得2分（第1個及第4個事件）。但是如果以上面第2種方法可以得3分（124或者134其相對的順序可以在標(biāo)準(zhǔn)答案發(fā)現(xiàn)）在本問題中，請你寫一個程式以第2個方法算出學(xué)生該得多少分。Input只考一次試，所以輸入的第1列有一個整數(shù)n（2<=n<=20）代表此次歷史考試有多少個事件要排序。第2列為標(biāo)準(zhǔn)答案，有n個正整數(shù)c,c,c，（其內(nèi)容為1到n的某種排列），c代表第1個事件發(fā)生的順序，I代表第2個事件發(fā)生的順序，依此類推。從第3列開始每列為一學(xué)生的答案；每列有n個正整數(shù)r,r, r，（其內(nèi)容亦為1到n的某種排列），r代表學(xué)生回答第1個事件發(fā)生的順序：r代表學(xué)生回答第2個事件發(fā)生的順序1依此類推。2Output對每一學(xué)生的答案，輸出其所得的分?jǐn)?shù)。SampleInput10TOC\o"1-5"\h\z31 2 4 9 5 10 6 8 712 3 4 5 6 7891047 2 3 1069 1 5 831 2 4 9 5 10 6 8 721013849576SampleOutput65109Q112:TreeSummingLISP是最早的高階程式語言之一，而Lists則是LISP中最重要的資料結(jié)構(gòu)。Lists可以很簡單的用來表達其他的資料結(jié)構(gòu)，例如：tree。在這個問題中，給你LISP中的S表示式(S-expression)，請你寫一個程式判斷這表示式(整數(shù)的二元樹)是否存在一條由根節(jié)點到樹葉的路徑，且路徑上各節(jié)點的值的和為某一特定的數(shù)n。例如：在以下的樹中共有4條從根到樹葉的路徑。而各路徑的和分別為27,22,26以及18。在LISP中的S表示式有以下的格式emptytree::=() ；tree::=emptytree|(integertreetree)上圖中的樹若以S表示式表達為：(5(4(11(7()())(2()()))())(8(13()())(4()(1()())))注意：在樹中所有的葉節(jié)點為(integer()())既然空樹不存在任何根到葉的路徑，任何對空樹是否有某個和的詢問，其答案都是否定的。Input輸入含有多組測試資料。每組測試資料的開頭有一個整數(shù)n。接下來為一S表示式。所有的S表示式一定是合法的，但是可能會跨多列，并且可能含有空白字元。請參考SampleInput。Output對每一組測試資料輸出一列。如果S表示式所表達的樹存在一條由根到葉的路徑，且路徑上節(jié)點值的和為n的話，則輸出yes，否則輸出no。SampleInput22(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()YesNoSampleOutputYesNoyesnoQ113:PowerofCryptography給你兩個整數(shù)n（n>=1）和p（p>=1），你必須寫一個程式來計算出p的正n次方根。在這個問題里，p皆可表成kn的形式，其中k為整數(shù)。（k也就是你的程式所要求的）Input每組測試資料2歹列，第1列有1個整數(shù)n（1<=n<=200，第2列有1個整數(shù)p（1<=p<=101。1）。并且存在一個整數(shù)k,（1<=k<=109）,使得kn=p。Output每組測試資料請輸出k。SampleInput21632774357186184021382204544SampleOutput431234Q115:ClimbingTrees原翻譯者：untitled這個問題的目地在討論兩個人在所謂的“家庭樹”（familytree即族譜）里，他們的關(guān)系為何。給你兩組名字：第一組里有若干對名字，就是所謂的“孩子，家長對"（child-parentpairs）,也就是一對名字，前面的名字是孩子的名字，而后面的名字為其家長的名字；第二組則也有若干對名字，是“欲查詢對”（querypairs）,其表達格式跟前面的“孩子，家長對”一樣有兩個名字。給你這兩組若干對的名字，你必須寫個程式來判斷在“欲查詢對”里，每對的那兩個人彼此關(guān)系為何。在這里我們設(shè)定一個人只會有一個家長（雖然我們都知道每個人都有父、母親二者，但是在本問題中，我們僅以其中一人代表）在此問題里，我們說“孩子，家長對"p、q表示P是q的孩子。我們?yōu)榱艘硎境鏊^的關(guān)系，我們先看下面的定義：?當(dāng)在輸入檔案的“孩子，家長對”里有pq（或者qp），我們說P是q的0級子孫（或者0級祖先）?當(dāng)在輸入檔案的“孩子，家長對”里有pr（或者qr），而且r是q的（k-1）級子孫（或者p是r的（k-1）級祖先），則稱p是q的k級子孫（或者k級祖先）在這個問題里，任兩個人p,q之間的關(guān)系一定可歸類到下列四種的其中之一（如果他們有關(guān)系的話）.直系子孫類（child）：child、grandchild、greatgrandchild>greatgreatgrandchild，依此類推。（即：孩子、孫子、曾孫、曾曾孫...）根據(jù)定義，當(dāng)輸入檔案里的“孩子，家長對”有pq存在（也就是p是q的0級子孫），則這時p是q的“child”一即是“孩子”；而當(dāng)p是q的1級子孫時，我們就稱p是q的“grandchild”一即是“孫子”；當(dāng)p是q的（n+1）級子孫，則p是q的“greatgreat...greatgrandchild”，其中有n個"great”,然后后面接"grandchild〃，也就是“曾曾...曾孫”的意思（其中有p個〃曾〃）。.直系長輩類（parent）：parent、grandparent、greatgrandparent、greatgreatgrandparent，依此類推。（即：父（母）、祖父（母）、曾祖父（母）、曾曾祖父（母））（注意：無論是男是女，每一個人如果有家長，則必然是恰有一個）根據(jù)定義，當(dāng)輸入檔案里的“孩子，家長對”有qp存在（也就是p是q的0級祖先），則這時p是q的“parent”一即是“父（母）”；而當(dāng)p是q的1級祖先時，我們就稱p是q的“grandparent”一即是“祖父（母）"；當(dāng)p是q的（n+1）級祖先，則p是q的“greatgreat...greatgrandparent”，其中有n個〃great〃，然后后面接〃grandparent〃，也就是“曾曾...曾祖父（母）”的意思（其中有p個〃曾〃）。.旁系血親類（就是非直系的遠(yuǎn)親）（cousin）：依兩個人對其同祖先的輩分差距，可分為0thcousin、1stcousin、2ndcousin，依此類推；對于兩個人彼此的輩分差距又可分為onceremoved,twiceremoved.threetimesremoved,依此類推。（removed有類似親等遠(yuǎn)近關(guān)系之意）根據(jù)定義，只要P和q有血緣關(guān)系，而且他們不是直系血親關(guān)系，那他們就是旁系血親的關(guān)系。（或者也可以這樣講，如果把familytree當(dāng)作是一個無向圖，則存在一條路徑連通P與q）今天將P和q的共同祖先里，輩份最小的稱作r（也就是r的子孫里沒有人既是p的祖先，又是q的祖先。），然后知道P是r的m級子孫，q是r的n級子孫。 則我們這樣定義：P和q的關(guān)系有‘‘kthcousins'',其中k=min（n,m）（也就是k是p,q里面較小的那一個）；而且p和q的關(guān)系還有''cousinsremovedjtimes''，其中j=|n-m|（也就是j為n和m差的絕對值。）.兄弟姊妹類（sibling）：0thcousinsremoved0times就是所謂的“兄弟姊妹”。（也就是他們有同一個家長）Input輸入包括2個部分：第一部部分為“孩子，家長對”，每對一列。包含孩子和家長的名字，名字由小寫字母及.組成。若遇到孩子的名字為no.child代表這部分的輸入結(jié)束。注意，〃no.child"開頭的這一對名字本身并不算在“孩子，家長對”里，它的作用只是拿來分隔“孩子，家長對”和“欲查詢對”而己。另外，這部分的輸入也不會含有循環(huán)矛盾的關(guān)系，也就是不會有人既是另一人的子孫又是其祖先。 接著就是“欲查詢對”，其格式與第一組一樣，都是每列兩個名字，由小寫字母或句號組成，中間用一個以上的空白隔開。而“欲查詢對"是以end-of-file作結(jié)尾。在輸入中，不同的名字不會超過300個。每個名字皆不超過31個字母長?！坝樵儗Α崩镒疃嗖粫^100對名字。請參考SampleInput。Output對于查詢對里的每對名字pq,都必須輸出p是q的什么關(guān)系一用下面的格式：child,grandchild,greatgrandchild,greatgreat...greatgrandchildparent,grandparent,greatgrandparent,greatgreat...greatgrandparentsiblingncousinremovedmnorelation其中第四項，如果是〃n-cousinisremoved0times〃則只需輸出ncousin即可。也就是說不能輸出removed0這個東西。另外，不要在數(shù)字的后面加上st,nd,rd,th等字樣。請參考SampleOutput。SampleInputalonzo.churchoswald.veblenstephen.kleenealonzo.churchdana.scottalonzo.churchmartin.davisalonzo.churchpat.fischerhartley.rogersmike.patersondavid.parkdennis.ritchiepat.fischerhartley.rogersalonzo.churchles.valiantmike.patersonbob.constablestephen.kleenedavid.parkhartley.rogersno.childno.parentstephen.kleenebob.constablehartley.rogersstephen.kleeneles.valiantalonzo.churchles.valiantdennis.ritchiedennis.ritchieles.valiantpat.fischermichael.rabinmike.patersondennis.ritchieSampleOutputparentsiblinggreatgreatgrandchildcousinremoved1cousinremoved1norelationcousinQ116:UnidirectionalTSP給你一個由整數(shù)組成的m*n方陣，你必須要寫個程式，來計算出“重量”（weight）最小的路線。每條路線都是從第一直行的任何一格做為起點，走了若干步之后，至第n行（最后一行）的其中一格為終點。所謂的一步就是從第i行走至第i+1行，其中移動的時候只能走到原本的或是相鄰的一橫列（也就是走平的或是斜一格）。另外要注意的是，第一橫列和最后一橫列（第m歹列）也算是相鄰的，也可以這樣想，就是整個方陣是上下“包”起來的，看起來像一個倒著的圓柱體?？傊?，對于任何一格能夠走的下一步就如下圖所示：

所謂一個路徑的“重量”(weight)就是此路徑經(jīng)過的n個格子里，它們的整數(shù)總和。舉個例子，下面有兩個不同的5*6方陣。(實際上你可以注意到它們的不同只在最后一列而已)這兩個方陣的“最小重量路徑”(minimal-weightpath)已經(jīng)在上面分別標(biāo)出來了。注意一下右邊的方陣，其利用了第一列和最后一列是相鄰的這個性質(zhì)達到了最小的重量。Input輸入里包含多組測試資料，每組代表一個方陣。每組測試資料的第一列為2個正整數(shù)m與n(1<=m<=10，1<=n<=100)，依序表示這方陣有幾橫列和幾直行。而后就是m*n個整數(shù)，這些整數(shù)是按照“列順序”(rowmajororder)來排列，也就是輸入里的前n個數(shù)表示方陣的第一橫列，再下來的n個數(shù)表示第二橫列，依此類推。在輸入里，同一列的數(shù)彼此間將會被一個以上的空白隔開。值得注意的是，這里說的整數(shù)并不一定是正的。輸入以及計算的過程所出現(xiàn)的數(shù)均不會超過長整數(shù)(long)的范圍。SampleInput中前2組測試資料所表達的方陣就是上方的2個圖，請參考。Output對于每個方陣，你必須輸出兩列東西。第一列是“最小重量路徑”(minimal-weightpath)，第二列則是其“重量”。對于第一列，你必須輸出n個正整數(shù)，依序表示在每一行，此路徑經(jīng)過了第幾列。如果存在兩個以上的路徑其“重量”皆為最小，則輸出按照字典順序(lexicographically)最小的那一個路徑。請參考SampleOutput。SampleInput56341286618274593995841326372864563412866182745939958413263721232910910SampleOutput12344516121545111119Q127:"Accordian"Patience你的任務(wù)是模擬一種叫“Accordian”的紙牌游戲，他的游戲規(guī)則如下：一副撲克牌有52張牌，首先把紙牌一張一張由左到右排好（不能有重疊，所以共有52堆牌，每堆一張），當(dāng)某一張牌與他左邊那張牌或者左邊的第三張牌有“Match”的時候，就把這張牌移到那張牌上面去。在這里兩張牌“Match”指的是這兩張牌的花色（suit）或者點數(shù)（rank）一樣。當(dāng)你做了一個移動之后，要察看是否還可以做其他的移動。在任何時間，只有最上面那張牌可以被移動。如果因為移動一張牌使得產(chǎn)生一個空格（也就是被移動的那堆牌只有一張牌），你必須把右邊所有的牌堆往左移一格。如此不斷的尋找可移動的牌，直到?jīng)]有一張牌可以移動游戲就結(jié)束了。在選擇可以移動的牌的時候可能有些狀況會發(fā)生。如果有兩張牌都可以移動，你應(yīng)該要移動最左邊的那張牌。當(dāng)一張牌可以被移動到左邊一格，或左邊三格的時候，你必須移動到左邊三格。Input輸入包含多組測試資料。每組測試資料兩列，每列有26張牌的資料。每張牌以2個字元代表。第一個字元代表牌的點數(shù)（A=Ace,2?9,T=10,尸Jack,Q=Queen,1?？?），第二個字元代表牌的花色（C=Clubs,D=Diamonds,H=Hearts,S=Spades）若遇到僅含#的一列代表輸入結(jié)束。請參考SampleInput。Output對每組測試資料輸出游戲結(jié)束時剩下幾堆牌，以及每堆牌有多少張牌。請注意如果只有1堆牌，pi