Astar2006百度之星程序設計大賽題目1.百度語言翻譯機百度的工程師們是特別著重效率的，在長久的開發與測試過程中，他們漸漸創建了一套獨到的縮略語。他們在平常的談話、會議，甚至在各種技術文檔中都會大批運用。為了讓新職工能夠更快地適應百度的文化，更好地閱讀企業的技術文檔，人力資源部決定開發一套專用的翻譯系統，把有關文檔中的縮略語和專出名詞翻譯成平常語言。輸入要求：輸入數據包含三部分：第一行包含一個整數N(N<=10000)，表示總合有多少個縮略語的詞條；緊接著有N行的輸入，每行包含兩個字符串，以空格分開。第一個字符串為縮略語（僅包含大寫英文字符，長度不超出10字節），第二個字符串為平常語言（不包含空格，長度不超出255字節）；3.從第N+2開始到輸入結束為包含縮略語的有關文檔（總長度不超出1000000個字節）。例：6PS門戶搜尋部NLP自然語言辦理PM產品市場部HR人力資源部PMD產品推行部MD

市場發展部百度的部門包含PS，PM，HR，PMD，MD等等，此中PS還包含NLP小組。樣例：in.txt輸出要求：輸出將縮略語變換成平常語言后的文檔。（將縮略語變換成平常語言，其余字符保存原樣）例：

。百度的部門包含門戶搜尋部，產品市場部，人力資源部，產品推行部，市場發展部等等，其中門戶搜尋部還包含自然語言辦理小組。樣例：out.txt評分規則：1．程序將運轉在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運轉不可以超出10秒，不然該用例不得分；2．要求程序能依據輸入樣例的格式讀取數據文件，依據輸出樣例的格式將運轉結果輸出到標準輸出上。假如不可以正確讀入數據和輸出數據，該題將不得分；3．該題目共有4個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分數的比率分別為25%，25%，25%，25%；4．該題目20分。注意事項：1．輸入數據是中英文混淆的，中文采納GBK編碼。GBK：是又一個漢字編碼標準，全稱《漢字內碼擴展規范》。采納雙字節表示，整體編碼范圍為8140-FEFE，首字節在81-FE之間，尾字節在40-FE之間，清除xx7F。總計23940個碼位，共收入21886個漢字和圖形符號，此中漢字（包含部首和構件）21003個，圖形符號883個。2．為保證答案的獨一性，縮略語的變換采納正向最大般配（從左到右為正方向）原則。請注意樣例中PMD的翻譯。2.飯團的煩憂“午飯飯團”是百度內部參加人數最多的民間組織。同一個部門的、同一所大學的、同一年出生的、使用同一種型號電腦的職工們老是以各種理由組織各種長久的、暫時的飯團。參加飯團，不單能夠以優惠的價錢嘗到更為豐富的菜式，還能夠在吃飯的時候和同事們增進感情。但是，跟著百度的職工愈來愈多，各個飯團的管理變得繁瑣起來。特別是為了照料職工們越來越挑剔的胃，飯團的點菜負責人的壓力也愈來愈大。此刻，這個任務就交給“百度之星”了，因為，你將要為所有的百度飯團設計一個自動點菜的算法。飯團點菜的需求以下：1．經濟是我們要考慮的一個要素，既要充分利用百度職工的午飯補貼，又不可以鋪張浪費。所以，我們希望最后的人均花費越靠近12元越好。2．菜式豐富是我們要考慮的另一個要素。

為簡單起見，我們將各種菜肴的屬性歸納為葷菜，素菜，辛辣，平淡，并且每個菜只好點一次。3．請牢記，百度飯團在各大餐館享受

8折優惠。輸入要求：1．輸入數據第一行包含三個整數

N，M，K(0<N<=16

，0<M<=N

，0<K<=12)

，分別表示菜單上菜的數目，飯團需重點的菜的數目，就餐的人數；2．緊接著N行，每行的格式以下：菜名（長度不超出20個字符）價錢（原價，整數）辛辣（1表示是，0表示否）；

能否葷菜（

1表示是，

0表示否）能否3．第N+2行是abcd四個整數，分別表示需重點的葷菜，素菜，辛辣，平淡菜的數目。例：322水煮魚3011口水雞1811清燉豆腐12001111樣例：in.txt輸出要求：關于每組測試數據，輸出數據包含M+1行，前M行每行包含一個菜名（按菜名在原菜單的次序排序）。第M+1行是人均花費，結果保存兩位小數。例：口水雞清燉豆腐12.00樣例：out.txt評分規則：1．程序將運轉在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運轉不可以超出10秒，不然該用例不得分；2．要求程序能依據輸入樣例的格式讀取數據文件，依據輸出樣例的格式將運轉結果輸出到標準輸出上。假如不可以正確讀入數據和輸出數據，該題將不得分；3．該題目共有5個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分數的比率分別為20%，20%，20%，20%，20%；4．該題目10分。3.變態競賽規則為了促使各部門職工的溝通，百度舉辦了一場全企業范圍內的“拳皇”（百度內部最流行的格斗游戲）友情賽，負責組織這場競賽的是百度的超級“拳皇”迷W.Z。W.Z不想用傳統的裁減賽或許循環賽的方式，而是自己擬訂了一個競賽規則。因為一些職工（比方同部門或許相鄰部門職工）平常接觸的時機比許多，為了促使不一樣部門之間的溝通，W.Z希望職工自由分組。不一樣組之間的每兩個人都會進行一場友情賽而同一組內的人之間不會打任何競賽。比方4個人，編號為1~4,假如分為兩個組并且1，2一個組，3，4一個組，那么一共需要打四場競賽：1vs3，1vs4，2vs3，2vs4。而假如是1，2，3一組，4單獨一組，那么一共需要打三場競賽:1vs4，2vs4，3vs4。很快W.Z意識到，這樣的競賽規則可能會讓競賽的場數特別多。W.Z想知道假如有N個人，經過上邊這類競賽規則，總競賽場數有可能為K場嗎？比方3個人，假如只分到一組則不需要競賽，假如分到兩組則需要2場競賽，假如分為三組則需要3場競賽。但是不論怎么分都不行能恰需要1場競賽。相信作為編程能手的你必定知道該怎么回答這個問題了吧？那么此刻請你幫助W.Z吧。輸入要求：每行為一組數據，包含兩個數字N,K(0<N<=500,K>=0)。例：20213132樣例：in.txt輸出要求：對輸入的N,K假如N個職工經過必定的分組方式能夠使競賽場數恰巧為K，則輸出"YES"，不然輸出"NO"（請所有使用大寫字母），每組數據占一行。例：YESYESNOYES樣例：out.txt評分規則：1．程序將運轉在一臺Linux機器上（內存使用不作嚴格限制），在每一測試數據集上運轉不可以超出10秒，不然該用例不得分；2．要求程序能依據輸入樣例的格式讀取數據文件，依據輸出樣例的格式將運轉結果輸出到標準輸出上。假如不可以正確讀入數據和輸出數據，該題將不得分；3．該題目共有3個測試數據集，每個測試數據集為一個輸入文件。各測試數據集占該題目分數的比率分別為30%，30%，40%；4．該題目20分。4.蟈蟈計分蟈蟈小朋友剛才學會了0~9這十個數字,也跟爸爸媽媽來參加百度每周進行的羽毛球活動。但是他還沒有球拍高，于是大人們叫他記錄分數。聰慧的蟈蟈發現只需記錄連續得分的狀況便可以了，比方用“324”能夠表示一方在這一局中連得三分后，輸了兩分，接著又連獲取四分。但是，以后大人們發現蟈蟈只會用0~9這十個數字，所以當競賽選手得分超出9的時候，他會用一個X來表示10達成記分。但問題是，當記錄為“X35”的時候，蟈蟈自己也記不起來是一方連續獲取十三分后，再輸五分；仍是先贏十分輸三分再贏五分。因為百度內部就要開始進行羽毛球聯賽了，要先摸清大家的實力才好分組競賽呢～于是，大人們想知道從前每局的比分是如何的，以及誰獲取了成功。假如碰到了依據競賽記錄沒法確認比勝過程的狀況，也要輸出相應的提示哦。需要進一步說明的是，競賽是五局三勝的，每局先獲取二十一分的為勝，但是勝方一定當先敵手兩分或以上，不然一定持續競賽直到一方高出敵手兩分為止，比分多的一方獲勝。任何一方先獲勝三局后就獲取最后成功，競賽也相應的結束。并且蟈蟈保證是完好的無剩余信息的記錄了競賽。輸入要求：1．文件中第一行只有一個整數M，表示蟈蟈記錄了多少場競賽的分數；2．在接下來的2M行里，每場競賽用兩行記錄，第一行是一個整數N(N<=1000)表示目前這個記錄中有多少個字符，第二行就是詳細的N個字符表示記錄的分數（相鄰字符用空格隔開）。例：323973624783279X22121X1X11259385483984XXXX2XXXX28492443樣例：in.txt輸出要求：對應每一個分數記錄，輸出相應的每局分數，每局分數都使用兩個整數表示，表示兩個選手的得分，中間用":"分分開；每組分數記錄間使用一個空行分分開。假如相應的競賽結果無法展望，以“UNKNOWN”一個單詞獨占一行表示（請所有使用大寫字母）。例：21:1724:2221:3UNKNOWN21:1420:2221:2321:1621:9樣例：out.txt評分規則：1．程序將運轉在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運轉不可以超出10秒，不然該用例不得分；2．要求程序能依據輸入樣例的格式讀取數據文件，依據輸出樣例的格式將運轉結果輸出到標準輸出上。假如不可以正確讀入數據和輸出數據，該題將不得分；3．該題目共有4個測試數據集，每個測試數據集為一個輸入文件。各測試數據集占該題目分數的比率分別為20%，30%，40%，10%；4．該題目10分。5.座位調整百度辦公區里各處擺放著各種各種的零食。百度人力資源部的調研發現，職工假如能夠在自己喜愛的美食旁邊工作，效率會大大提升。所以，百度決定進行一次職工座位的大調整。調整的方法以下：1．第一將辦公區依據各種零食的擺放分紅

N個不一樣的地區（比如：可樂區，餅干區，牛奶區等等）；2．每個職工對不一樣的零食地區有不一樣的愛好程度（愛好程度是大表示該職工越希望被調整到相應的零食地區）；

1~100的整數，愛好程度越3．因為每個零食地區能夠容納的職工數目有限，人力資源部希望找到一個最優的調整方案使得總的愛好程度最大。輸入要求：文件第一行包含兩個整數N，M(N>=1，M<=300)第二行是N個整數組成的數列a，此中a[i]表示第

。分別表示N個地區和Mi個地區能夠容納的職工數

個職工；(1<=a[i]<=M

，a[1]+a[2]+...+a[N]=M)緊接著是一個M*N

；的矩陣

P，P(i,j)表示第

i個職工對第

j個地區的愛好程度。例：311502550251005025樣例：in.txt輸出要求：關于每個測試數據，輸出能夠達到的最大的愛好程度。例：175樣例：out.txt數據解說：此數據只存在一種安排方法，三個職工分別布置在三個地區。最后的愛好程度為100+50+25=175評分規則：1．程序將運轉在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運轉不可以超出10秒，不然該用例不得分；2．要求程序能依據輸入樣例的格式讀取數據文件，依據輸出樣例的格式將運轉結果輸出到標準輸出上。假如不可以正確讀入數據和輸出數據，該題將不得分；3．該題目共有4個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分數的比率分別為25%，25%，25%，25%；4．該題目20分。6.剪刀石頭布N個兒童正在和你玩一種剪刀石頭布游戲（剪刀贏布，布贏石頭，石頭贏剪刀）。N個兒童中有一個是裁判，其余兒童分紅三組（不清除某些組沒有任何成員的可能性），但是你不知道誰是裁判，也不知道兒童們的分組狀況。而后，兒童們開始玩剪刀石頭布游戲，一共玩M次，每次隨意選擇兩個兒童進行一輪，你會被見告結果，即兩個兒童的輸贏狀況，但是你不會得悉兒童詳細出的是剪刀、石頭仍是布。已知各組的兒童分別只會出一種手勢（因此同一組的兩個兒童總會是和局），而裁判則每次都會隨意選擇出一種手勢，所以沒有人會知道裁判究竟會出什么。請你在M次剪刀石頭布游戲結束后，猜猜誰是裁判。假如你能猜出誰是裁判，請說明最早在第幾次游戲結束后你便可以確立誰是裁判。輸入要求：輸入文件包含多組測試數據，每組測試數據第一行為兩個整數N和M(1<=N<=500，0<M<=2000)，分別為兒童的個數和剪刀石頭布游戲進行的次數。接下來M行，每行兩個整數且中間以一個符號分開。兩個整數分別為進行游戲的兩個兒童各自的編號（為小于N的非負整數）。符號的可能值為“=”“、>”和“<”分別表示和局、第一個兒童勝和第二個兒童勝，三種狀況。例：30<11<22<050<10>11<21>20<240<10>12<32>310樣例：in.txt輸出要求：1．每組測試數據輸出一行，若能猜出誰是裁判，則輸出裁判的編號，并輸出在第幾次游戲結束后便可以確立誰是裁判，兒童的編號和游戲次數以一個空格分開；2．假如沒法確立誰是