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

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

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