資源簡介

2013 亞太地區(qū)信息學奧林匹克競賽
APIO 2013
競賽時間：2013 年 5 月 11 日 9:00-14:00
題目名稱 機器人 道路費用 出題人
英文名稱 ROBOTS TOLL TASKSAUTHOR
輸入 標準輸入
輸出 標準輸出
每個測試點時限 1.5 秒 2.5 秒 /
內(nèi)存限制 128 MB 128MB /
試題總分 100 100 100
測試點數(shù)目 20 20 8
每個測試點分值 5 5 見題面
編譯器版本及編譯選項見考試注意事項。
2013 亞太地區(qū)信息學奧林匹克競賽
機器人
機器人
【問題描述】
VRI（Voltron 機器人學會）的工程師建造了 n 個機器人。任意兩個兼容的機
器人站在同一個格子時可以合并為一個復合機器人。
我們把機器人用 1 至 n 編號（n ≤ 9）。如果兩個機器人的編號是連續(xù)的，那
么它們是兼容的，可以合并成一個復合機器人。最初這 n 個機器人各自都只有唯
一的編號。而一個由兩個或以上的機器人合并構(gòu)成的復合機器人擁有兩個編號，
分別是構(gòu)成它的所有機器人中最小和最大的編號。
例如，2 號機器人只可以與 1 號或 3 號機器人合并。若 2 號機器人與 3 號機
器人合并，可構(gòu)成編號為 2-3 的復合機器人。如果編號為 2-3 的復合機器人與編
號為 4-6 的復合機器人合并，可構(gòu)成編號為 2-6 的復合機器人。當所有機器人合
并以后則構(gòu)成 1-n 復合機器人。
工程師把這 n 個機器人放在了一個封閉的房間中，房間四周均是墻。該房間
被劃分成 w × h 個方格。有些方格有障礙物，機器人不可經(jīng)過或停留；其余方格
允許多個機器人停留，同時允許機器人經(jīng)過。任何時候一個機器人只占用一個方
格。初始時刻，所有機器人均在不同的方格中。
這些原始的機器人不會自發(fā)地移動。它們只有被工程師沿 x 軸或 y 軸推動
后，才會沿推動的方向不斷向前直線移動，直至碰到障礙物或墻停止移動。停止
移動后，它會掃描當前的格子是否存在可以與它合并的機器人，如果有，則合并
并繼續(xù)檢查，直至不能再合并為止。工程師只能沿水平向左、水平向右、豎直向
上、豎直向下四個方向推動機器人，并且，在機器人尚未停止移動時，不允許推
動其它機器人，因此任何時刻，房間中都只能有一個機器人移動。
為了幫助機器人轉(zhuǎn)向，工程師在一些格子中放置了轉(zhuǎn)向器。具體地說，轉(zhuǎn)向
器分為順時針轉(zhuǎn)向器（右轉(zhuǎn)器）和逆時針轉(zhuǎn)向器（左轉(zhuǎn)器），順時針轉(zhuǎn)向器可以
使到達該格子的機器人沿順時針方向轉(zhuǎn)向 90°；逆時針轉(zhuǎn)向器可以使到達該格
子的機器人沿逆時針方向轉(zhuǎn)向 90°。
現(xiàn)在，我們將告訴你初始時刻房間內(nèi)的信息。請你計算工程師最少共計需要
推動機器人多少次，才能把所有的 n 個機器人全部合并（如果可能的話）。
【輸入格式】
你的程序必須從標準輸入讀入。輸入的第 1 行包含 3 個整數(shù) n、w 和 h，用
空格隔開。
輸入文件中接下來的 h 行描述初始時刻房間內(nèi)的信息，每行包含 w 個字符。
這 w × h 個字符中每一個表示房間中的一個格子，意義如下：
‘1’至‘9’：表示該方格中有一個機器人，編號為這個數(shù)字；
‘x’：表示該方格有障礙物；
‘A’：表示該方格中有一個逆時針轉(zhuǎn)向器；
‘C’：表示該方格中有一個順時針轉(zhuǎn)向器；
‘.’：表示該方格為空地。
第 2 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
機器人
【輸出格式】
你的程序必須輸出到標準輸出。輸出僅一個整數(shù)，表示最少需要推動的次數(shù)。
若不能使所有機器人全部合并，輸出-1。
【樣例輸入】
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
【樣例輸出】
5
【樣例說明】
第一步：向右推動 3 號機器人，當它碰到轉(zhuǎn)向器后會向上繼續(xù)移動，直至碰
到墻壁停止移動。
第二步：向上推動 4 號機器人，當它碰到墻壁后停止移動，與 3 號機器人合
并，構(gòu)成 3-4 號機器人
第三步：向上推動 2 號機器人，當它碰到轉(zhuǎn)向器后會向左移動，由于左側(cè)為
墻壁，故停留在原地。
第四步：向右推動 2 號機器人，由于它在一個轉(zhuǎn)向器上，故它會向上移動，
直至碰到墻壁停止移動，與 1 號機器人合并，構(gòu)成 1-2 號機器人。
第五步：向左推動 3-4 號機器人，當它碰到墻壁后停止移動，與 1-2 號機器
人合并，構(gòu)成 1-4 號機器人。
【數(shù)據(jù)規(guī)模與約定】
我們將使用以下 4 類輸入測例測試你的程序。
1. （10 分）測例滿足 n = 2，w ≤ 10 且 h ≤ 10，沒有任何轉(zhuǎn)向器。
2. （20 分）測例滿足 n = 2，w ≤ 10 且 h ≤ 10。
3. （30 分）測例滿足 n ≤ 9，w ≤ 300 且 h ≤ 300。
4. （40 分）測例滿足 n ≤ 9，w ≤ 500 且 h ≤ 500。
第 3 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
道路費用
道路費用
【問題描述】
幸福國度可以用 N 個城鎮(zhèn)（用 1 到 N 編號）構(gòu)成的集合來描述，這些城鎮(zhèn)
最開始由 M 條雙向道路（用 1 到 M 編號）連接。城鎮(zhèn) 1 是中央城鎮(zhèn)。保證一個
人從城鎮(zhèn) 1 出發(fā)，經(jīng)過這些道路，可以到達其他的任何一個城市。這些道路都是
收費道路，道路 i 的使用者必須向道路的主人支付 ci 分錢的費用。已知所有的這
些 ci是互不相等的。最近有K條新道路建成，這些道路都屬于億萬富豪Mr. Greedy。
Mr. Greedy 可以決定每條新道路的費用（費用可以相同），并且他必須在明天宣
布這些費用。
兩周以后，幸福國度將舉辦一個盛況空前的嘉年華！大量的參與者將沿著這
些道路游行并前往中央城鎮(zhèn)。共計 pj 個參與者將從城鎮(zhèn) j 出發(fā)前往中央城鎮(zhèn)。這
些人只會沿著一個選出的道路集合前行，并且這些選出的道路將在這件事的前一
天公布。根據(jù)一個古老的習俗，這些道路將由幸福國度中最有錢的人選出，也就
是 Mr. Greedy。同樣根據(jù)這個習俗，Mr. Greedy 選出的這個道路集合必須使所有
選出道路的費用之和最小，并且仍要保證任何人可以從城鎮(zhèn) j 前往城鎮(zhèn) 1（因此，
這些選出的道路來自將費用作為相應邊邊權(quán)的“最小生成樹”）。如果有多個這樣
的道路集合，Mr. Greedy 可以選其中的任何一個，只要滿足費用和是最小的。
Mr. Greedy 很明確地知道，他從 K 條新道路中獲得的收入不只是與費用有
關。一條道路的收入等于所有經(jīng)過這條路的人的花費之和。更準確地講，如果 p
個人經(jīng)過道路 i，道路 i 產(chǎn)生的收入為 ci p 的積。注意 Mr. Greedy 只能從新道路
收取費用，因為原來的道路都不屬于他。
Mr. Greedy 有一個陰謀。他計劃通過操縱費用和道路的選擇來最大化他的收
入。他希望指定每條新道路的費用（將在明天公布），并且選擇嘉年華用的道路
（將在嘉年華的前一天公布），使得他在 K 條新道路的收入最大。注意 Mr. Greedy
仍然需要遵循選出花費之和最小的道路集合的習俗。
你是一個記者，你想揭露他的計劃。為了做成這件事，你必須先寫一個程序
來確定 Mr. Greedy 可以通過他的陰謀獲取多少收入。
【輸入格式】
你的程序必須從標準輸入讀入。第一行包含三個由空格隔開的整數(shù) N，M 和
K。接下來的 M 行描述最開始的 M 條道路。這 M 行中的第 i 行包含由空格隔開
的整數(shù) ai，bi 和 ci，表示有一條在 ai 和 bi 之間，費用為 ci 的雙向道路。接下來的
K 行描述新建的 K 條道路。這 K 行中的第 i 行包含由空格隔開的整數(shù) xi 和 yi，表
示有一條連接城鎮(zhèn) xi 和 yi 新道路。最后一行包含 N 個由空格隔開的整數(shù)，其中
的第 j 個為 pj，表示從城鎮(zhèn) j 前往城鎮(zhèn) 1 的人數(shù)。
輸入也滿足以下約束條件。
1 ≤ N ≤ 100000；
1 ≤ K ≤ 20；
1 ≤ M ≤ 300000；
6
對每個 i 和 j，1 ≤ ci, pj ≤ 10 ；
第 4 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
道路費用
如果 i ≠ i'，則 ci ≠ ci'；
在任意兩個城市之間，最多只有一條道路（包括新建的道路）。
【輸出格式】
你的程序必須輸出恰好一個整數(shù)到標準輸出，表示能獲得的最大的收入。
【樣例輸入】
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
【樣例輸出】
400
【樣例說明】
在樣例中，Mr. Greedy 應該將新道路(1,3)的費用設置為 5 分錢。在這個費用
下，他可以選擇道路(3,5)，(1,2)，(2,4)和(1,3)來最小化總費用，這個費用為 14。
從城鎮(zhèn) 3 出發(fā)的 30 個人和從城鎮(zhèn) 5 出發(fā)的 50 個人將經(jīng)過新道路前往城鎮(zhèn) 1，因
此他可以獲得為(30+50)×5=400 分錢的最好收入。
如果我們這樣做，將新道路(1,3)的費用設置為 10 分錢。根據(jù)傳統(tǒng)的限制，
Mr. Greedy 必須選擇(3,5)，(1,2)，(2,4)和(2,3)，因為這是唯一費用最小的集合。
因此，在嘉年華的過程中道路(1,3)將沒有任何收入。
【數(shù)據(jù)規(guī)模與約定】
我們將使用以下 5 類測例測試你的程序。
1. （國際 16 分，國內(nèi) 15 分）N ≤ 10，M ≤ 20 且 K = 1；
2. （國際 18 分，國內(nèi) 20 分）N ≤ 30，M ≤ 50 且 K ≤ 10；
3. （國際 22 分，國內(nèi) 20 分）N ≤ 1,000，M ≤ 5,000 且 K ≤ 10；
4. （國際 22 分，國內(nèi) 20 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 15；
5. （國際 22 分，國內(nèi) 25 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 20。
第 5 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
出題人
出題人
【問題描述】
當今世界上各類程序設計競賽層出不窮。而設計一場好比賽絕非易事，比如
給題目設計測試數(shù)據(jù)就是一項挑戰(zhàn)。一組好的測試數(shù)據(jù)需要對不同的程序有區(qū)分
度：滿足所有要求的程序自然應該得到滿分，而那些貌似正確的程序則會在某些
特殊數(shù)據(jù)上出錯。
在本題中，你在比賽中的角色反轉(zhuǎn)啦！作為一名久經(jīng)百戰(zhàn)的程序員，你將幫
助 Happy Programmer Contest 的命題委員會設計這次比賽的測試數(shù)據(jù)。本次比
賽命題委員會選擇了兩個圖論問題，分為 8 個子任務。委員會寫了一些貌似可以
解決這些子任務的代碼。在給任務設計數(shù)據(jù)的時候，命題委員會期望其中的一些
源程序能夠得到滿分，而另外的一些則只能得到 0 分或者少許的部分分?，F(xiàn)在你
將會獲得這些源程序（C,C++以及 Pascal 版本）。對于每個子任務，你需要去產(chǎn)
生一組數(shù)據(jù) X 使得它能將該任務給定的 2 種源程序 A 和 B 區(qū)分開來。更具體地
說，生成的數(shù)據(jù)必須滿足如下兩個條件：
1. 輸入 X 對于源程序 A 一定不會出現(xiàn)超出時間限制（TLE）的問題。
2. 輸入 X 一定會導致源程序 B 產(chǎn)生超出時間限制的問題。
此外，命題委員喜歡較小規(guī)模的測試數(shù)據(jù)，希望測試數(shù)據(jù)最好能夠包含不超
過 T 個整數(shù)。
（譯注：本題中只關心源程序 A 和 B 是否超時，不關心是否結(jié)果正確）
命題委員會選擇了單源最短路（SSSP）以及一個被稱之為神秘問題（Mystery）
的兩個圖論問題來作為比賽的題目。我們將命題委員會完成的偽代碼列在了附錄
中，而具體的 C++和 Pascal 源程序被我們放在了下發(fā)的文件當中。
【數(shù)據(jù)描述】
參見下表。表中每一行描述了一個子任務。其中前六個子任務與單源最短路
相關，子任務 7,8 與神秘問題相關。每個任務所占分數(shù)見下表。
測試點
分數(shù) S T 的限制 問題 源程序 A 源程序 B
編號
1 3 107 SSSP ModifiedDijkstra FloydWarshall
2 7 2222 SSSP FloydWarshall OptimizedBellmanFord
3 8 105 SSSP OptimizedBellmanFord FloydWarshall
4 17 157 SSSP FloydWarshall ModifiedDijkstra
5 10 1016 SSSP ModifiedDijkstra OptimizedBellmanFord
6 19 143 SSSP OptimizedBellmanFord ModifiedDijkstra
7 11 3004 Mystery Gamble1 RecursiveBactracking
8 25 3004 Mystery RecursiveBactracking Gamble2
對于每個子任務，你的程序給出的輸入 X 需要能夠?qū)⒃闯绦?A 和 B 區(qū)分開
來，這有這樣你才能夠得到相應的分數(shù)。具體說來，你的分數(shù)將由輸入 X 中數(shù)的
第 6 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
出題人
個數(shù)決定。假設 X 中包含了 F 個整數(shù)，子任務的滿分為 S，T 是該任務的目標大
小，則該測試點的分數(shù)將由下式給出：
0.5 + S * min{T / F, 1}
也就是說，如果你的測試數(shù)據(jù) X 中含有不超過 T 個整數(shù)，則你將得到該任
務的全部得分。
【評分標準】
你需要將你的 8 個測試數(shù)據(jù)命名為 tasksauthor.outX.1，其中的 X 是
子任務的編號。在提交前，你需要將你的測試數(shù)據(jù)使用 gzip 進行壓縮。在 Unix
系統(tǒng)下，可以使用如下命令壓縮文件：
tar -cvzf tasksauthor.tgz tasksauthor.out*.1
而在 Windows 系統(tǒng)中，可以使用 7-Zip 或是 Winzip 來進行壓縮。最后將打
包后的文件 tasksauthor.tgz 提交至評測服務器中。
評測服務器將會把你提交的文件解壓縮。對于每個子任務 X，評測系統(tǒng)將根
據(jù)如下步驟來確定你將會得到多少分：
1. 如果 tasksauthor.outX.1不存在，則不得分；
2. 若 tasksauthor.outX.1不滿足輸入格式要求，則不得分；
3. 對源程序 A 運行輸入 tasksauthor.outX.1，若發(fā)生超時現(xiàn)象，則不
得分；
4. 對源程序 B 運行輸入 tasksauthor.outX.1，若發(fā)生超時現(xiàn)象，則按
照下述公式給出該測試點的分數(shù)：
0.5 + S * min{T / F, 1}
題目提供的所有源代碼均會維護一個計數(shù)器來統(tǒng)計程序的操作次數(shù)。在源程
序的運行過程中，當該計數(shù)器超過了 1,000,000 次時，那么我們認為程序運行超
時。
【問題描述 1：單源最短路(SSSP)】
給定一個帶權(quán)有向圖 G，以及 G 中的兩個節(jié)點 s 與 t，令 p(s, t) 為 G 中從
s 至 t 的最短路長度。如果 s 與 t 不連通，則認為 p(s, t)=1,000,000,000。在本題
中，輸入為圖 G 以及 Q 個詢問(s1, t1), (s2, t2 ), …, (sQ, tQ)。輸出則是對這 Q 個詢問
的相應輸出 p(s1, t1), p(s2, t2 ), …, p(sQ, tQ)。
【問題 1 輸入輸出格式】
輸入數(shù)據(jù)包含 2 部分，其中第一部分使用鄰接表來描述帶權(quán)有向圖 G。第二
部分則描述對 G 的最短路徑的查詢。
數(shù)據(jù)第一部分的第一行包含一個整數(shù) V，表示 G 中點的個數(shù)，所有點的編號
為 0, 1, …, V – 1。
接下來 V 行，每行描述一個點的所有邊。行中的第一個整數(shù) ni 描述了節(jié)點
i 的出邊數(shù)量，接下來有 ni 個整數(shù)對 (j, w) 表示有一條從 i 到 j ，邊權(quán)為 w
的邊。
數(shù)據(jù)第二部分的第一行包含一個整數(shù) Q，表示詢問的組數(shù)。
第 7 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
出題人
接下來 Q 行，第 k 行包含兩個整數(shù) sk, tk，為該詢問對應的起點與終點位置。
同一行中任意兩個相鄰的整數(shù)均需要至少一個空格將他們分開。除此之外，
數(shù)據(jù)還需滿足如下條件：
1. 0 < V ≤ 300；
2. ni 是一個非負整數(shù)；
3. 0 ≤ j < V；
4. |w| < 106；
5. 0 ≤ ∑V 1i=0 ≤ 5000；
6. 0 < Q ≤ 10；
7. 0 ≤ sk < V, 0 ≤ tk < V；
8. 所有詢問中的起點 sk 都不能達到任何一個負權(quán)圈。
程序?qū)敵?Q 行，每行一個整數(shù)，表示對應的 p(sk, tk)。而在輸出的最后，
所有提供的程序都會給出計數(shù)器對此輸入的數(shù)值。
【問題 1 樣例輸入】1
3
2 1 4 2 1
0
1 1 2
2
0 1
1 0
【問題 1 樣例輸出】2
3
1000000000
The value of counter is: 5
圖：問題 1 樣例輸入中的有向帶權(quán)圖
1 輸入包含 15 個整數(shù)，因此 F = 15。
2 將給定的樣例輸入使用 ModifiedDijkstra.cpp/pas 運行時，counter 的值為 5。
第 8 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
出題人
【問題描述 2：神秘問題】
給定一個包含 V 個節(jié)點 E 條邊的無向圖 G，要求將所有的節(jié)點進行編號（編
號范圍為[0 .. (X-1)]），使得所有直接相連的節(jié)點均有不同的編號。找出符合題
意的最小的 X。
【問題 2 輸入輸出格式】
輸入數(shù)據(jù)的第一行包含兩個整數(shù) V 和 E。
接下來 E 行，每行兩個整數(shù) a, b，表示 a 與 b 在 G 中直接相連。此外，輸入
數(shù)據(jù)應滿足如下限制條件：
1. 70 < V < 1000；
2. 1500 < E < 106；
3. 對于所有的邊 (a, b)，有 a ≠ b, 0 ≤ a < V, 0 ≤ b < V，不會重復描述一條
邊。
程序?qū)⒃诘谝恍休敵?X，即最小的編號范圍，接下來在第二行中給出 V 個整
數(shù)，依次描述節(jié)點 0 至 V – 1 的編號。在輸出的最后，所有提供的程序都會給出
計數(shù)器對此輸入的數(shù)值。
【問題 2 樣例輸入】3
4 5
0 1
0 2
0 3
1 2
2 3
【問題 2 樣例輸出】4
3
0 1 2 1
The value of counter is: 18
圖：左圖為問題 2 樣例輸入中的無向圖，右圖為 X=3 的一種標號
3 輸入包含 12 個整數(shù)，因此 F=12。這個例子只是一個示例，其中 V 和 E 的值都不滿足數(shù)據(jù)的限制（太
小）。
4 將給定的樣例輸入使用 RecursiveBacktracking.cpp/pas 運行時，counter 的值為 5。
第 9 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
出題人
【附錄：偽代碼】
接下來是我們提供的所有程序的偽代碼；變量 counter 近似描述出了程
序的運行時間。評測服務器將會使用這些偽代碼的 c++ 版本來進行評測。
【FloydWarshall.cpp/pas】
// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
for i = 0 to V-1
for j = 0 to V-1
increase counter by 1;
M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
output M[s][t];
【OptimizedBellmanFord.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];
【ModifiedDijkstra.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
dist[s] = 0;
pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq;
remove the top element from pq;
第 10 頁 共 11 頁
2013 亞太地區(qū)信息學奧林匹克競賽
出題人
if (d == dist[u])
for each edge (u,v) in L
if (dist[u] + weight(u,v) ) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq;
output dist[t];
【Gamble1.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE
【Gamble2.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE
【RecursiveBacktracking.cpp/pas】
This algorithm tries X from 2 to V one by one
and stops at the first valid X.
For each X, the backtracking routine label vertex 0 with 0,
then for each vertex u that has been assigned a label,
the backtracking routine tries to assign
the smallest possible label up to label X-1 to its neighbor v,
and backtracks if necessary.
// Please check RecursiveBacktracking.cpp/pas to see
// the exact lines where the iteration counter is increased by 1
第 11 頁 共 11 頁本資料來自于資源最齊全的２１世紀教育網(wǎng)www.21cnjy.com
2013亞太地區(qū)信息學奧林匹克競賽
APIO 2013
競賽時間：2013年5月11日9:00-14:00
題目名稱 機器人 道路費用 出題人
英文名稱 ROBOTS TOLL TASKSAUTHOR
輸入 標準輸入
輸出 標準輸出
每個測試點時限 1.5 秒 2.5 秒 /
內(nèi)存限制 128 MB 128MB /
試題總分 100 100 100
測試點數(shù)目 20 20 8
每個測試點分值 5 5 見題面
編譯器版本及編譯選項見考試注意事項。
機器人
【問題描述】
VRI（Voltron機器人學會）的工程師建造了n個機器人。任意兩個兼容的機器人站在同一個格子時可以合并為一個復合機器人。
我們把機器人用1至n編號（n ≤ 9）。如果兩個機器人的編號是連續(xù)的，那么它們是兼容的，可以合并成一個復合機器人。最初這n個機器人各自都只有唯一的編號。而一個由兩個或以上的機器人合并構(gòu)成的復合機器人擁有兩個編號，分別是構(gòu)成它的所有機器人中最小和最大的編號。
例如，2號機器人只可以與1號或3號機器人合并。若2號機器人與3號機器人合并，可構(gòu)成編號為2-3的復合機器人。如果編號為2-3的復合機器人與編號為4-6的復合機器人合并，可構(gòu)成編號為2-6的復合機器人。當所有機器人合并以后則構(gòu)成1-n復合機器人。
工程師把這n個機器人放在了一個封閉的房間中，房間四周均是墻。該房間被劃分成w × h個方格。有些方格有障礙物，機器人不可經(jīng)過或停留；其余方格允許多個機器人停留，同時允許機器人經(jīng)過。任何時候一個機器人只占用一個方格。初始時刻，所有機器人均在不同的方格中。
這些原始的機器人不會自發(fā)地移動。它們只有被工程師沿x軸或y軸推動后，才會沿推動的方向不斷向前直線移動，直至碰到障礙物或墻停止移動。停止移動后，它會掃描當前的格子是否存在可以與它合并的機器人，如果有，則合并并繼續(xù)檢查，直至不能再合并為止。工程師只能沿水平向左、水平向右、豎直向上、豎直向下四個方向推動機器人，并且，在機器人尚未停止移動時，不允許推動其它機器人，因此任何時刻，房間中都只能有一個機器人移動。
為了幫助機器人轉(zhuǎn)向，工程師在一些格子中放置了轉(zhuǎn)向器。具體地說，轉(zhuǎn)向器分為順時針轉(zhuǎn)向器（右轉(zhuǎn)器）和逆時針轉(zhuǎn)向器（左轉(zhuǎn)器），順時針轉(zhuǎn)向器可以使到達該格子的機器人沿順時針方向轉(zhuǎn)向90°；逆時針轉(zhuǎn)向器可以使到達該格子的機器人沿逆時針方向轉(zhuǎn)向90°。
現(xiàn)在，我們將告訴你初始時刻房間內(nèi)的信息。請你計算工程師最少共計需要推動機器人多少次，才能把所有的n個機器人全部合并（如果可能的話）。
【輸入格式】
你的程序必須從標準輸入讀入。輸入的第1行包含3個整數(shù)n、w和h，用空格隔開。
輸入文件中接下來的h行描述初始時刻房間內(nèi)的信息，每行包含w個字符。這w × h個字符中每一個表示房間中的一個格子，意義如下：
‘1’至‘9’：表示該方格中有一個機器人，編號為這個數(shù)字；
‘x’：表示該方格有障礙物；
‘A’：表示該方格中有一個逆時針轉(zhuǎn)向器；
‘C’：表示該方格中有一個順時針轉(zhuǎn)向器；
‘.’：表示該方格為空地。
【輸出格式】
你的程序必須輸出到標準輸出。輸出僅一個整數(shù)，表示最少需要推動的次數(shù)。若不能使所有機器人全部合并，輸出-1。
【樣例輸入】
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
【樣例輸出】
5
【樣例說明】
第一步：向右推動3號機器人，當它碰到轉(zhuǎn)向器后會向上繼續(xù)移動，直至碰到墻壁停止移動。
第二步：向上推動4號機器人，當它碰到墻壁后停止移動，與3號機器人合并，構(gòu)成3-4號機器人
第三步：向上推動2號機器人，當它碰到轉(zhuǎn)向器后會向左移動，由于左側(cè)為墻壁，故停留在原地。
第四步：向右推動2號機器人，由于它在一個轉(zhuǎn)向器上，故它會向上移動，直至碰到墻壁停止移動，與1號機器人合并，構(gòu)成1-2號機器人。
第五步：向左推動3-4號機器人，當它碰到墻壁后停止移動，與1-2號機器人合并，構(gòu)成1-4號機器人。
【數(shù)據(jù)規(guī)模與約定】
我們將使用以下4類輸入測例測試你的程序。
1. （10分）測例滿足n = 2，w ≤ 10且h ≤ 10，沒有任何轉(zhuǎn)向器。
2. （20分）測例滿足n = 2，w ≤ 10且h ≤ 10。
3. （30分）測例滿足n ≤ 9，w ≤ 300且h ≤ 300。
4. （40分）測例滿足n ≤ 9，w ≤ 500且h ≤ 500。
道路費用
【問題描述】
幸福國度可以用N個城鎮(zhèn)（用1到N編號）構(gòu)成的集合來描述，這些城鎮(zhèn)最開始由M條雙向道路（用1到M編號）連接。城鎮(zhèn)1是中央城鎮(zhèn)。保證一個人從城鎮(zhèn)1出發(fā)，經(jīng)過這些道路，可以到達其他的任何一個城市。這些道路都是收費道路，道路i的使用者必須向道路的主人支付ci分錢的費用。已知所有的這些ci是互不相等的。最近有K條新道路建成，這些道路都屬于億萬富豪Mr. Greedy。Mr. Greedy可以決定每條新道路的費用（費用可以相同），并且他必須在明天宣布這些費用。
兩周以后，幸福國度將舉辦一個盛況空前的嘉年華！大量的參與者將沿著這些道路游行并前往中央城鎮(zhèn)。共計pj個參與者將從城鎮(zhèn)j出發(fā)前往中央城鎮(zhèn)。這些人只會沿著一個選出的道路集合前行，并且這些選出的道路將在這件事的前一天公布。根據(jù)一個古老的習俗，這些道路將由幸福國度中最有錢的人選出，也就是Mr. Greedy。同樣根據(jù)這個習俗，Mr. Greedy選出的這個道路集合必須使所有選出道路的費用之和最小，并且仍要保證任何人可以從城鎮(zhèn)j前往城鎮(zhèn)1（因此，這些選出的道路來自將費用作為相應邊邊權(quán)的“最小生成樹”）。如果有多個這樣的道路集合，Mr. Greedy可以選其中的任何一個，只要滿足費用和是最小的。
Mr. Greedy很明確地知道，他從K條新道路中獲得的收入不只是與費用有關。一條道路的收入等于所有經(jīng)過這條路的人的花費之和。更準確地講，如果p個人經(jīng)過道路i，道路i產(chǎn)生的收入為ci p的積。注意Mr. Greedy只能從新道路收取費用，因為原來的道路都不屬于他。
Mr. Greedy有一個陰謀。他計劃通過操縱費用和道路的選擇來最大化他的收入。他希望指定每條新道路的費用（將在明天公布），并且選擇嘉年華用的道路（將在嘉年華的前一天公布），使得他在K條新道路的收入最大。注意Mr. Greedy仍然需要遵循選出花費之和最小的道路集合的習俗。
你是一個記者，你想揭露他的計劃。為了做成這件事，你必須先寫一個程序來確定Mr. Greedy可以通過他的陰謀獲取多少收入。
【輸入格式】
你的程序必須從標準輸入讀入。第一行包含三個由空格隔開的整數(shù)N，M和K。接下來的M行描述最開始的M條道路。這M行中的第i行包含由空格隔開的整數(shù)ai，bi和ci，表示有一條在ai和bi之間，費用為ci的雙向道路。接下來的K行描述新建的K條道路。這K行中的第i行包含由空格隔開的整數(shù)xi和yi，表示有一條連接城鎮(zhèn)xi和yi新道路。最后一行包含N個由空格隔開的整數(shù)，其中的第j個為pj，表示從城鎮(zhèn)j前往城鎮(zhèn)1的人數(shù)。
輸入也滿足以下約束條件。
1 ≤ N ≤ 100000；
1 ≤ K ≤ 20；
1 ≤ M ≤ 300000；
對每個i和j，1 ≤ ci, pj ≤ 106；
如果i ≠ i'，則ci ≠ ci'；
在任意兩個城市之間，最多只有一條道路（包括新建的道路）。
【輸出格式】
你的程序必須輸出恰好一個整數(shù)到標準輸出，表示能獲得的最大的收入。
【樣例輸入】
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
【樣例輸出】
400
【樣例說明】
在樣例中，Mr. Greedy應該將新道路(1,3)的費用設置為5分錢。在這個費用下，他可以選擇道路(3,5)，(1,2)，(2,4)和(1,3)來最小化總費用，這個費用為14。從城鎮(zhèn)3出發(fā)的30個人和從城鎮(zhèn)5出發(fā)的50個人將經(jīng)過新道路前往城鎮(zhèn)1，因此他可以獲得為(30+50)×5=400分錢的最好收入。
如果我們這樣做，將新道路(1,3)的費用設置為10分錢。根據(jù)傳統(tǒng)的限制，Mr. Greedy必須選擇(3,5)，(1,2)，(2,4)和(2,3)，因為這是唯一費用最小的集合。因此，在嘉年華的過程中道路(1,3)將沒有任何收入。
【數(shù)據(jù)規(guī)模與約定】
我們將使用以下5類測例測試你的程序。
1. （國際16分，國內(nèi)15分）N ≤ 10，M ≤ 20且K = 1；
2. （國際18分，國內(nèi)20分）N ≤ 30，M ≤ 50且K ≤ 10；
3. （國際22分，國內(nèi)20分）N ≤ 1,000，M ≤ 5,000且K ≤ 10；
4. （國際22分，國內(nèi)20分）N ≤ 100,000，M ≤ 300,000且K ≤ 15；
5. （國際22分，國內(nèi)25分）N ≤ 100,000，M ≤ 300,000且K ≤ 20。
出題人
【問題描述】
當今世界上各類程序設計競賽層出不窮。而設計一場好比賽絕非易事，比如給題目設計測試數(shù)據(jù)就是一項挑戰(zhàn)。一組好的測試數(shù)據(jù)需要對不同的程序有區(qū)分度：滿足所有要求的程序自然應該得到滿分，而那些貌似正確的程序則會在某些特殊數(shù)據(jù)上出錯。
在本題中，你在比賽中的角色反轉(zhuǎn)啦！作為一名久經(jīng)百戰(zhàn)的程序員，你將幫助 Happy Programmer Contest 的命題委員會設計這次比賽的測試數(shù)據(jù)。本次比賽命題委員會選擇了兩個圖論問題，分為8個子任務。委員會寫了一些貌似可以解決這些子任務的代碼。在給任務設計數(shù)據(jù)的時候，命題委員會期望其中的一些源程序能夠得到滿分，而另外的一些則只能得到0分或者少許的部分分?，F(xiàn)在你將會獲得這些源程序（C,C++以及Pascal版本）。對于每個子任務，你需要去產(chǎn)生一組數(shù)據(jù)X使得它能將該任務給定的2種源程序A和B區(qū)分開來。更具體地說，生成的數(shù)據(jù)必須滿足如下兩個條件：
1. 輸入X對于源程序A一定不會出現(xiàn)超出時間限制（TLE）的問題。
2. 輸入X一定會導致源程序B產(chǎn)生超出時間限制的問題。
此外，命題委員喜歡較小規(guī)模的測試數(shù)據(jù)，希望測試數(shù)據(jù)最好能夠包含不超過T個整數(shù)。
（譯注：本題中只關心源程序A和B是否超時，不關心是否結(jié)果正確）
命題委員會選擇了單源最短路（SSSP）以及一個被稱之為神秘問題（Mystery）的兩個圖論問題來作為比賽的題目。我們將命題委員會完成的偽代碼列在了附錄中，而具體的C++和Pascal源程序被我們放在了下發(fā)的文件當中。
【數(shù)據(jù)描述】
參見下表。表中每一行描述了一個子任務。其中前六個子任務與單源最短路相關，子任務7,8與神秘問題相關。每個任務所占分數(shù)見下表。
測試點編號 分數(shù)S T的限制 問題 源程序A 源程序B
1 3 107 SSSP ModifiedDijkstra FloydWarshall
2 7 2222 SSSP FloydWarshall OptimizedBellmanFord
3 8 105 SSSP OptimizedBellmanFord FloydWarshall
4 17 157 SSSP FloydWarshall ModifiedDijkstra
5 10 1016 SSSP ModifiedDijkstra OptimizedBellmanFord
6 19 143 SSSP OptimizedBellmanFord ModifiedDijkstra
7 11 3004 Mystery Gamble1 RecursiveBactracking
8 25 3004 Mystery RecursiveBactracking Gamble2
對于每個子任務，你的程序給出的輸入X需要能夠?qū)⒃闯绦駻和B區(qū)分開來，這有這樣你才能夠得到相應的分數(shù)。具體說來，你的分數(shù)將由輸入X中數(shù)的個數(shù)決定。假設X中包含了F個整數(shù)，子任務的滿分為S，T是該任務的目標大小，則該測試點的分數(shù)將由下式給出：
0.5 + S * min{T / F, 1}
也就是說，如果你的測試數(shù)據(jù)X中含有不超過 T 個整數(shù)，則你將得到該任務的全部得分。
【評分標準】
你需要將你的8個測試數(shù)據(jù)命名為tasksauthor.outX.1，其中的 X 是子任務的編號。在提交前，你需要將你的測試數(shù)據(jù)使用gzip進行壓縮。在Unix系統(tǒng)下，可以使用如下命令壓縮文件：
tar -cvzf tasksauthor.tgz tasksauthor.out*.1
而在Windows系統(tǒng)中，可以使用7-Zip或是Winzip來進行壓縮。最后將打包后的文件 tasksauthor.tgz 提交至評測服務器中。
評測服務器將會把你提交的文件解壓縮。對于每個子任務X，評測系統(tǒng)將根據(jù)如下步驟來確定你將會得到多少分：
1. 如果tasksauthor.outX.1不存在，則不得分；
2. 若tasksauthor.outX.1不滿足輸入格式要求，則不得分；
3. 對源程序A運行輸入tasksauthor.outX.1，若發(fā)生超時現(xiàn)象，則不得分；
4. 對源程序B運行輸入tasksauthor.outX.1，若發(fā)生超時現(xiàn)象，則按照下述公式給出該測試點的分數(shù)：
0.5 + S * min{T / F, 1}
題目提供的所有源代碼均會維護一個計數(shù)器來統(tǒng)計程序的操作次數(shù)。在源程序的運行過程中，當該計數(shù)器超過了1,000,000次時，那么我們認為程序運行超時。
【問題描述1：單源最短路(SSSP)】
給定一個帶權(quán)有向圖G，以及G中的兩個節(jié)點s與t，令 p(s, t) 為G中從s至t的最短路長度。如果s與t不連通，則認為p(s, t)=1,000,000,000。在本題中，輸入為圖G以及Q個詢問(s1, t1), (s2, t2 ), …, (sQ, tQ)。輸出則是對這Q個詢問的相應輸出p(s1, t1), p(s2, t2 ), …, p(sQ, tQ)。
【問題1輸入輸出格式】
輸入數(shù)據(jù)包含2部分，其中第一部分使用鄰接表來描述帶權(quán)有向圖G。第二部分則描述對G的最短路徑的查詢。
數(shù)據(jù)第一部分的第一行包含一個整數(shù)V，表示G中點的個數(shù)，所有點的編號為0, 1, …, V – 1。
接下來V行，每行描述一個點的所有邊。行中的第一個整數(shù) ni 描述了節(jié)點 i 的出邊數(shù)量，接下來有 ni 個整數(shù)對 (j, w) 表示有一條從 i 到 j ，邊權(quán)為 w的邊。
數(shù)據(jù)第二部分的第一行包含一個整數(shù)Q，表示詢問的組數(shù)。
接下來Q行，第k行包含兩個整數(shù) sk, tk，為該詢問對應的起點與終點位置。
同一行中任意兩個相鄰的整數(shù)均需要至少一個空格將他們分開。除此之外，數(shù)據(jù)還需滿足如下條件：
1. 0 < V ≤ 300；
2. ni 是一個非負整數(shù)；
3. 0 ≤ j < V；
4. |w| < 106；
5. 0 ≤ ≤ 5000；
6. 0 < Q ≤ 10；
7. 0 ≤ sk < V, 0 ≤ tk < V；
8. 所有詢問中的起點sk 都不能達到任何一個負權(quán)圈。
程序?qū)敵鯭行，每行一個整數(shù)，表示對應的p(sk, tk)。而在輸出的最后，所有提供的程序都會給出計數(shù)器對此輸入的數(shù)值。
【問題1樣例輸入】 [1]
3
2 1 4 2 1
0
1 1 2
2
0 1
1 0
【問題1樣例輸出】 [2]
3
1000000000
The value of counter is: 5
圖：問題1樣例輸入中的有向帶權(quán)圖
【問題描述2：神秘問題】
給定一個包含V個節(jié)點E條邊的無向圖G，要求將所有的節(jié)點進行編號（編號范圍為[0 .. (X-1)]），使得所有直接相連的節(jié)點均有不同的編號。找出符合題意的最小的 X。
【問題2輸入輸出格式】
輸入數(shù)據(jù)的第一行包含兩個整數(shù)V和E。
接下來E行，每行兩個整數(shù)a, b，表示a與b在G中直接相連。此外，輸入數(shù)據(jù)應滿足如下限制條件：
1. 70 < V < 1000；
2. 1500 < E < 106；
3. 對于所有的邊 (a, b)，有 a ≠ b, 0 ≤ a < V, 0 ≤ b < V，不會重復描述一條邊。
程序?qū)⒃诘谝恍休敵鯴，即最小的編號范圍，接下來在第二行中給出V個整數(shù)，依次描述節(jié)點0至V – 1的編號。在輸出的最后，所有提供的程序都會給出計數(shù)器對此輸入的數(shù)值。
【問題2樣例輸入】 [3]
4 5
0 1
0 2
0 3
1 2
2 3
【問題2樣例輸出】 [4]
3
0 1 2 1
The value of counter is: 18
圖：左圖為問題2樣例輸入中的無向圖，右圖為X=3的一種標號
【附錄：偽代碼】
接下來是我們提供的所有程序的偽代碼；變量 counter 近似描述出了程序的運行時間。評測服務器將會使用這些偽代碼的 c++ 版本來進行評測。
【FloydWarshall.cpp/pas】
// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
for i = 0 to V-1
for j = 0 to V-1
increase counter by 1;
M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
output M[s][t];
【OptimizedBellmanFord.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];
【ModifiedDijkstra.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
dist[s] = 0;
pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq;
remove the top element from pq;
if (d == dist[u])
for each edge (u,v) in L
if (dist[u] + weight(u,v) ) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq;
output dist[t];
【Gamble1.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE
【Gamble2.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE
【RecursiveBacktracking.cpp/pas】
This algorithm tries X from 2 to V one by one
and stops at the first valid X.
For each X, the backtracking routine label vertex 0 with 0,
then for each vertex u that has been assigned a label,
the backtracking routine tries to assign
the smallest possible label up to label X-1 to its neighbor v,
and backtracks if necessary.
// Please check RecursiveBacktracking.cpp/pas to see
// the exact lines where the iteration counter is increased by 1
21世紀教育網(wǎng) -- 中國最大型、最專業(yè)的中小學教育資源門戶網(wǎng)站。 版權(quán)所有@21世紀教育網(wǎng)
^1 輸入包含15個整數(shù)，因此F = 15。
^2 將給定的樣例輸入使用ModifiedDijkstra.cpp/pas運行時，counter的值為5。
^3 輸入包含12個整數(shù)，因此F=12。這個例子只是一個示例，其中V和 E的值都不滿足數(shù)據(jù)的限制（太?。?br/>^4 將給定的樣例輸入使用RecursiveBacktracking.cpp/pas運行時，counter的值為5。

展開更多......

收起↑