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