1.百度語言翻譯機
百度的工程師們是非常注重效率的，在長期的開發與測試過程中，他們逐漸創造了一套獨特的縮略語。他們在平時的交談、會議，甚至在各種技術文檔中都會大量運用。
為了讓新員工可以更快地適應百度的文化，更好地閱讀公司的技術文檔，人力資源部決定開發一套專用的翻譯系統，把相關文檔中的縮略語和專有名詞翻譯成日常語言。
輸入要求：
輸入數據包含三部分：
1. 第一行包含一個整數N(N<=10000)，表示總共有多少個縮略語的詞條；
2. 緊接著有N行的輸入，每行包含兩個字符串，以空格隔開。第一個字符串為縮略語（僅包含大寫英文字符，長度不超過10字節），第二個字符串為日常語言（不包含空格，長度不超過255字節）；
3. 從第N+2開始到輸入結束為包含縮略語的相關文檔（總長度不超過1000000個字節）。例：
6
PS 門戶搜索部
NLP 自然語言處理
PM 產品市場部
HR 人力資源部
PMD 產品推廣部
MD 市場發展部
百度的部門包括PS，PM，HR，PMD，MD等等，其中PS還包括NLP小組。
樣例：in.txt
輸出要求：
輸出將縮略語轉換成日常語言后的文檔。（將縮略語轉換成日常語言，其他字符保留原樣）。例：
百度的部門包括門戶搜索部，產品市場部，人力資源部，產品推廣部，市場發展部等等，其中門戶搜索部還包括自然語言處理小組。
樣例：out.txt
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行是 a b c d 四個整數，分別表示需要點的葷菜，素菜，辛辣，清淡菜的數目。例：
3 2 2
水煮魚 30 1 1
口水雞 18 1 1
清燉豆腐 12 0 0
1 1 1 1
樣例：in.txt
輸出要求：
對于每組測試數據，輸出數據包含M+1行，前M行每行包含一個菜名（按菜名在原菜單的順序排序）。第M+1行是人均消費，結果保留兩位小數。例：
口水雞
清燉豆腐
12.00
樣例：out.txt
3.變態比賽規則
為了促進各部門員工的交流，百度舉辦了一場全公司范圍內的“拳皇”（百度內部最流行的格斗游戲）友誼賽，負責組織這場比賽的是百度的超級“拳皇”迷W.Z。W.Z不想用傳統的淘汰賽或者循環賽的方式，而是自己制定了一個比賽規則。
由于一些員工（比如同部門或者相鄰部門員工）平時接觸的機會比較多，為了促進不同部門之間的交流，W.Z希望員工自由分組。不同組之間的每兩個人都會進行一場友誼賽而同一組內的人之間不會打任何比賽。
比如4個人，編號為1~4,如果分為兩個組并且1，2一個組，3，4一個組，那么一共需要打四場比賽：1 vs 3，1 vs 4，2 vs 3，2 vs 4。而如果是1，2，3一組，4單獨一組，那么一共需要打三場比賽: 1 vs 4，2 vs 4，3 vs 4。
很快W.Z意識到，這樣的比賽規則可能會讓比賽的場數非常多。W.Z想知道如果有N個人，通過上面這種比賽規則，總比賽場數有可能為K場嗎？比如3個人，如果只分到一組則不需要比賽，如果分到兩組則需要2場比賽，如果分為三組則需要3場比賽。但是無論怎么分都不可能恰需要1場比賽。
相信作為編程高手的你一定知道該怎么回答這個問題了吧？那么現在請你幫助W.Z吧。
輸入要求：
每行為一組數據，包含兩個數字 N, K(0<N<=500, K>=0)。例：
2 0
2 1
3 1
3 2
樣例：in.txt
輸出要求：
對輸入的N,K 如果N個員工通過一定的分組方式可以使比賽場數恰好為K，則輸出"YES"，否則輸出"NO"（請全部使用大寫字母），每組數據占一行。例：
YES
YES
NO
YES
樣例：out.txt
4.蟈蟈計分
蟈蟈小朋友剛剛學會了0~9這十個數字,也跟爸爸媽媽來參加百度每周進行的羽毛球活動。但是他還沒有球拍高，于是大人們叫他記錄分數。聰明的蟈蟈發現只要記錄連續得分的情況就可以了，比如用“3 2 4”可以表示一方在這一局中連得三分后，輸了兩分，接著又連得到四分。可是，后來大人們發現蟈蟈只會用0~9這十個數字，所以當比賽選手得分超過9的時候，他會用一個X來表示10完成記分。但問題是，當記錄為“X 3 5”的時候，蟈蟈自己也記不起來是一方連續得到十三分后，再輸五分；還是先贏十分輸三分再贏五分。
因為百度內部就要開始進行羽毛球聯賽了，要先摸清大家的實力才好分組比賽呢～于是，大人們想知道以前每局的比分是怎樣的，以及誰獲得了勝利。要是遇到了根據比賽記錄無法確認比賽過程的情況，也要輸出相應的提示哦。
需要進一步說明的是，比賽是五局三勝的，每局先獲得二十一分的為勝，但是勝方必須領先對手兩分或以上，否則必須繼續比賽直到一方超出對手兩分為止，比分多的一方獲勝。任何一方先獲勝三局后就獲得最終勝利，比賽也相應的結束。而且蟈蟈保證是完整的無多余信息的記錄了比賽。
輸入要求：
1．文件中第一行只有一個整數M，表示蟈蟈記錄了多少場比賽的分數；
2．在接下來的2M行里，每場比賽用兩行記錄，第一行是一個整數N(N<=1000)表示當前這個記錄中有多少個字符，第二行就是具體的N個字符表示記錄的分數（相鄰字符用空格隔開）。例：
3
23
9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1
25
9 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4
43
7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1
樣例：in.txt
輸出要求：
對應每一個分數記錄，輸出相應的每局分數，每局分數都使用兩個整數表示，表示兩個選手的得分，中間用":"分隔開；每組分數記錄間使用一個空行分隔開。如果相應的比賽結果無法預測，以“UNKNOWN”一個單詞獨占一行表示（請全部使用大寫字母）。例：
21:17
24:22
21:3
UNKNOWN
21:14
20:22
21:23
21:16
21:9
樣例：out.txt
5.座位調整
百度辦公區里到處擺放著各種各樣的零食。百度人力資源部的調研發現，員工如果可以在自己喜歡的美食旁邊工作，效率會大大提高。因此，百度決定進行一次員工座位的大調整。
調整的方法如下：
1．首先將辦公區按照各種零食的擺放分成N個不同的區域（例如：可樂區，餅干區，牛奶區等等）；
2．每個員工對不同的零食區域有不同的喜好程度（喜好程度是1~100的整數，喜好程度越大表示該員工越希望被調整到相應的零食區域）；
3．由于每個零食區域可以容納的員工數量有限，人力資源部希望找到一個最優的調整方案使得總的喜好程度最大。
輸入要求：
文件第一行包含兩個整數N，M(N>=1，M<=300)。分別表示N個區域和M個員工；
第二行是N個整數構成的數列a，其中a[i]表示第i個區域可以容納的員工數(1<=a[i]<=M，a[1]+a[2]+...+a[N]=M)；
緊接著是一個M*N的矩陣P，P(i,j)表示第i個員工對第j個區域的喜好程度。例：
3 3
1 1 1
100 50 25
100 50 25
100 50 25
樣例：in.txt
輸出要求：
對于每個測試數據，輸出可以達到的最大的喜好程度。例：
175
樣例：out.txt
數據解釋：
此數據只存在一種安排方法，三個員工分別安置在三個區域。最終的喜好程度為100+50+25=175
6.剪刀石頭布
N個小孩正在和你玩一種剪刀石頭布游戲（剪刀贏布，布贏石頭，石頭贏剪刀）。N個小孩中有一個是裁判，其余小孩分成三組（不排除某些組沒有任何成員的可能性），但是你不知道誰是裁判，也不知道小孩們的分組情況。然后，小孩們開始玩剪刀石頭布游戲，一共玩M次，每次任意選擇兩個小孩進行一輪，你會被告知結果，即兩個小孩的勝負情況，然而你不會得知小孩具體出的是剪刀、石頭還是布。已知各組的小孩分別只會出一種手勢（因而同一組的兩個小孩總會是和局），而裁判則每次都會隨便選擇出一種手勢，因此沒有人會知道裁判到底會出什么。請你在M次剪刀石頭布游戲結束后，猜猜誰是裁判。如果你能猜出誰是裁判，請說明最早在第幾次游戲結束后你就能夠確定誰是裁判。
輸入要求：
輸入文件包含多組測試數據，每組測試數據第一行為兩個整數N和M(1<=N<=500，0<M<=2000)，分別為小孩的個數和剪刀石頭布游戲進行的次數。接下來M行，每行兩個整數且中間以一個符號隔開。兩個整數分別為進行游戲的兩個小孩各自的編號（為小于N的非負整數）。符號的可能值為“=”、“>”和“<”，分別表示和局、第一個小孩勝和第二個小孩勝三種情況。例：
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0
樣例：in.txt
輸出要求：
1．每組測試數據輸出一行，若能猜出誰是裁判，則輸出裁判的編號，并輸出在第幾次游戲結束后就能夠確定誰是裁判，小孩的編號和游戲次數以一個空格隔開；
2．如果無法確定誰是裁判，輸出-2；如果發現剪刀石頭布游戲的勝負情況不合理（即無論誰是裁判都會出現矛盾），則輸出-1。例：
-2
1 4
-1
0 0
程序之美”-百度之星程序設計大賽 - 題目
第一題（共四題100分）：連續正整數（10分）
題目描述：
一個正整數有可能可以被表示為n(n>=2)個連續正整數之和，如：
15=1+2+3+4+5
15=4+5+6
15=7+8
請編寫程序，根據輸入的任何一個正整數，找出符合這種要求的所有連續正整數序列。
輸入數據：
一個正整數，以命令行參數的形式提供給程序。
輸出數據：
在
標準輸出上打印出符合題目描述的全部正整數序列，每行一個序列，每個序列都從該序列的最小正整數開始、以從小到大的順序打印。如果結果有多個序列，按各序
列的最小正整數的大小從小到大打印各序列。此外，序列不允許重復，序列內的整數用一個空格分隔。如果沒有符合要求的序列，輸出“NONE”。
例如，對于15，其輸出結果是：
1 2 3 4 5
4 5 6
7 8
對于16，其輸出結果是：
NONE
評分標準：
程序輸出結果是否正確。
第二題（共四題100分）：重疊區間大小（20分）
題目描述：
請編寫程序，找出下面“輸入數據及格式”中所描述的輸入數據文件中最大重疊區間的大小。
對一個正整數n，如果n在數據文件中某行的兩個正整數（假設為A和B）之間，即A<=n<=B或A>=n>=B，則n屬于該行；如果n同時屬于行i和j，則i和j有重疊區間；重疊區間的大小是同時屬于行i和j的整數個數。
例如，行（10 20）和（12 25）的重疊區間為[12 20]，其大小為9；行（20 10）和（12 18）的重疊區間為[10 12]，其大小為3；行(20 10)和（20 30）的重疊區間大小為1。
輸入數據：
程
序讀入已被命名為input.txt的輸入數據文本文件，該文件的行數在1到1,000,000之間，每行有用一個空格分隔的2個正整數，這2個正整數的
大小次序隨機，每個數都在1和2^32-1之間。（為便于調試，您可下載測試input.txt文件，實際運行時我們會使用不同內容的輸入文件。）
輸出數據：
在標準輸出上打印出輸入數據文件中最大重疊區間的大小，如果所有行都沒有重疊區間，則輸出0。
評分標準：
程序輸出結果必須正確，內存使用必須不超過256MB，程序的執行時間越快越好。
第三題（共四題100分）：字符串替換（30分）
題目描述：
請編寫程序，根據指定的對應關系，把一個文本中的字符串替換成另外的字符串。
輸入數據：
程
序讀入已被命名為text.txt和dict.txt的兩個輸入數據文本文件，text.txt為一個包含大量字符串（含中文）的文本，以
whitespace為分隔符；dict.txt為表示字符串（s1）與字符串（s2）的對應關系的另一個文本（含中文），大約在1萬行左右，每行兩個字
符串（即s1和s2），用一個\t或空格分隔。dict.txt中各行的s1沒有排序，并有可能有重復，這時以最后出現的那次s1所對應的s2為準。
text.txt和dict.txt中的每個字符串都可能包含除whitespace之外的任何字符。text.txt中的字符串必須和dict.txt
中的某s1完全匹配才能被替換。（為便于調試，您可下載測試text.txt和dict.txt文件，實際運行時我們會使用不同內容的輸入文件。）
輸出數據：
在標準輸出上打印text.txt被dict.txt替換后了的整個文本。
評分標準：
程序輸出結果必須正確，內存使用越少越好，程序的執行時間越快越好。
第四題（共四題100分）：低頻詞過濾（40分）
題目描述：
請編寫程序，從包含大量單詞的文本中刪除出現次數最少的單詞。如果有多個單詞都出現最少的次數，則將這些單詞都刪除。
輸入數據：
程序讀入已被命名為corpus.txt的一個大數據量的文本文件，該文件包含英文單詞和中文單詞，詞與詞之間以一個或多個whitespace分隔。（為便于調試，您可下載測試corpus.txt文件，實際運行時我們會使用不同內容的輸入文件。）
輸出數據：
在標準輸出上打印刪除了corpus.txt中出現次數最少的單詞之后的文本（詞與詞保持原來的順序，仍以空格分隔）。
評分標準：
程序輸出結果必須正確，內存使用越少越好，程序的執行時間越快越好。
第一題（共兩題100分）站點統計（50分）
題目描述：
一個Internet站點集合，可以用如下的方式來描述站點和站點之間的鏈接引用關系：
s 1 2 3 4
1 / 4 0 3
2 3 / 4 5
3 2 2 / 2
4 6 1 4 /
其中與s(site)同行和同列的數字都表示站點號，其他每個數字表示一個站點到另一個站
點的超文本鏈接數。如果站點A有到另一個站點B的直接鏈接或間接（指通過一個或多個
直接鏈接）鏈接，則稱站點A有到站點B的訪問關系，或稱站點B可以被站點A訪問到。例
如，上面描述了一個有4個站點鏈接關系的站點集合，第一行 / 4 0 3 表示站點1到站點
1，2，3，4的超文本鏈接數。
請編寫程序:
1） 將一個有N個站點的集合劃分成滿足下面所有條件的站點子集（這些子集的union組
成了該N個站點集合）：
a) 當任一子集中的站點數大于1時，該子集內至少存在一個站點有到該子集內所有
其他站點的訪問關系；
b) 當任一子集中的站點數大于1時，該子集內的任一站點至少可以被該子集內的某
一站點訪問到；
c) 兩個不同子集中的任意兩個站點之間不存在任何訪問關系。
2） 裁減這些子集內的站點之間現有的鏈接關系，使得被裁減后的各子集內的站點依然
可以滿足上述所有條件，同時使得子集內的站點之間的鏈接總數相加之和為最小。
假如上面的站點集合是這N個站點集合中的一個子集，它滿足了條件a)：4可以訪問到3，
也可以訪問到2和1；也滿足了條件b)：站點4可以被站點3訪問到，等等。對該站點集合
進行裁減使其仍然滿足條件a和b，并使得其鏈接總數之和為最小的結果為：
s 1 2 3 4
1 / 0 0 0
2 0 / 0 0
3 2 0 / 2
4 0 1 4 /
這里，站點4可以訪問到站點3和2，站點4也可以訪問到站點1（通過站點3間接訪問）；
此外，站點3可以訪問到站點4；最小鏈接總數相加為2＋2＋1＋4=9。
輸入數據：
程序讀入已被命名為sites.txt的完全如上所示的N*N矩陣的輸入數據文本文件，N不大于
10萬（N即為行數和列數），輸入文件的每一行的列和列之間用一個\\t分隔，行和行之
間用\\n分隔。
輸出數據：
按行輸出滿足題目要求的每個子集內的站點數以及裁減后的最小鏈接總數之和，數和數
之間都以一個空格分隔。如上述子集和最小鏈接總數為：
1 2 3 4 9
如果輸入數據無滿足題目要求的子集存在，則輸出NONE。
評分標準：
在結果正確的前提下，會考慮程序的運行時間。我們會用兩個不同的輸入數據文件（一
個簡單一個復雜）進行測試，簡單的輸入數據產生的程序輸出結果如果正確，獲該題滿
分的30%即15分（不處理運行時間，除非因程序錯誤引起的超時運行）；復雜的輸入數據
產生的程序輸出結果如果正確，獲50%即25分，運行時間滿分為20%即10分，按各自程序
的運行時間在所有參賽選手的程序的運行時間中所占位置獲得相應比例。請仔細閱讀并
遵守"輸入數據"和"輸出數據"中的格式要求，如不符合要求，我們的自動評分程序可能
會判定程序不正確。
第二題（共兩題100分）決策系統（50分）
題目描述：
一個智能決策系統可以由規則庫和事實庫兩部分組成，假定規則庫的形式為：
Ri C1 & C2 & … & Cn->A
表示在條件C1，C2，… 和Cn都滿足的前提下，結論A成立（即采取行動A）；Ri表示這是
規則庫中的第i條規則。事實庫則由若干為真的條件（即命題）所組成。
對一個新的待驗證的命題Q，可使用數據驅動或目標驅動兩種推理方式之一，來確認它是
否可由某規則庫和事實庫推出：
1） 數據驅動的推理是指從事實庫開始，每次試圖發現規則庫中某條能滿足所有條件的
規則，并將其結論作為新的事實加入事實庫，然后重復此過程，直至發現Q是一個事實或
沒有任何新的事實可被發現；
2） 目標驅動的推理是指從目標假設Q出發，每次試圖發現規則庫中某條含該假設的規
則，然后將該規則的前提作為子目標，確認這些子目標是否和事實庫中的事實相匹配，
如果沒有全部匹配，則重復此過程，直至發現新的子目標都為真或不能再驗證子目標是
否為真。
例如，一個規則庫為：
R1 X & B & E -> Y
R2 Y & D -> Z
R3 A->X
事實庫為：
A
B
C
D
E
如果想知道命題Z是否為真，數據驅動的推理是從A B C D E開始，依次匹配規則R3（得
到新事實X），R1（得到新事實Y）和R2，得到Z為真的事實；目標驅動的推理是從假設目
標Z開始，依次匹配規則R2（得到新的子目標Y），R1（得到新的子目標X）和R3，得到假
設Z為真的結論。
請編寫程序正確、高效的實現這兩種推理方式。
輸入數據：
程序需要兩個命令行參數：
1） <推理方式>：data|goal，分別表示程序應采用數據驅動的推理或目標驅動的推理；
2） <命題>：如Z。
此外，程序還需讀入已被命名為rules.txt的規則庫和已被命名為facts.txt的事實庫。
規則庫中的規則可能在千量級，按R1,R2,R3…依次按行排列的，每行一條規則，每條規
則都以Ri C1 & C2 & … & Cn->A的形式表示，Ri和C1之間有1個或多個空格，Ci和&之
間，Cn和->之間，以及->和A之間可以有0或多個空格。事實庫中的各事實之間用1個\\n
隔開，每行一個事實。
輸出數據：
如果Z能被推理為真，則輸出：
TRUE <推理方式：data或goal> <用空格隔開的規則序列：以在所輸入的推理方式下，推
出該命題為真的規則被激活的順序排列>
例如：TRUE goal R2 R1 R3
如果Z不能被推理為真，輸出：
UNCERTAIN
評分標準：
在結果正確的前提下，會考慮程序的運行時間。我們會用兩組不同的輸入數據文件（一
個簡單一個復雜）進行測試，簡單的輸入數據產生的程序輸出結果如果正確，獲該題滿
分的20%即10分（不處理運行時間，除非因程序錯誤引起的超時運行）；復雜的輸入數據
產生的程序輸出結果如果正確，獲40%即20分，運行時間滿分為40%即20分，按各自程序
的運行時間在所有參賽選手的程序的運行時間中所占位置獲得相應比例。兩種推理方式
各占一半的分數。請仔細閱讀并遵守"輸入數據"和"輸出數據"中的格式要求，如不符合
要求，我們的自動評分程序可能會判定程序不正確。
題目描述：
八方塊移動游戲要求從一個含8個數字（用1-8表示）的方塊以及一個空格方塊（用0表示）的3x3矩陣的起始狀態開始，不斷移動該空格方塊以使其和相鄰的方塊互換，直至達到所定義的目標狀態。空格方塊在中間位置時有上、下、左、右4個方向可移動，在四個角落上有2個方向可移動，在其他位置上有3個方向可移動。例如，假設一個3x3矩陣的初始狀態為：
8 0 3
2 1 4
7 6 5
目標狀態為：
1 2 3
8 0 4
7 6 5
則一個合法的移動路徑為：
8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5
另外，在所有可能的從初始狀態到目標狀態的移動路徑中，步數最少的路徑被稱為最短路徑；在上面的例子中，最短路徑為5。如果不存在從初試狀態到目標狀態的任何路徑，則稱該組狀態無解。
請設計有效的（細節請見評分規則）算法找到從八方塊的某初試狀態到某目標狀態的所有可能路徑中的最短路徑，并用C/C++實現。
輸入數據：
程序需讀入已被命名為start.txt的初始狀態和已被命名為goal.txt的目標狀態，這兩個文件都由9個數字組成（0表示空格，1-8表示8個數字方塊），每行3個數字，數字之間用空格隔開。
輸出數據：
如果輸入數據有解，輸出一個表示最短路徑的非負的整數；如果輸入數據無解，輸出-1。
自測用例：
如果輸入為：start.txt和goal.txt，則產生的輸出應為：
5
又例，如果用
7 8 4
3 5 6
1 0 2
替換start.txt中的內容，則產生的輸出應為：
21
評分規則：
1）我們將首先使用和自測用例不同的10個start.txt以及相同的goal.txt，每個測試用例的運行時間在一臺Intel Xeon 2.80GHz 4 CPU/6G 內存的Linux機器上應不超過10秒（內存使用不限制），否則該用例不得分；
2）每個選手的總分（精確到小數點后6位）=10秒鐘內能產生正確結果的測試用例數量x10+（1/產生這些正確結果的測試用例的平均運行毫秒)；
3）如果按此評分統計仍不能得出總決賽將決出的一、二、三等獎共計九名獲獎者，我們將先設N=2，然后重復下述過程直至產生最高的9位得分：用隨機生成的另外10個有解的start.txt再做測試，并對這10*N個測試用例用2）中公式重新計算總分，N++。