acm編程比賽入門(mén)題目集

1、程序設(shè)計(jì)比賽試題主辦方:迅翔計(jì)算機(jī)協(xié)會(huì)最少錢(qián)幣數(shù)：【問(wèn)題描述】這是一個(gè)古老而又經(jīng)典的問(wèn)題。 用給定的幾種錢(qián)幣湊成某個(gè)錢(qián)數(shù)， 一般而言有多種方式。 例 如：給定了6種錢(qián)幣面值為2、5、10、20、50、100，用來(lái)湊15元，可以用5個(gè)2元、1個(gè)5元，或者3個(gè)5元，或者1個(gè)5元、1個(gè)10元，等等。顯然，最少需要2個(gè)錢(qián)幣才能 湊成15元。你的任務(wù)就是， 給定若干個(gè)互不相同的錢(qián)幣面值， 編程計(jì)算， 最少需要多少個(gè)錢(qián)幣才能湊成 某個(gè)給出的錢(qián)數(shù)?！疽?】【數(shù)據(jù)輸入 】輸入可以有多個(gè)測(cè)試用例。 每個(gè)測(cè)試用例的第一行是待湊的錢(qián)數(shù)值M(1 = M= 2000，整數(shù))，接著的一行中，第一個(gè)整數(shù)K(1 = K =

2、 10)表示幣種個(gè)數(shù)，隨后是K個(gè)互不相同的錢(qián)幣面值Ki(1 = Ki = 1000)。輸入M=0時(shí)結(jié)束?！緮?shù)據(jù)輸出 】每個(gè)測(cè)試用例輸出一行，即湊成錢(qián)數(shù)值M最少需要的錢(qián)幣個(gè)數(shù)。如果湊錢(qián)失 敗，輸出“Impossible”你可以假設(shè)，每種待湊錢(qián)幣的數(shù)量是無(wú)限多的?！緲永斎?】156 2 5 10 20 50 10011 20【樣例輸出 】2Impossible8Feli的生日禮物【問(wèn)題描述】Felicia的生日是11月1日（和Kitty是同一天生的哦） 。于是Feli請(qǐng)來(lái)Kitty一起過(guò)生日。Kitty帶來(lái)了最新款的“Kitty貓”玩具準(zhǔn)備送給Feli，不過(guò)她說(shuō)，這份禮物可不是白送的。Feli要

3、幫她一個(gè)忙，才能夠得到心儀已久的玩具。Kitty說(shuō)，“Kitty貓”玩具已經(jīng)賣(mài)出了n!個(gè)，*=10X00 *_*,Kitty想知道確切的數(shù)字，而不是無(wú)聊的“一個(gè)數(shù)加個(gè)感嘆號(hào)”。Feli聽(tīng)了大吃一驚。要知道，算出n!是一個(gè)無(wú)比艱巨的任務(wù)。Feli告訴Kitty，就算Feli算出n!，Kitty也看不下去，因?yàn)楫?dāng)n=20時(shí)，計(jì)算機(jī)的長(zhǎng)整型已經(jīng)存不下了（Kitty只能接受1-9之 間的數(shù)字）。于是Kitty說(shuō)，你只要告訴我n!最后一位非0的數(shù)就可以了。Feli想了想，立刻 動(dòng)手寫(xiě)了個(gè)程序算出了正確的答案。現(xiàn)在，請(qǐng)你也試試看！注意哦，AC的男生將會(huì)得到一個(gè)“Hello Kitty”計(jì)算器（可編程，CP

4、U 1THz，Mem 1TMB），AC的女生將會(huì)得到一個(gè)仿 真“Hello Kitty”寵物（善解人意，無(wú)須喂養(yǎng)，智商1101，附帶寫(xiě)情書(shū)功能）?！疽?】【數(shù)據(jù)輸入】每行一個(gè)n,直到輸入數(shù)據(jù)結(jié)束【數(shù)據(jù)輸出】對(duì)應(yīng)輸入的n，每行輸出一個(gè)答案【樣例輸入 】1101【樣例輸出 】蛇行矩陣【問(wèn)題描述】蛇形矩陣是由1開(kāi)始的自然數(shù)依次排列成的一個(gè)矩陣上三角形。【要求 】【數(shù)據(jù)輸入】本題有多組數(shù)據(jù)，每組數(shù)據(jù)由一個(gè)正整數(shù)N組成。（N不大于100）【數(shù)據(jù)輸出 】對(duì)于每一組數(shù)據(jù)，輸出一個(gè)N行的蛇形矩陣。兩組輸出之間不要額外的空行。 矩陣三角中同一行的數(shù)字用一個(gè)空格分開(kāi)。行尾不要多余的空格?！緲永斎?】5【樣例輸

5、出 】1 3 6 10 152 5 9 144 8 137 12114青蛙的約會(huì)【問(wèn)題描述】?jī)芍磺嗤茉诰W(wǎng)上相識(shí)了， 它們聊得很開(kāi)心， 于是覺(jué)得很有必要見(jiàn)一面。 它們很高興地發(fā)現(xiàn)它 們住在同一條緯度線上， 于是它們約定各自朝西跳， 直到碰面為止。 可是它們出發(fā)之前忘記 了一件很重要的事情， 既沒(méi)有問(wèn)清楚對(duì)方的特征， 也沒(méi)有約定見(jiàn)面的具體位置。 不過(guò)青蛙們 都是很樂(lè)觀的， 它們覺(jué)得只要一直朝著某個(gè)方向跳下去， 總能碰到對(duì)方的。 但是除非這兩只 青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂(lè)觀的青蛙， 你被要求寫(xiě)一個(gè)程序來(lái)判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。我們把這

6、兩只青蛙分別叫做青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東 往西為正方向，單位長(zhǎng)度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā) 點(diǎn)坐標(biāo)是x，青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩 只青蛙跳一次所花費(fèi)的時(shí)間相同。緯度線總長(zhǎng)L米?，F(xiàn)在要你求出它們跳了幾次以后才會(huì) 碰面?！疽?】【數(shù)據(jù)輸入】輸入只包括一行5個(gè)整數(shù)x,y,m,n,L,其中x豐y 2000000000,0 m、n 2000000000，0 L 2100000000。【數(shù)據(jù)輸出 】輸出碰面所需要的跳躍次數(shù),如果永遠(yuǎn)不可能碰面則輸出一行Impossible【樣例輸入 】1 2 3 4 5

7、【樣例輸出 】敲七【問(wèn)題描述】輸出7和7的倍數(shù)，還有包含7的數(shù)字例如（17，27，37.70，71，72，73.） 【要求 】【數(shù)據(jù)輸入】一個(gè)整數(shù)N。（N不大于30000）【數(shù)據(jù)輸出 】從小到大排列的不大于N的與7有關(guān)的數(shù)字，每行一個(gè)?！緲永斎?】20【樣例輸出 】71417連續(xù)郵資問(wèn)題【問(wèn)題描述】G國(guó)發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資 問(wèn)題要求對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，使得可在1張信封上貼出從 郵資1開(kāi)始，增量為1的最大連續(xù)郵資區(qū)間。 例如，當(dāng)n=5和m=4時(shí)，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續(xù)郵資

8、區(qū)間是1到70。編程任務(wù):對(duì)于給定的正整數(shù)m和n,計(jì)算出郵票面值的最佳設(shè)計(jì)。【要求 】【數(shù)據(jù)輸入 】輸入數(shù)據(jù)每一行給出2個(gè)正整數(shù)m和n的值(1=n,m=9),最后以0 0表 示文件結(jié)束?！緮?shù)據(jù)輸出 】對(duì)于輸以假定(ai, aj) = 1.輸出包含一個(gè)正整數(shù),即為Andy家至少養(yǎng)豬的數(shù)目?！緲永斎?】33 15 17 2【樣例輸出 】16kitty貓的基因編碼【問(wèn)題描述】kitty的基因編碼如下定義：kitty的基因由一串長(zhǎng)度2Ak(k=8)的01序列構(gòu)成，為了方便研究，需要把,01序列轉(zhuǎn)換為ABC編碼。用T(s)來(lái)表示01序列s的ABC編碼T(s)=A(當(dāng)S全由0組成)T(s)=B(當(dāng)s全由

9、1組成)T(s)=C+T(s1)+T(s2) s1,s2為把s等分為2個(gè)長(zhǎng)度相等的子串 比如T(00)=A T(00001111)=CAB【要求 】【數(shù)據(jù)輸入】一行，長(zhǎng)度為2Ak，為kitty貓的01基因編碼，有多個(gè)數(shù)據(jù)【數(shù)據(jù)輸出 】一行，由ABC構(gòu)成的ABC編碼【樣例輸出 】01001011【樣例輸出 】CCCABACCBAB取石子游戲【問(wèn)題描述】有兩堆石子，數(shù)量任意，可以不同。游戲開(kāi)始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種 不同的取法，一是可以在任意的一堆中取走任意多的石子； 二是可以在兩堆中同時(shí)取走相同 數(shù)量的石子。 最后把石子全部取完者為勝者。 現(xiàn)在給出初始的兩堆石子的數(shù)目， 如果輪

10、到你 先取，假設(shè)雙方都采取最好的策略，問(wèn)最后你是勝者還是敗者?！疽?】【數(shù)據(jù)輸入 】輸入包含若干行， 表示若干種石子的初始情況， 其中每一行包含兩個(gè)非負(fù)整數(shù)a和b,表示兩堆石子的數(shù)目，a和b都不大于1,000,000,000?！緮?shù)據(jù)輸出 】輸出對(duì)應(yīng)也有若干行，每行包含一個(gè)數(shù)字1或0，如果最后你是勝者，則為1，反之,則為0?！緲永斎?】2 18 44 7【樣例輸出 】010勇氣的挑戰(zhàn)【問(wèn)題描述】給定n個(gè)點(diǎn)的坐標(biāo)（x,y,z）,且*=50,從點(diǎn)1出發(fā),怎么樣才能走一條路徑 一次,使走過(guò)的距離和最小?【要求 】【數(shù)據(jù)輸入】多組數(shù)據(jù)第1行n,然后n行3個(gè)整數(shù)坐標(biāo)【數(shù)據(jù)輸出 】每組一行,代表最小權(quán)和

11、 【樣例輸入 】30 0 01 1 01 -1 0【樣例輸出 】3.4,訪問(wèn)每個(gè)點(diǎn)一次且僅Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1608Accepted Submission(s): 877統(tǒng)計(jì)同成績(jī)學(xué)生人數(shù)【問(wèn)題描述】讀入N名學(xué)生的成績(jī)，將獲得某一給定分?jǐn)?shù)的學(xué)生人數(shù)輸出?！疽?】【數(shù)據(jù)輸入 】測(cè)試輸入包含若干測(cè)試用例，每個(gè)測(cè)試用例的格式為第1行：N第2行：N名學(xué)生的成績(jī)，相鄰兩數(shù)字用一個(gè)空格間隔。第3行：給定分?jǐn)?shù)當(dāng)讀到N=0時(shí)輸入

12、結(jié)束。其中N不超過(guò)1000，成績(jī)分?jǐn)?shù)為(包含)0到100之間的一個(gè)整 數(shù)?！緮?shù)據(jù)輸出 】對(duì)每個(gè)測(cè)試用例，將獲得給定分?jǐn)?shù)的學(xué)生人數(shù)輸出?！緲永敵?】380 60 9060285 660560 75 90 55 75750【樣例輸出 】102Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1608Accepted Submission(s): 877錢(qián)幣兌換問(wèn)題【問(wèn)題描述】在一個(gè)國(guó)家僅有1分，2分，3分硬幣，將錢(qián)N兌換成硬幣有很多種兌法。請(qǐng)你編程

13、序計(jì)算 出共有多少種兌法?！疽?】【數(shù)據(jù)輸入 】每行只有一個(gè)正整數(shù)N，N小于32768。【數(shù)據(jù)輸出 】對(duì)應(yīng)每個(gè)輸入，輸出兌換方法數(shù)?！緲永斎?】293412553【樣例輸出 】71883113137761Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1608Accepted Submission(s): 877字串?dāng)?shù)【問(wèn)題描述】一個(gè)A和兩個(gè)B一共可以組成三種字符串:ABB,BAB,BBA.給定若趕字母和它們相應(yīng)的個(gè)數(shù),計(jì)算一共可以組成多少

14、個(gè)不同的字符串.【要求 】【數(shù)據(jù)輸入 】每組測(cè)試數(shù)據(jù)分兩行,第一行為n(1=n=26),表示不同字母的個(gè)數(shù),第二行為n個(gè)數(shù)A1,A2,.,An(1=Ai=12),表示每種字母的個(gè)數(shù).測(cè)試數(shù)據(jù)以n=0為結(jié)束.【數(shù)據(jù)輸出】對(duì)于每一組測(cè)試數(shù)據(jù)，輸出一個(gè)m,表示一共有多少種字符串.【樣例輸入 】21 232 2 20【樣例輸出 】390Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1608Accepted Submission(s): 877小希的數(shù)

15、表【問(wèn)題描述】Gardon昨天給小希布置了一道作業(yè)，即根據(jù)一張由不超過(guò)5000的N(3=N=100)個(gè)正整數(shù) 組成的數(shù)表兩兩相加得到N*(N-1)/2個(gè)和，然后再將它們排序。例如，如果數(shù)表里含有四個(gè) 數(shù)1，3，4，9，那么正確答案是4，5，7，10，12，13。小希做完作業(yè)以后出去玩了一陣， 可是下午回家時(shí)發(fā)現(xiàn)原來(lái)的那張數(shù)表不見(jiàn)了， 好在她做出的答案還在， 你能幫助她根據(jù)她的 答案計(jì)算出原來(lái)的數(shù)表么？【要求 】【數(shù)據(jù)輸入 】包含多組數(shù)據(jù)，每組數(shù)據(jù)以一個(gè)N開(kāi)頭，接下來(lái)的一行有按照大小順序排列 的N*(N-1)/2個(gè)數(shù)，是小希完成的答案。文件最后以一個(gè)0結(jié)束。假設(shè)輸入保證解的存在性和唯一性?！緮?shù)據(jù)

16、輸出 】對(duì)于每組數(shù)據(jù)，輸出原來(lái)的數(shù)表。它們也應(yīng)當(dāng)是按照順序排列的?！緲永斎?】44 5 7 10 12 1345 6 7 8 9 100【樣例輸出 】1 3 4 92 3 4 6Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1608Accepted Submission(s): 877士兵隊(duì)列訓(xùn)練問(wèn)題【問(wèn)題描述】 某部隊(duì)進(jìn)行新兵隊(duì)列訓(xùn)練， 將新兵從一開(kāi)始按順序依次編號(hào)， 并排成一行橫隊(duì)， 訓(xùn)練的規(guī)則 如下： 從頭開(kāi)始一至二報(bào)數(shù)，凡報(bào)到二的出

17、列，剩下的向小序號(hào)方向靠攏， 再?gòu)念^開(kāi)始進(jìn)行 一至三報(bào)數(shù)，凡報(bào)到三的出列，剩下的向小序號(hào)方向靠攏， 繼續(xù)從頭開(kāi)始進(jìn)行一至二報(bào)數(shù)。 。 以后從頭開(kāi)始輪流進(jìn)行一至二報(bào)數(shù)、一至三報(bào)數(shù)直到剩下的人數(shù)不超過(guò)三人為止?！疽?】【數(shù)據(jù)輸入】本題有多個(gè)測(cè)試數(shù)據(jù)組，第一行為組數(shù)N，接著為N行新兵人數(shù)，新兵人數(shù)不超過(guò)5000?！緮?shù)據(jù)輸出 】共有N行，分別對(duì)應(yīng)輸入的新兵人數(shù)，每行輸出剩下的新兵最初的編號(hào)，編 號(hào)之間有一個(gè)空格?！緲永斎?】22040【樣例輸出 】1 7 191 19 37Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768

18、 K (Java/Others)Total Submission(s): 1608Accepted Submission(s): 877最簡(jiǎn)單的計(jì)算機(jī)【問(wèn)題描述】一個(gè)名叫是PigHeadThree的研究組織設(shè)計(jì)了一臺(tái)實(shí)驗(yàn)用的計(jì)算機(jī)，命名為PpMm。PpMm只能執(zhí)行簡(jiǎn)單的六種命令A(yù),B,C,D,E,F;只有二個(gè)內(nèi)存M1,M2;三個(gè)寄存器R1,R2，R3。六種命令的含義如下：命令A(yù):將內(nèi)存M1的數(shù)據(jù)裝到寄存器R1中；命令B:將內(nèi)存M2的數(shù)據(jù)裝到寄存器R2中；命令C:將寄存器R3的數(shù)據(jù)裝到內(nèi)存M1中；命令D:將寄存器R3的數(shù)據(jù)裝到內(nèi)存M2中；命令E:將寄存器R1中的數(shù)據(jù)和寄存器R2中的數(shù)據(jù)相加，結(jié)果

19、放到寄存器R3中； 命令F:將寄存器R1中的數(shù)據(jù)和寄存器R2中的數(shù)據(jù)相減，結(jié)果放到寄存器R3中。 你的任務(wù)是:設(shè)計(jì)一個(gè)程序模擬PpMm的運(yùn)行。【要求 】【數(shù)據(jù)輸入 】有若干組，每組有2行，第一行是2個(gè)整數(shù)，分別表示M1和M2中的初始內(nèi) 容；第二行是一串長(zhǎng)度不超過(guò)200的由大寫(xiě)字母A到F組成的命令串，命令串的含義如上 所述。【數(shù)據(jù)輸出 】對(duì)應(yīng)每一組的輸入，輸出只有一行，二個(gè)整數(shù)，分別表示 其中M1和M2之間用逗號(hào)隔開(kāi)。其他說(shuō)明：R1，R2，R3的初始值為0,所有中間結(jié)果都在-2A31和2A31之間?！緲永斎?】100 288ABECED876356 321456ABECAEDBECAF【數(shù)據(jù)輸

20、出 】388,3882717080,1519268M1，M2的內(nèi)容；Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 241 Accepted Submission(s): 168愚人節(jié)的禮物【問(wèn)題描述】四月一日快到了，Vayko想了個(gè)愚人的好辦法送禮物。嘿嘿，不要想的太好，這禮物可 沒(méi)那么簡(jiǎn)單，Vayko為了愚人，準(zhǔn)備了一堆盒子，其中有一個(gè)盒子里面裝了禮物。盒子里面 可以再放零個(gè)或者多個(gè)盒子。假設(shè)放禮物的盒子里不再放其他盒子。用()表示一個(gè)盒

21、子，B表示禮物，Vayko想讓你幫她算出愚人指數(shù)，即最少需要拆多少個(gè)盒子才能拿到禮物?！疽?】【數(shù)據(jù)輸入 】本題目包含多組測(cè)試， 請(qǐng)?zhí)幚淼轿募Y(jié)束。 每組測(cè)試包含一個(gè)長(zhǎng)度不大于1000,只包含(,)和B三種字符的字符串，代表Vayko設(shè)計(jì)的禮物透視圖。你可以假設(shè)，每個(gè)透視圖畫(huà)的都是合法的?！緮?shù)據(jù)輸出 】對(duì)于每組測(cè)試，請(qǐng)?jiān)谝恍欣锩孑敵鲇奕酥笖?shù)?！緲永斎?】(B)()()(B)【樣例輸出 】41Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1

22、608Accepted Submission(s): 877整數(shù)對(duì)【問(wèn)題描述】Gardon和小希玩了一個(gè)游戲，Gardon隨便想了一個(gè)數(shù)A（首位不能為0）,把它去掉一個(gè)數(shù)字以后得到另外一個(gè)數(shù)B,他把A和B的和N告訴了小希，讓小希猜想他原來(lái)想的數(shù)字。 不過(guò)為了公平起見(jiàn)，如果小?；卮鸬臄?shù)雖然不是A，但同樣能達(dá)到那個(gè)條件（去掉其中的一個(gè)數(shù)字得到B，A和B之和是N）, 樣算小希勝利。而且小希如果能答出多個(gè)符合條件的 數(shù)字，就可以得到額外的糖果。所以現(xiàn)在小希希望你編寫(xiě)一個(gè)程序，來(lái)幫助她找到盡可能多的解。例如，Gardon想的是A=31,B=3告訴小希N=34，小希除了回答31以外還可以回答27（27+7

23、=34）所以小希可以因此而得到一個(gè)額外的糖果?！疽?】【數(shù)據(jù)輸入】輸入包含多組數(shù)據(jù)，每組數(shù)據(jù)一行，包含一個(gè)數(shù)N（1=N=10A9），文件以0結(jié)尾?！緮?shù)據(jù)輸出】 對(duì)于每個(gè)輸入的N， 輸出所有符合要求的解 （按照大小順序排列） 如果沒(méi)有這 樣的解， 輸出No solution.【樣例輸入 】34152210【樣例輸出 】27 31 32126 136 139 141No solution.Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1608A

24、ccepted Submission(s): 877寒冰王座【問(wèn)題描述】 不死族的巫妖王發(fā)工資拉,死亡騎士拿到一張N元的鈔票(記住,只有一張鈔票),為了防止自己 在戰(zhàn)斗中頻繁的死掉，他決定給自己買(mǎi)一些道具，于是他來(lái)到了地精商店前.死亡騎士：“我要買(mǎi)道具！”地精商人：“我們這里有三種道具，血瓶150塊一個(gè)，魔法藥200塊一個(gè)，無(wú)敵 藥水350塊一個(gè)。”死亡騎士：“好的,給我一個(gè)血瓶。 ”說(shuō)完他掏出那張N元的大鈔遞給地精 商人.地精商人：“我忘了提醒你了，我們這里沒(méi)有找客人錢(qián)的習(xí)慣的，多的錢(qián)我們都當(dāng)小費(fèi) 收了的，嘿嘿。”死亡騎士： “”死亡騎士想，與其把錢(qián)當(dāng)小費(fèi)送個(gè)他還不如自己多買(mǎi)一 點(diǎn)道具，反正

25、以后都要買(mǎi)的，早點(diǎn)買(mǎi)了放在家里也好，但是要盡量少讓他賺小費(fèi)?，F(xiàn)在死亡騎士希望你能幫他計(jì)算一下，最少他要給地精商人多少小費(fèi)?！疽?】【數(shù)據(jù)輸入 】輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)T(1=T=100),代表測(cè)試數(shù)據(jù)的數(shù)量.然后是T行測(cè)試數(shù)據(jù),每個(gè)測(cè)試數(shù)據(jù)只包含一個(gè)正整數(shù)N(1=N=10000),N代表死亡騎士手中鈔票的面值.注意： 地精商店只有題中描述的三種道具.【數(shù)據(jù)輸出 】對(duì)于每組測(cè)試數(shù)據(jù),請(qǐng)你輸出死亡騎士最少要浪費(fèi)多少錢(qián)給地精商人作為小費(fèi)【樣例輸入 】2900250【樣例輸出 】050Time Limit: 10000/5000 MS (Java/Others)Memory Limit: 655

26、36/32768 K (Java/Others)Total Submission(s): 170Accepted Submission(s): 60覆蓋的面積【問(wèn)題描述】給定平面上若干矩形,求出被這些矩形覆蓋過(guò)至少兩次的區(qū)域的面積.【要求 】【數(shù)據(jù)輸入 】輸入數(shù)據(jù)的第一行是一個(gè)正整數(shù)T(1=T=100),代表測(cè)試數(shù)據(jù)的數(shù)量.每個(gè)測(cè)試 數(shù)據(jù)的第一行是一個(gè)正整數(shù)N(1=N13,12-23,13-12,13-32,23-21,23-31。 注意：文件里只有一個(gè)整數(shù)N(2wNw1000)?！緮?shù)據(jù)輸出 】輸出一個(gè)整數(shù)，為可能的過(guò)程的總數(shù)除以10007的余數(shù)。【樣例輸入 】4【樣例輸出 】96Time l

27、imit: 11s Memory limit: 32768KTotal Submit : 184Accepted Submit : 75猴子的爭(zhēng)斗【問(wèn)題描述】從前在一個(gè)森林里，有N只好斗的猴子。一開(kāi)始，他們互不認(rèn)識(shí)。互不認(rèn)識(shí)的猴子間是無(wú) 法避免爭(zhēng)斗的， 而且爭(zhēng)斗只會(huì)發(fā)生在兩只互不認(rèn)識(shí)的猴子間。 決斗結(jié)束后， 這兩只猴子和他 們各自的朋友們通過(guò)這場(chǎng)決斗相互間都認(rèn)識(shí)了，爭(zhēng)斗便不會(huì)再發(fā)生在這一大群猴子中的任兩 只。由于爭(zhēng)斗是比較激烈的，所以同一時(shí)間內(nèi)不會(huì)有兩場(chǎng)決斗一起發(fā)生。經(jīng)過(guò)N-1次決斗 后，這N只猴子間相互都認(rèn)識(shí)了，現(xiàn)在問(wèn)有多少種可能的決斗過(guò)程。例如N=3，有6種不同的過(guò)程：12-13，12-2

28、3，13-12，13-32，23-21，23-31?！疽?】【數(shù)據(jù)輸入】文件里只有一個(gè)整數(shù)N(2N1000)?！緮?shù)據(jù)輸出 】輸出一個(gè)整數(shù)，為可能的過(guò)程的總數(shù)除以10007的余數(shù)?！緲永斎?】4【樣例輸出 】96Time limit: 10s Memory limit: 32768KTotal Submit : 70 Accepted Submit : 121提示：只需要一步就可以完成排序：3 2 1 41 2 3 4。排序【問(wèn)題描述】通常我們對(duì)一個(gè)長(zhǎng)度為n(n24)的整數(shù)數(shù)列進(jìn)行排序操作，其實(shí)就是講他們按照從小到大的順序重整。 一般情況下我們可以比較任意兩個(gè)數(shù)之間的大小并交換他們的位置，但

29、這里我們限制只能數(shù)列的某一個(gè)前綴序列翻轉(zhuǎn)， 除此之外的任何操作都是不允許的。 更精確地說(shuō)， 假 設(shè)數(shù)列al, a2,an,個(gè)合法的操作是把數(shù)列變?yōu)閍k, ak-1,.,a2, a1, ak+1, ak+2,.,an,其中1kwn。例如：數(shù)列3 2 1 4，可能的操作有三種，分別是2 3 1 4、1 2 3 4、4 1 2 3。你任務(wù)是求出一個(gè)序列用上面的方法排序至少需要多少步?！疽?】【數(shù)據(jù)輸入】輸入文件有兩行：第一行是一個(gè)整數(shù)n,表示數(shù)列的長(zhǎng)度。第二行有n個(gè)整數(shù), 表示待排序的數(shù)列,每個(gè)整數(shù)的絕對(duì)值不大于32767?！緮?shù)據(jù)輸出】輸出文件有一行是一個(gè)整數(shù)s,表示完成排序所需的最少步數(shù)?！緲永?/p>

30、輸入 】43 2 1 4【樣例輸出 】Time limit: 10sMemory limit: 32768KTotal Submit : 100Accepted Submit : 13選址【問(wèn)題描述】很久以前， 在世界的某處有一個(gè)形狀為凸多邊形的小島， 島上的居民們決定建一個(gè)祭壇， 居 民們認(rèn)為祭壇的位置離島的頂點(diǎn)處越遠(yuǎn)越好。 你的任務(wù)是求凸多邊形內(nèi)一點(diǎn)， 使其與各頂點(diǎn) 的距離中最短的距離最遠(yuǎn)， 點(diǎn)在邊上也可以。這樣的點(diǎn)可能有多個(gè)， 你只需輸出這些點(diǎn)與各 頂點(diǎn)的最短距離?！疽?】【數(shù)據(jù)輸入】第一行是一個(gè)整數(shù)N(3NW100)。接下來(lái)N行按逆時(shí)針順序給出每個(gè)頂點(diǎn)的坐標(biāo)，每行包含 縱坐標(biāo)(坐標(biāo)絕

31、對(duì)值小于10000)。數(shù)據(jù)輸出 】輸出一個(gè)實(shí)數(shù)，表示凸多邊形內(nèi)一點(diǎn)與各頂點(diǎn)的距離中最短的距離的最大值?！緲永斎?】30 29 07 7【樣例輸出 】4.8932個(gè)實(shí)數(shù)，表示頂點(diǎn)的橫坐標(biāo)和Time limit: 1s Memory limit: 32768KTotal Submit : 471Accepted Submit : 325過(guò)河【問(wèn)題描述】 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子， 青蛙很討厭踩在這些石子上。 由于橋的長(zhǎng)度和青蛙一次跳過(guò)的距離都是正整數(shù)， 我們可以把 獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0,1,L（其中L是橋的長(zhǎng)度）。

32、坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為L(zhǎng)的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開(kāi)始，不停的 向終點(diǎn)方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過(guò)坐標(biāo)為L(zhǎng)的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長(zhǎng)度L,青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過(guò)河，最少需要踩到的石子數(shù)。【要求 】【數(shù)據(jù)輸入 】輸入的第一行有一個(gè)正整數(shù)L（1 = L = 109）,表示獨(dú)木橋的長(zhǎng)度。第二行 有三個(gè)正整數(shù)S,T,M,分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè) 數(shù),其中1 = S = T = 10,1 = M = 100。第三行有M個(gè)不同的正整數(shù)分別

33、表示這M個(gè) 石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒(méi)有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開(kāi)。【數(shù)據(jù)輸出 】輸出只包括一個(gè)整數(shù),表示青蛙過(guò)河最少需要踩到的石子數(shù)。【樣例輸入 】102 3 52 3 5 6 7【樣例輸出 】Time limit: 1s Memory limit: 32768KTotal Submit : 471Accepted Submit : 325數(shù)字游戲【問(wèn)題描述】小W發(fā)明了一個(gè)游戲，他在黑板上寫(xiě)出了一行數(shù)字a1,a2,.an,然后給你m個(gè)回合的機(jī)會(huì)，每回合你可以從中選擇一個(gè)數(shù)擦去它，接著剩下來(lái)的每個(gè)數(shù)字ai都要遞減一個(gè)值bi。如此重復(fù)m個(gè)回合，所有你擦去的數(shù)字之

34、和就是你所得到的分?jǐn)?shù)。小W和他的好朋友小Y玩了這個(gè)游戲,可是他發(fā)現(xiàn),對(duì)于每個(gè)給出的an和bn序列,小Y的得分總是比他高,所以 他就很不服氣。 于是他想讓你幫他算算, 對(duì)于每個(gè)an和bn序列, 可以得到的最大得分是多 少。這樣他就知道有沒(méi)有可能超過(guò)小Y的得分。【要求 】【數(shù)據(jù)輸入 】第一行,一個(gè)整數(shù)n(1=n=200),表示數(shù)字的個(gè)數(shù)。第二行，一個(gè)整數(shù)m(1=m=n)，表示回合數(shù)。接下來(lái)一行有n個(gè)不超過(guò)10000的正整數(shù)，a1,a2an,表示原始數(shù)字，最后一行有n個(gè)不超過(guò)500的正整數(shù)，b1,b2.bn,表示每回合每個(gè)數(shù)字遞減的值數(shù)據(jù)輸出 】一個(gè)整數(shù),表示最大可能的得分 【樣例輸入 】3310

35、20 304 5 6【樣例輸出 】47Time limit: 5sMemory limit: 32768KTotal Submit : 295Accepted Submit : 209速配游戲【問(wèn)題描述】有這么一個(gè)速配電視節(jié)目。N位男士和N位女士要在攝像機(jī)前選出他們合適的伴侶。每位 女士按照其對(duì)每位男士作為配偶的偏愛(ài)程度給每位男士排名次， 每位男士也按照其對(duì)每位女 士作為配偶的偏愛(ài)程度給每位女士排名次。 這些名次不允許并列。 然后每位男士將向心儀的 對(duì)象求婚，經(jīng)過(guò)殘酷的競(jìng)爭(zhēng)之后各自找到適合的伴侶。最開(kāi)始的時(shí)候每位男士都還沒(méi)有被任何一位女士拒絕。 求婚環(huán)節(jié)會(huì)經(jīng)過(guò)很多輪進(jìn)行， 每一輪：(1)每位男

36、士向還沒(méi)有拒絕過(guò)自己的女士中選出自己認(rèn)為最理想的一個(gè)，并向她求婚(2)每位女士在所有這一輪中向她求婚的男士中選出自己認(rèn)為最理想的一個(gè)，并不答應(yīng)，也 不拒絕。她把其余向她求婚的男士都婉言拒絕掉。 經(jīng)過(guò)了若干輪求婚之后， 在某一輪， 幸運(yùn) 的事情發(fā)生了： 所有的女士都恰好有一個(gè)求婚者， 所有的男士都找到一個(gè)心儀的對(duì)象。 主持 人將繼續(xù)指出這個(gè)配對(duì)方式的神奇之處：沒(méi)有任意的兩個(gè)配對(duì)，比方說(shuō)男士A和女士a配 對(duì)，男士B和女士b配對(duì)，使得在A心目中b較a更理想，而且在b心目中A較B更理想(這 樣A和b就會(huì)私奔”)。因此，主持人總結(jié)說(shuō)，這個(gè)配對(duì)是非常合理的。(他知道，這種情況是一定會(huì)發(fā)生的。 )主持人在節(jié)

37、目之前已經(jīng)知道男士和女士之間的偏愛(ài)情況， 他想預(yù)先知道最后的匹配結(jié)果是怎 么樣的，你能幫幫他嗎？【要求 】【數(shù)據(jù)輸入 】第一行包括一個(gè)數(shù)字N(1=N=1000)以下N*2行，每行有N個(gè)數(shù)字。 第i+1行(1=i=N)表示編號(hào)為i的男士對(duì)女士們的排序(從最喜歡的到最不喜歡的) 。第N+j+1行(1=j=N)表示編號(hào)為j的女士對(duì)男士們的排序(同樣從最喜歡的到最不喜歡的) ?！緮?shù)據(jù)輸出 】N行，每行包括一個(gè)數(shù)字。第i行的數(shù)字表示與編號(hào)為i的男士匹配的女士的 編號(hào)?！緲永斎?】31 2 32 3 12 1 33 2 12 3 12 3 1【樣例輸出 】321Time limit: 1s Memory

38、 limit: 32768KTotal Submit : 471Accepted Submit : 3253n+1數(shù)鏈問(wèn)題【問(wèn)題描述】在計(jì)算機(jī)科學(xué)上，有很多類問(wèn)題是無(wú)法解決的，我們稱之為不可解決問(wèn)題。 然而， 在很多情 況我們并不知道哪一類問(wèn)題可以解決，那一類問(wèn)題不可解決?，F(xiàn)在我們就有這樣一個(gè)問(wèn)題， 問(wèn)題如下：1.輸入一個(gè)正整數(shù)n；2.把n顯示出來(lái)；3.如果n=1則結(jié)束；4.如果n是奇數(shù)則n變?yōu)?，否則n變?yōu)閚/2；5.轉(zhuǎn)入第2步。例如對(duì)于輸入的正整數(shù)22，應(yīng)該有如下數(shù)列被顯示出來(lái)：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1我們推測(cè)：對(duì)于任意一個(gè)正整數(shù)

39、，經(jīng)過(guò)以上算法最終會(huì)推到1。盡管這個(gè)算法很簡(jiǎn)單，但我們?nèi)匀粺o(wú)法確定我們的推斷是否正確。不過(guò)好在我們有計(jì)算機(jī)，我們驗(yàn)證了對(duì)于小于1,000,000的正整數(shù)都滿足以上推斷。對(duì)于給定的正整數(shù)n,我們把顯示出來(lái)的數(shù)的個(gè)數(shù)定義為n的鏈長(zhǎng)，例如22的鏈長(zhǎng)為16。你的任務(wù)是編寫(xiě)一個(gè)程序，對(duì)于任意一對(duì)正整數(shù)i和j,給出i、j之間的最長(zhǎng)鏈長(zhǎng)，當(dāng)然這個(gè)最長(zhǎng)鏈長(zhǎng)是由i、j之間的其中一個(gè)正整數(shù)產(chǎn)生的。我們這里的i、j之間即包括i也包括j?！疽?】【數(shù)據(jù)輸入】輸入文件只有一行，即為正整數(shù)i和j，i和j之間以一個(gè)空格隔開(kāi)。0 ij 10,000?！緮?shù)據(jù)輸出 】文件只能有一行,即為i、j之間的最長(zhǎng)鏈長(zhǎng)?！緲永斎?】1

40、10【樣例輸出 】20Time limit: 1s Memory limit: 32768KTotal Submit : 471Accepted Submit : 325數(shù)制轉(zhuǎn)換【問(wèn)題描述】有一種數(shù)制的基數(shù)是3，權(quán)值可以取-1,0,1，并分別用符號(hào)-,0,1表示，如這種數(shù)制的101表示十進(jìn)制數(shù)的10，即1*(3人2)+0*(3人1)+1*(3人0)=10，又如這種數(shù)制的-0表示十進(jìn)制數(shù)的-3,即-1*(3A1)+0*(3A0)=-3。編程要求把給定的有符號(hào)整數(shù)轉(zhuǎn)換為新數(shù)制的數(shù)，該數(shù)的前面不能 有多余的0，如10的新數(shù)制表示是101，則不要輸出成0101?！疽?】【數(shù)據(jù)輸入】文件有一行或多行，

41、每行有一個(gè)整數(shù)N (-2,147,483,647NW2,147,483,647),整數(shù)內(nèi)不會(huì)有其他分隔符?！緮?shù)據(jù)輸出 】對(duì)輸入文件的每一行輸出一行， 該行是輸入行的整數(shù)的新數(shù)制表示， 不能有多 余空行，每行之前不能有前導(dǎo)空格?！緲永斎?】10-3【樣例輸出 】101-0Time limit: 1s Memory limit: 32768KTotal Submit : 471Accepted Submit : 325數(shù)列【問(wèn)題描述】給定一個(gè)正整數(shù)k（3kw15）,把所有k的方幕及所有有限個(gè)互不相等的k的方幕之和構(gòu)成一個(gè)遞增的序列，例如，當(dāng)k=3時(shí)，這個(gè)序列是：1，3，4，9，10，12，13,

42、（該序列實(shí)際上就是：30，31，30+31，32，30+32，31+32，30+31+32，）請(qǐng)你求出這個(gè)序列的第N項(xiàng)的值（用10進(jìn)制數(shù)表示）。例如，對(duì)于k=3，N=100，正確答案應(yīng)該是981?！疽?】【數(shù)據(jù)輸入 】輸入包含多個(gè)測(cè)試數(shù)據(jù)。每個(gè)測(cè)試數(shù)據(jù)只有1行，為2個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：k N（k、N的含義與上述的問(wèn)題描述一致，且3kw15，10wNw1000）【數(shù)據(jù)輸出 】對(duì)于每個(gè)測(cè)試數(shù)據(jù)輸出一個(gè)正整數(shù)（在所有的測(cè)試數(shù)據(jù)中，結(jié)果均不超過(guò)2.1*109）?！緲永斎?】3 1003 100【樣例輸出 】981981Time limit: 1s Memory limit: 32768KTo

43、tal Submit : 471Accepted Submit : 3252Ak進(jìn)制數(shù)【問(wèn)題描述】設(shè)r是個(gè)2k進(jìn)制數(shù)，并滿足以下條件：（1）r至少是個(gè)2位的2k進(jìn)制數(shù)。（2）作為2k進(jìn)制數(shù)，除最后一位外，r的每一位嚴(yán)格小于它右邊相鄰的那一位。（3）將r轉(zhuǎn)換為2進(jìn)制數(shù)q后，則q的總位數(shù)不超過(guò)w。在這里，正整數(shù)k（1kw9）和w（kww30000）是事先給定的。問(wèn)：滿足上述條件的不同的r共有多少個(gè)？我們?cè)購(gòu)牧硪唤嵌茸餍┙忉專?設(shè)S是長(zhǎng)度為w的01字符串（即字符串S由w個(gè)“0”或“1” 組成），S對(duì)應(yīng)于上述條件（3）中的q。將S從右起劃分為若干個(gè)長(zhǎng)度為k的段，每段對(duì)應(yīng) 一位2k進(jìn)制的數(shù)，如果S至少可

44、分成2段，則S所對(duì)應(yīng)的二進(jìn)制數(shù)又可以轉(zhuǎn)換為上述的2k進(jìn)制數(shù)r。例：設(shè)k=3，w=7。則r是個(gè)八進(jìn)制數(shù)（23=8）。由于w=7，長(zhǎng)度為7的01字符串按3位一 段分，可分為3段（即1，3，3，左邊第一段只有一個(gè)二進(jìn)制位） ，則滿足條件的八進(jìn)制數(shù) 有：2位數(shù)：高位為1:6個(gè)（即12,13,14,15,16,17）,高位為2:5個(gè)，高位為6:1個(gè)（即67）。共6+5+1=21個(gè)。3位數(shù)：高位只能是1,第2位為2:5個(gè)（即123,124,125,126,127）,第2位為3：4個(gè)，第2位為6:1個(gè)（即167）。共5+4+1=15個(gè)。 所以，滿足要求的r共有36個(gè)?！疽?】【數(shù)據(jù)輸入 】輸入包含多個(gè)測(cè)試

45、數(shù)據(jù), 每個(gè)測(cè)試數(shù)據(jù)只有1行,為兩個(gè)正整數(shù), 用一個(gè)空格 隔開(kāi)：k W【數(shù)據(jù)輸出 】對(duì)于每個(gè)測(cè)試數(shù)據(jù),輸出一行,是一個(gè)正整數(shù),為所求的計(jì)算結(jié)果,即滿足條 件的不同的r的個(gè)數(shù)（用十進(jìn)制數(shù)表示） ,要求最高位不得為0,各數(shù)字之間不得插入數(shù)字 以外的其他字符（例如空格、換行符、逗號(hào)等） 。（提示：作為結(jié)果的正整數(shù)可能很大,但不會(huì)超過(guò)200位）【樣例輸入 】3 73 7【樣例輸出 】3636Time limit: 1s Memory limit: 32768KTotal Submit : 471Accepted Submit : 325【問(wèn)題描述】 某小學(xué)最近得到了一筆贊助，打算拿出其中一部分為學(xué)習(xí)成

46、績(jī)優(yōu)秀的前5名學(xué)生發(fā)獎(jiǎng)學(xué)金。 期末，每個(gè)學(xué)生都有3門(mén)課的成績(jī)：語(yǔ)文、數(shù)學(xué)、英語(yǔ)。先按總分從高到低排序，如果兩個(gè) 同學(xué)總分相同， 再按語(yǔ)文成績(jī)從高到低排序， 如果兩個(gè)同學(xué)總分和語(yǔ)文成績(jī)都相同， 那么規(guī) 定學(xué)號(hào)小的同學(xué)排在前面，這樣，每個(gè)學(xué)生的排序是唯一確定的。任務(wù)：先根據(jù)輸入的3門(mén)課的成績(jī)計(jì)算總分， 然后按上述規(guī)則排序， 最后按排名順序輸出前5名學(xué)生的學(xué)號(hào)和總分。注意，在前5名同學(xué)中，每個(gè)人的獎(jiǎng)學(xué)金都不相同，因此，你必須 嚴(yán)格按上述規(guī)則排序。例如，在某個(gè)正確答案中，如果前兩行的輸出數(shù)據(jù)（每行輸出兩個(gè)數(shù)：學(xué)號(hào)、總分）是：7 2795 279這兩行數(shù)據(jù)的含義是：總分最高的兩個(gè)同學(xué)的學(xué)號(hào)依次是 是27

47、9（總分等于輸入的語(yǔ)文、數(shù)學(xué)、英語(yǔ)三科成績(jī)之和） 高一些。如果你的前兩名的輸出數(shù)據(jù)是：5 2797 279則按輸出錯(cuò)誤處理，不能得分?！疽?】【數(shù)據(jù)輸入 】輸入包含多組測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)有n+1行。第1行為一個(gè)正整數(shù)n表示該校參加評(píng)選的學(xué)生人數(shù)。第2到n+1行，每行有3個(gè)用空格隔開(kāi)的數(shù)字，每個(gè)數(shù)字都在0到100之間。第j行的3個(gè)數(shù)字依次表示學(xué)號(hào)為j-1的學(xué)生的語(yǔ)文、數(shù)學(xué)、英語(yǔ)的成績(jī)。每個(gè)學(xué)生的學(xué)號(hào)按照輸入順序 編號(hào)為1n（恰好是輸入數(shù)據(jù)的行號(hào)減1）。所給的數(shù)據(jù)都是正確的，不必檢驗(yàn)?！緮?shù)據(jù)輸出 】對(duì)于每個(gè)測(cè)試數(shù)據(jù)輸出5行，每行是兩個(gè)用空格隔開(kāi)的正整數(shù),依次表示前5名學(xué)生的學(xué)號(hào)和總分。兩個(gè)相

48、鄰測(cè)試數(shù)據(jù)間用一個(gè)空行隔開(kāi)?！緲永斎?】690 67 8087 66 9178 89 9188 99 7767 89 6478 89 98880 89 897號(hào)、5號(hào)。這兩名同學(xué)的總分都，但學(xué)號(hào)為7的學(xué)生語(yǔ)文成績(jī)更88 98 7890 67 8087 66 9178 89 9188 99 7767 89 6478 89 98【樣例輸出 】6 2654 2643 2582 2441 2378 2652 2646 2641 2585 258Time limit: 1s Memory limit: 32768KTotal Submit : 471Accepted Submit : 325紀(jì)念品分組

49、【問(wèn)題描述】元旦快到了， 校學(xué)生會(huì)讓樂(lè)樂(lè)負(fù)責(zé)新年晚會(huì)的紀(jì)念品發(fā)放工作。 為使得參加晚會(huì)的同學(xué)所獲 得的紀(jì)念品價(jià)值相對(duì)均衡， 他要把購(gòu)來(lái)的紀(jì)念品根據(jù)價(jià)格進(jìn)行分組， 但每組最多只能包括兩 件紀(jì)念品， 并且每組紀(jì)念品的價(jià)格之和不能超過(guò)一個(gè)給定的整數(shù)。 為了保證在盡量短的時(shí)間 內(nèi)發(fā)完所有紀(jì)念品， 樂(lè)樂(lè)希望分組的數(shù)目最少。 你的任務(wù)是寫(xiě)一個(gè)程序， 找出所有分組方案 中分組數(shù)最少的一種，輸出最少的分組數(shù)目。【要求 】【數(shù)據(jù)輸入 】 輸入包含多組測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)包含n+2行：第1行包括一個(gè)整數(shù)w，為每組紀(jì)念品價(jià)格之和的上限。第2行為一個(gè)整數(shù)n,表示購(gòu)來(lái)的紀(jì)念品的總件數(shù)。第3n+2行每行包含一個(gè)正整數(shù)p

50、i (5 = pi = w)，表示所對(duì)應(yīng)紀(jì)念品的價(jià)格。1 = n = 30000, 80 = w = 200【數(shù)據(jù)輸出 】對(duì)每個(gè)測(cè)試數(shù)據(jù),輸出一行,包含一個(gè)整數(shù),即最少的分組數(shù)目。 相鄰兩個(gè)測(cè)試數(shù)據(jù)間用一個(gè)空行隔開(kāi)?！緲永斎?】1009902020305060708090【樣例輸出 】Time limit: 1s Memory limit: 32768KTotal Submit : 471Accepted Submit : 325統(tǒng)計(jì)數(shù)字【問(wèn)題描述】某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò)1500000000(1.5*10A9)。已知不相同 的數(shù)不超過(guò)10000個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然

51、數(shù)各自出現(xiàn)的次數(shù)， 并按照自然數(shù)從小到大的 順序輸出統(tǒng)計(jì)結(jié)果。【要求 】【數(shù)據(jù)輸入 】包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)包含n+1行：第1行是整數(shù)n,表示自然數(shù)的個(gè)數(shù)。第2n+1行每行一個(gè)自然數(shù)。1=n=200000,每個(gè)數(shù)均不超過(guò)1 500 000 000(1.5*109)【數(shù)據(jù)輸出 】對(duì)每個(gè)測(cè)試數(shù)據(jù)輸出m行(m為n個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù)) ,按照自然數(shù) 從小到大的順序輸出。每行輸出兩個(gè)整數(shù), 分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù), 其間用一個(gè)空 格隔開(kāi)。相鄰兩個(gè)測(cè)試數(shù)據(jù)間用一個(gè)空行隔開(kāi)?！緲永斎?】8242451002100【樣例輸出 】2 34 25 1100 2Time limit: 1s Memor

52、y limit: 32768KTotal Submit : 471Accepted Submit : 325矩陣取數(shù)游戲【問(wèn)題描述】帥帥經(jīng)常跟同學(xué)玩一個(gè)矩陣取數(shù)游戲：對(duì)于一個(gè)給定的n*m的矩陣，矩陣中的每個(gè)元素aij均為非負(fù)整數(shù)。游戲規(guī)則如下：1.每次取數(shù)時(shí)須從每行各取走一個(gè)元素，共n個(gè)。m次后取完矩陣所有元素；2.每次取走的各個(gè)元素只能是該元素所在行的行首或行尾；3.每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和，每行取數(shù)的得分=被取走的元素值*2i，其中i表示第i次取數(shù)（從1開(kāi)始編號(hào)）；4.游戲結(jié)束總得分為m次取數(shù)得分之和。 帥帥想請(qǐng)你幫忙寫(xiě)一個(gè)程序，對(duì)于任意矩陣，可以求出取數(shù)后的最大得分。

53、【要求 】【數(shù)據(jù)輸入 】輸入有多個(gè)測(cè)試數(shù)據(jù)，每個(gè)包括n+1行：第1行為兩個(gè)用空格隔開(kāi)的整數(shù)n和m。第2n+1行為n*m矩陣，其中每行有m個(gè)用單個(gè)空格隔開(kāi)的非負(fù)整數(shù)。1=n, m=80, 0=aij=1000【數(shù)據(jù)輸出 】對(duì)每個(gè)數(shù)據(jù)，輸出一行，為一個(gè)整數(shù)，即輸入矩陣取數(shù)后的最大得分。相鄰兩 個(gè)輸出間用一個(gè)空行隔開(kāi)?！緲永斎?】1 44 5 0 52 1096 56 54 46 86 12 23 88 80 4316 95 18 29 30 53 88 83 64 67【樣例輸出 】122316994四塔問(wèn)題【問(wèn)題描述】“漢諾塔” ，是一個(gè)眾所周知的古老游戲。現(xiàn)在我們把問(wèn)題稍微改變一下：如果一共

54、有4根柱子， 而不是3根，那么至少需要移動(dòng)盤(pán)子多少次， 才能把所有的盤(pán)子從第1根柱子移動(dòng) 到第4根柱子上呢？ 為了編程方便，您只需要輸出這個(gè)結(jié)果mod 10000的值。要求 】數(shù)據(jù)輸入 】該題含有多組測(cè)試數(shù)據(jù)，每組一個(gè)正整數(shù)n。(0n=50000)數(shù)據(jù)輸出 】一個(gè)正整數(shù)， 表示把n個(gè)盤(pán)子從第1根柱子移動(dòng)到第4根柱子需要的最少移動(dòng) 次數(shù)mod 10000的值?！緲永斎?】15【數(shù)據(jù)輸出 】129平方數(shù)【問(wèn)題描述】給出包含M個(gè)數(shù)字的列表，和列表中所有數(shù)字的所有質(zhì)因數(shù)。求出最長(zhǎng)的子列表，使得子 列表中所有數(shù)字的乘積是一個(gè)完全平方數(shù)。【要求 】【數(shù)據(jù)輸入 】輸入文件包含多組測(cè)試數(shù)據(jù)。第一行包含兩個(gè)整

55、數(shù)N , M ( 1 = N = 30 , 1 =M = 30000 ). N是質(zhì)因數(shù)的個(gè)數(shù)。接下來(lái)一行有N個(gè)整數(shù)，給出所有的質(zhì)因數(shù)。然后一行 包含M個(gè)整數(shù)，給出列表。 輸入文件結(jié)束于N = M = 0.【數(shù)據(jù)輸出】對(duì)于每組數(shù)據(jù)，輸出最長(zhǎng)子列表的兩個(gè)位置坐標(biāo)I r。丨是該子列表在列表中的起始位置，r是結(jié)束位置。如果多種情況都滿足子列表長(zhǎng)度最大，輸出l最小的一個(gè)。如果不存在這樣的子列表輸出“None”?！緲永斎?】3 42 3 54 9 25 63 42 3 56 6 3 30 0【樣例輸出 】1 31 4【問(wèn)題描述】 給定平面上三個(gè)圓的位置， 請(qǐng)你用鋼筆在紙上畫(huà)出它們， 作圖的起點(diǎn)自定。 拿

56、起鋼筆的時(shí)候， 你不能作圖。 在畫(huà)完一個(gè)完整的圓后， 才可以接著畫(huà)另一個(gè)， 決不可半途中止去畫(huà)另一個(gè)圓 已知把鋼筆移動(dòng)一個(gè)單位距離需要一個(gè)單位時(shí)間， 拿起它則不需時(shí)間。 請(qǐng)計(jì)算畫(huà)完這三個(gè)圓 所需的最小時(shí)間。【要求 】【數(shù)據(jù)輸入 】第一行為一個(gè)正整數(shù)T(T=100)，表示測(cè)試程序的次數(shù)。接下來(lái)的T行，每一行都有9個(gè)實(shí)數(shù)x1,y1,r1,x2,y2,r2,x3,y3,r3，分別指第i(i=1,2,3)個(gè)圓的圓 心坐標(biāo)和半徑長(zhǎng)。其中，-10000=xi,yi=10000, 0ri=10000.【數(shù)據(jù)輸出 】對(duì)于每一種測(cè)試情況，輸出相應(yīng)的最小作圖時(shí)間。 【樣例輸入 】20 0 0.5 -2 0 0.5

57、 2 0 0.50 0 1 -2 2 1 2 2 1【樣例輸出 】12.42521.322埃及分?jǐn)?shù)【問(wèn)題描述】在古埃及，人們使用單位分?jǐn)?shù)的和（形如1/a的,a是自然數(shù)）表示一切有理數(shù)。如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因?yàn)榧訑?shù)中有相同的。對(duì)于一個(gè)分?jǐn)?shù)a/b，表示方法有很多種，但是哪種最好呢？ 首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個(gè)數(shù)相同的，最小的分?jǐn)?shù)越大越好。 如：19/45=1/3 + 1/12 + 1/18019/45=1/3 + 1/15 + 1/4519/45=1/3 + 1/18 + 1/30，19/45=1/4 + 1/6 + 1/18019/45=1/

58、5 + 1/6 + 1/18.最好的是最后一種，因?yàn)?/18比1/180，1/45，1/30，1/180都大。 給出a,b（0ab1000）,編程計(jì)算最好的表達(dá)方式?！疽?】【數(shù)據(jù)輸入 】第一行:N表示有N組測(cè)試數(shù)據(jù)， 每組測(cè)試數(shù)據(jù)為一行包含a,b（0ab1000）。【數(shù)據(jù)輸出 】每組測(cè)試數(shù)據(jù)若干個(gè)數(shù)，自小到大排列，依次是單位分?jǐn)?shù)的分母。【樣例輸入 】119 45【樣例輸出 】5 6 18Time Limit:1000MS Memory Limit:65536KTotal Submit:589 Accepted:34228植樹(shù)活動(dòng)【問(wèn)題描述】 春暖花開(kāi)，萬(wàn)物復(fù)蘇， 這正是植物生長(zhǎng)的好季節(jié)。

59、珠海校區(qū)舉行了一次題為 “迎 百年校慶， 添三分綠色” 的植樹(shù)活動(dòng)。這次植樹(shù)活動(dòng)的目的除了美化我們的校園， 進(jìn)一步增 強(qiáng)同學(xué)們的環(huán)保意識(shí)以外， 還在于迎接即將到來(lái)的百年校慶， 張江河副院長(zhǎng)認(rèn)為這次活動(dòng)意 義重大， 并不亞于其他大型的植樹(shù)活動(dòng)。 他希望同學(xué)們要堅(jiān)持照顧好自己所種的樹(shù)， 為它們 澆水捉蟲(chóng)，讓它們茁壯成長(zhǎng)。 師生共同植樹(shù)，打成一片。在這里我們看到的是熱情，是團(tuán) 隊(duì)合作精神， 還有同學(xué)們?yōu)閼c祝百年校慶的真誠(chéng)的心！ 經(jīng)過(guò)將近一個(gè)小時(shí)的努力， 各單位基 本上都把樹(shù)種好?？吹阶约河H手種的樹(shù)， 同學(xué)們都非常興奮， 紛紛拍照留念，記下這個(gè)難忘的時(shí)刻！同學(xué)們感嘆說(shuō)：“這次活動(dòng)很有意義啊！ ”,有的

60、同學(xué)則希望能留下一個(gè)見(jiàn)證,讓他們以后回來(lái)母校，可以看到自己的班集體種的樹(shù)，會(huì)覺(jué)得很有意義。這次植樹(shù)活動(dòng)有n個(gè)部門(mén)參加，樹(shù)種有米蘭、玉蘭，有桂花、榕樹(shù)，還有大皇椰等。每個(gè)部門(mén)分別種了m個(gè)樹(shù)種，每個(gè)樹(shù)種分別種了k1,k2,k3,km-1,km棵，現(xiàn)在有一個(gè)簡(jiǎn)單的任務(wù)， 就請(qǐng)你幫忙計(jì)算一下每個(gè)部門(mén)分別種了多少棵樹(shù)，全院一共種了多少棵樹(shù)?！疽?】【數(shù)據(jù)輸入 】所有的數(shù)據(jù)都是從鍵盤(pán)輸入，其數(shù)據(jù)格式是：第一行是參與植樹(shù)的部門(mén)數(shù)n，后面跟著的每二行是一個(gè)部門(mén)的數(shù)據(jù)， 在每一個(gè)部門(mén)的數(shù)據(jù)中， 第一行是該部門(mén)植樹(shù)的樹(shù)種 數(shù)m,第二行是m個(gè)樹(shù)種所種的棵數(shù)k1,k2,k3,km-1,km?！緮?shù)據(jù)輸出 】輸出結(jié)果為