「一家人」杯程式設計競賽 文字版題目

（文字版題目用於沒法檢視 PDF 版本題目者使用。能檢視 PDF 版本的，請不要檢視該版本。）

夢境奇遇 第一屆「一家人」杯程式設計競賽

(2010年6月6日，14:30:00 – 17:40:00)

出題人：Ceeji & LXYXYNT

審題人：LXYXYNT & Ceeji

特別說明：

一、檔名（程式名和輸入輸出檔名）必須使用小寫。
二、C/C++中函式main()的返回值型別必須是int，程式正常結束時的返回值必須是0。
三、統一評測時採用的機器參考配置為：CPU AMD 2.7GHz 雙核，記憶體 2 GB，使用虛擬機器環境測試。
四、關於使用Pascal語言與編譯結果的說明
1．對於Pascal語言的程式，當使用IDE和fpc編譯結果不一致時，以fpc的編譯結果為準。
2．允許使用數學庫(uses math子句)，以及ansistring。但不允許使用編譯開關（最後測試時pascal的範圍檢查開關預設關閉：{$R-,Q-,S-}），也不支援與最佳化相關的選項。
五、關於C++語言中模板使用的限制說明
不限制使用標準庫演算法和各種標頭檔案。

六、請使用「\n」作為 C/C++語言的換行符**。**

0**．**前言

夢這個字，無疑在每個人心目中都是重要的。從小，父母和社會就給我們灌輸「要樹立遠大理想」的號召，然而對於夢，我們印象最深的，恐怕卻是睡覺中實際所做的一個個夢境。在夢境中，我們可以實現自己多年的渴望。

俗話說，「日有所思，夜有所夢」。但是，在很多情況下，常常是「日有所思而不得，夜有所夢而無緣」。有一首詩這樣寫：

在夢中，我回到了遠古，

沒有地溝油，也沒有三聚氰胺，

沒有考試和競賽，也沒有下崗，

沒有高樓大廈，也進不了富士康，

有的，只是山水的旖旎，和你的溫柔。

就這樣，幸福

卻被寫模擬賽的鬧鐘驚醒

——Ceeji

1**．**排隊出發

(1.pas/c/cpp | 記憶體 128 MB)

【問題描述】

神牛島是傳說中的一個島嶼，凡是成功到那裡遊歷，完成探險並返回的人，都會成為神牛。但是，現實中卻沒有人知道如何到達神牛島。

這天夜裡，篤志者睡著之後，不久就進入了夢鄉。他突然看到有人在問，「有人想去神牛島的嗎？」神牛島之旅的牌子前，就開始有不少勇士報名要去冒險探索。

「我們會把勇士安排在前，帶領大家一起去神牛島。下面開始點名！」管理隊伍的LXY神牛說。其實說實話，給學生排隊這種工作是最讓神牛頭疼的了。因為同學們都有自尊心，都不願意排後面。共有n個同學要排成一列，每個同學有兩個屬性：影響力和承受能力。給一個同學造成的心理創傷指數等於所有在他前面同學的影響力之和減去他的承受能力。現在請你幫忙安排一下點名順序，儘量使受到心理創傷最大的同學少受創傷。

【輸入】

輸入檔案1.in包含_n_+1行：

第1行是整數_n_，表示同學的個數。

第2~n+1行每行兩個自然數，分別是該同學的影響力和承受能力。

【輸出】

輸出檔案1.out包含1行，為你安排的順序中受到心理創傷最大的同學受到的創傷。

【輸入輸出樣例】

1.in

1.out

3

10 3

2 5

3 3

2

【資料規模】

對於100％的資料，1<=n<=50000，1<=影響力<=10000，1<=承受能力<=1,000,000,000。

2**．自動做作業機**

(2.pas/c/cpp | 記憶體 128 MB)

【問題描述】

就在大家要出發的那一刻，篤志者想起昨天的作業還沒有寫完…為了解決這個問題，神牛給篤志者和其它有類似情況的人們準備了一個新發明：自動做作業機。這項發明能夠幫助大家做作業。。但是它非常非常非常費電。如果大家都毫無節制的用的話，很快就會因為用電嚴重超標而無法繼續。因此在用之前，你必須想辦法最小化耗電量。

假設現在有N項作業，每項作業會有兩個關鍵字Ti(耗時)和Fi(重要度)，我們所要做的是將作業分成若干塊（順序不能改變）依次給機器去做。每一塊中作業的完成時間為這一塊中所有作業完成的時間，而每一塊開始前必須有S的時間讓機器準備啟動。做作業機的耗電量就等於每項作業的完成時間乘以重要度之和。這次任務必須在0.2秒內解決。

【輸入】

輸入檔案2.in的第一行為N，為作業的個數。

第二行為S，為準備時間。

接下來有N行，第i+2行為兩個整數：Ti和Fi。

【輸出】

輸出檔案2.out只有一行，為做作業機的最小耗電量。

【輸入輸出樣例】

2.in

2.out

5

1

1 3

3 2

4 3

2 3

1 4

153

【輸入輸出樣例解釋】

樣例共有5個作業，應該分成｛1,2｝｛3｝｛4,5｝。作業的完成時間分別為｛5,5,10,14,14｝。

【資料規模】

對於40％的資料，1<=n<=2000。

對於100％的資料，1<=n<=10000。

對於100％的資料,1<=S<=50,1<=Fi<=100,1<=Ti<=100，保證最後的結果不大於2^31-1。

3**．鬼火閃閃**

(3.pas/c/cpp | 記憶體 128 MB)

【問題描述】

隊伍即將到達神牛島時，突然一片黑暗的路邊開始鬼火連連。這些特殊的鬼火有明有暗，安靜地排列在路的右邊。他們排成一條直線，似乎在恐嚇人們，不要繼續前進。

突然，前面出現一個鍵盤，恐怖的聲音傳了過來：「是自己人嗎？請輸入密碼。」

大家猜了半天也沒有猜到密碼，這時，篤志者想，這個密碼如果不簡單，那麼他們自己人怎麼能背會呢？由於是數字密碼，是不是這個密碼有什麼玄機的？

望著旁邊的鬼火，篤志者開始計算起來。突然，他輸入一個數字，鍵盤破解了。

原來，從左到右，明亮的鬼火和暗淡的鬼火是有玄機的。篤志者發現，旁邊有30個鬼火，用L表示亮，P表示不亮。假設亮鬼火所在位置為W（位置從右到左，從0開始計數），對於各個鬼火位置，二的W次方的和就是結果。

過了一會兒，竟然又出現了鍵盤，在鍵盤旁邊有一張小紙條，上面有一個數字，但是這時候卻看不見鬼火的明暗了。這次機關的破解難多了，過了三個小時，篤志者終於明白了規律。小紙條的數字，隱含著鬼火的排列情況，假設亮鬼火所在位置為W（位置從右到左，從0開始計數），對於各個鬼火位置，二的W次方的和就是結果。

例如某次鍵盤上的小紙條的數字是1，反推可得位置0是亮鬼火，其它位置都是暗鬼火，這樣就反推出了鬼火的情況。

然後，將從左到右的前14個鬼火最前面補兩個空位，和後16個鬼火進行交換，上例交換後，第14個鬼火為亮，其餘都是暗。如下所示：

交換前：

從左到右前十四：空 空 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗

從左到右後十六：暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 亮

交換後：

從左到右前十六：暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 亮

從左到右後十四：空 空 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗

在這樣的鬼火排列中，假設亮鬼火所在位置為W（位置從右到左，從0開始計數），對於各個鬼火位置，二的W次方的和就是結果。

也就是說，如果小紙條上的數字是1，交換後，從右到左的第16個鬼火為亮，那麼你應該輸入的密碼，就是216的值。

可是再往後，鍵盤越來越多，計算方法卻都和剛剛的那次一樣。繁瑣的工作就交給大家來做吧。

【輸入】

輸入檔案3.in的第一行為N，為紙條的個數。

接下來有N行，每行一個數，為小紙條上的數字。

【輸出】

輸出檔案3.out有N行，為每行對應的密碼。

【輸入輸出樣例】

3.in

3.out

1

7494574

1538130034

【資料規模】

對於100％的資料，1<=n<=600,000。

4**．險象叢生**

(4.pas/c/cpp | 記憶體 128 MB)

【問題描述】

到達神牛島之後，一行人瘋狂地慶祝了一番。神牛島上什麼都有，港口、超市一應俱全。然後就準備返回出發地。可是，這並不是一件容易的事情。因為，來的時候，他們有密碼；回去的時候，他們才發現，紙條都讓他們隨手給仍了，已經沒有辦法輸入正確的密碼。他們只好渡河到另一個港口。可是，到了渡河處，他們才發現這裡的河波濤洶湧，但船卻都很小，每個船都只能坐一個人。更恐怖的是，水中有一種叫做「有去無回」的怪物，不定什麼時候就會爬到某個船上，將其銷燬。為了防止這種情況，必須有人死死盯住周圍，一旦有東西爬上，先下手為強，將其弄死。

另一方面，這些船非常小，坐一個人就吃水很深，讓人覺得很不安全。為此，篤志者想到了赤壁之戰。於是，他就動員大家找了一些結實的材料，將一部分船連線在一起。由於材料很難找，連線都很短，從一艘船可以直接跳到另一艘船上，而且由於人們很聰明地節約材料，他們保證了去掉某兩船的連線後，一定會導致至少一艘船脫離連環船。即使這樣節約，也不能讓所有船都連在一起，只能成為一組一組的連環船。

現在已經連線好了一組組的連環船。由於擔心萬一船禁不住沉了或遇到「有去無回」怪物破壞船隻導致某船沉沒，就有人沒地方坐了，所以，每組船可以不坐滿，少坐人，這樣就會讓更多的船成為無人的「備用船」，以備不測。但卻必須保證每艘船都能被人看守住（每艘船或其直接連線的船二者至少有一船坐人），以便看住「有去無回」怪物，保障船的安全。同時，由於面臨很多未知數，篤志者希望大家乘坐的連環船的組數越多越好，一旦某組連環船沉沒，人們還可以逃生到另一組連環船。「船多力量大」嘛！篤志者想知道，在這樣的條件下，他們最多可以安全控制住多少組連環船。

資料保證人數<=船數。

【輸入】

輸入檔案4.in的第一行為三個正整數N M P，分別為船的條數、隊員的人數和邊數。

接下來有P行，每行兩個數i和j，表示這兩搜船直接相連，編號從1開始，不會輸入重複的連線，船的連線不分方向。

【輸出】

輸出檔案4.out只有一行，為隊員最多可以安全控制的連環船的組數。

【輸入輸出樣例】

4.in

4.out

6 2 3

2 5

3 5

2 6

2

【輸入輸出樣例解釋】

由於只有兩個人，可以控制船5所在的連環船（一個人坐船5，一個人坐船6，即可看住所有侵犯的「有去無回」），此時只能控制一組連環船。也可以控制船1和船4，此時則控制了兩組獨立的連環船，所以，答案為後者，2。

【資料規模】

對於100％的資料，1<=M<=N<=5000。