2013年9月28日 星期六

1236 - Disjoint Paths

給一張圖,具有 N 個點和 N-1 條有權重的邊。找到最多 K 條不相交(點和邊皆不重複使用)的路徑,而所有被選上的邊權重總和最大。


如上如所示,兩個不同限制下,在相同的圖中會有不同的答案。

在不相交路徑最多 K 條時,當 K = 1,如左圖所示,答案最大為 13 (5+2+6)。

當 K = 2,如右圖所示,答案最大為 15 ((5+1)+(3+6))。

Input 

輸入第一行會有一個整數 T,表示接下來的測資組樹。

對於每組測資,第一行會有兩個整數 N, K (K <= N <= 60)。

接下來會有 N - 1 行,每行上會有三個整數 A, B, D,表示一條無向邊於 A 到 B 權重為 D。
(1 <= A, B <= N, |D| <= 10000)


Output 

對於每組測資,輸出最大總和。

Sample Input 

2 
6 1 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1
6 2 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1

Sample Output 

13 
15

1199 - Elevator Stopping Plan

在 ZSoft Corp 這家公司中,每名員工都相當地勤奮,但是電梯問題總是困擾他們。
因為這家公司只有一台電梯運作,使得在早上的時候,總是會花很多時間在等待電梯。

Hal 相當聰明,想要改善這種情況,目標要把電梯改為更有效率,但這並不是簡單的工作。

公司總共有 31 樓,電梯上升一樓消耗 4 秒,也就是說將會使用 (31 - 1) ×4 = 120 秒到達頂樓,如果電梯打算停留某一層時,將會額外消耗 10 秒時間停止。如果電梯每層都停,將會消耗 30×4 + 29×10 = 410 秒 (不考慮停留在 31 樓)。

員工們可以打算爬樓梯,不管是往上或往下爬一層,都是消耗 20 秒。如果從 1 樓爬到 31 樓,則消耗 30×20 = 600 秒。當然,只爬樓梯肯定不是最好的方式。因此一些員工會使用電梯到達某一層之後,再爬樓梯到達他們自己的辦公室。

經過一段時間精密的思考後,Hal 最後找到一個方法改善這種情況。首先,電梯會先問所有人要到達的樓層,將會設計停留哪一層的方案,最小化最後一個人到達的時間。

例如,電梯被要求停留在第 4, 5, 10 樓時,停留方案為
1. 先停留於第 4 樓,此時消耗 3×4 = 12 秒,並且停止 10 秒。
2. 之後直接抵達 10 樓,此時時間為
3×4 + 10 + 6×4 = 46 秒。

到抵達 4 樓人在 12 秒時可以到達,抵達 5 樓的人可以在 12 + 20 = 32 秒,而要抵達 10 樓的人將在 46 秒後到達。


寫程式計算最小化最後一個人抵達的時間,並且輸出停留方案。

Input 

輸入有多組測資。

每組測資的格式如下:

n f1 f2 ... fn
將會有 n 個樓層被要求停留, f1 f2 ... fn 表示為要求停止的樓層。
 (n <= 30, 2 <= f1 < f2 < ... < fn <= 31)

Output 

對於每組測資,輸出一行最小的最後一個人抵達的時間。

第二行,先輸出停留樓層的個數,再分別輸出停留樓層的編號。

如果有多組輸出,任何一組都可以。

Sample Input 


3 4 5 10
1 2
0

Sample Output 


46
2 4 10
4
1 2

2013年9月18日 星期三

1148 - The mysterious X network

École 理工學院已經存在深根柢固的同儕網路。

當同學遇到任何困難時,他可以藉由這個網路尋求協助,也就是說,他想要在網路上找到另一個人尋求協助,他必須由中間人代為轉達。

特別注意:同儕關係都是對稱的,而且必然可以找到所有人。

寫一個程式計算最少的中間人個數。

Input


輸入第一行有一個整數,表示有多少測資組。

對於每組測資,第一行會有一個整數 N (1 <= N <= 105),同儕編號為 0 到 N-1。

接下來會有 N 行,每行前 2 個整數 c, nc ( <= 100) 表示同儕編號,以及關係個數。

接下來會有 nc 個整數緊接在後,表示 c 的同儕。

最後一行會有兩個整數 c1c2 ,表示 c1c2 求助。

Output


對於每組測資,分別輸出 
c1, c2, 和最少中間人個數。

Sample Input 


1

4
0 3 1 2 3
1 1 0
2 2 0 3
3 2 0 2
1 2

Sample Output 


1 2 1

388 - Galactic Import

隨著新系統的引進,星系之間的出口進口貿易變得更加容易,HyperCommodities 打算進口物品從不同的星系,每個星系中的行星的原物料都有不同的價值。

  • 每個星系中最多有 26 個星球,每個星球編號從 'A' 到 'Z'。
  • 每個星球都可以進口和出口,而且都有不同的原物料。
  • 其中會存在兩個星球間有貿易路線,每當原物料由其他星球轉口出去,每轉一次原物料價值將會折損當下的 5%。
  • 至少存在一個星球會向地球開放貿易。
找到其中一個星球的原物料進口到地球具有最高價值。

Input

輸入有多組測資。

每組測資第一行會有一個整數 N 表示描述星球間的關係。

每一行的格式如下:
  1. 星球的英文字母代號
  2. 空白
  3. 原物料的價值 d.dd
  4. 空白
  5. 一組字串,表示可以出口到的地方。以 '*' 表示地球。

Output

對於每組測資,輸出 ``Import from P'',P 為最高價值的星球代號。如果有多個,則選擇字典順序最小的。

Sample Input

1
F 0.81 *
5
E 0.01 *A
D 0.01 A*
C 0.01 *A
A 1.00 EDCB
B 0.01 A*
10
S 2.23 Q*
A 9.76 C
K 5.88 MI
E 7.54 GC
M 5.01 OK
G 7.43 IE
I 6.09 KG
C 8.42 EA
O 4.55 QM
Q 3.21 SO

Sample Output

Import from F
Import from A
Import from A

11487 - Gathering Food

冬天來臨,天氣越來越冷,許多動物採取不同的方法來適應冬天。

- 遷徙,移動到溫暖的地方。
- 很少有動物仍在冬天保持活躍。
- 冬眠,動物藉由深沉睡眠,降低體溫、心跳速度,而在秋天時準備足夠的食物以及體內脂肪。


而這題著重於第三點的例子,觀察一種特別的熊。


這種熊在一個特別的森林,將這個森林定義為 N x N 的網狀格子,每個格子只會有下列三種資訊。


'.' 空地
'#' 障礙物
[A-Z] 英文字母

森林中至少存在一個英文字母,所有字母只會存在唯一一個,如果存在有 n 個字母,這必然只會存在前 n 個字母,即當 n = 3 時,確切只會有 1 A, 1 B, 1 C

這些字母表示當地區的食物,熊會從 'A' 開始搜集其他食物,每次只會往四個方向(上下左右)移動,由於特別的習性,會根據字母順序搜集食物,當熊到達食物所在地時,才能將食物收集起來。


計算熊收集食物的最少移動步數,以及在最少移動步數下,有多少移動方法。


// 翻譯備註,非要撿起的食物必須當做障礙物。
Input

有多組測資,每組第一行有一個整數 N (N <= 10)。

Output

對於每組測資,輸出測資組編號,如果無法搜集到所有食物,則輸出 ‘Impossible’。

反之分別輸出最短路徑長及路徑個數,輸出 mod 20437 後的結果即可。

Sample Input                             Output for Sample Input

5
A....
####.
..B..
.####
C.DE.
2
A.
.B
2
A#
#B

0
Case 1: 15 1
Case 2: 2 2
Case 3: Impossible

11655 - Waterland

西元 3110 年,大多數的陸地已經陷入水中,只剩下少數的島嶼。水島是由許多小島嶼所組成,所有小島嶼間藉由隧道連接,每個隧道兩端確切只有 2 個島嶼。


水島總統想要去 Yablonoi 島度假,精英安全部隊必須要護送總統從 Kurai 島Yablonoi 島,他們必須選擇安全的隧道來前進。在每種可能路徑中,每條隧道都只能經過一次。


安全部隊每次派出有很多小隊一起出發,嘗試每種不同的路徑,每經過島嶼時,會留下一個小隊駐守,每次都只會剩下一個小隊抵達 Yablonoi 島,而一座小島可能會有多個小隊來自於不同次出發的。

現在安全部隊的負責人要計算總共派發出的小隊個數,並且計算有多少個小隊抵達目的地。
Input
測資第一行有一個整數 N (N < 40),表示測資組數。

對於每組測資,第一行會有兩個整數 L, T (2 <= L <= 5000, 0 <= T <= 5*L),分別表示島嶼個數,以及安全隧道的個數。

接下來會有 T 行,每行上有兩個整數 x, y (1 <= x, y <= L),表示有一條有向隧道從 xy。對於任兩個島嶼間最多有一條隧道連接,而島嶼編號 1 為 Kurai 島,島與編號 LYablonoi 島。

Output

對於每組測資,輸出測資組編號,以及兩個整數 S, D,分別表示總共需要的小隊數,以及最後抵達目的地的小隊總數。

只需打印出 mod 100000 的結果即可。

Sample Input                              Output for Sample Input

3
2 1
1 2
4 4
1 2
1 3
2 4
3 4
4 3
1 2
2 3
3 4
Case 1: 1 1
Case 2: 4 2
Case 3: 3 1

986 - How Many

在一個平面上的格子點中,考慮每次步驟為加上 (1,1) 或 (1,-1),並且不會低於 x 軸,而每個山頂高 k 定義為在 (1,1) 步驟後 y=k 且緊接著 (1,-1) 步驟。

如下圖所示,左圖有 4 個山頂,其中 2 個山頂高度 2,另 2 個山頂高度 3。

右圖則有 3 個山頂,高度分別為 1, 2, 3。



Problem

從 (0, 0) 出發,中止於 (2n, 0),並且確切存在 r 個山頂高度 k。

Input

輸入有多組測資。

每組一行有 3 個整數 n, r, k。
(1 <= n < 20, 0 <= r < 20, 1 <= k < 20)

Output

對於每組測資輸出一行,一個整數表示有多少種路徑走法, 答案小於 231

Sample Input


3 1 2
10 3 2

Sample Output


2
2002

10350 - Liftless EME

EME 建築在 2002 年到 2020 年間越建越高,但是電梯數量仍維持定量。因此這對於學生到教室是個很重要的問題,對於 ACM 練習賽的選手特別重要,比賽從每個星期二的 2:00 pm 開始,此時電梯和樓梯都擠滿了實驗室的學生。

所有參賽選手打算抄捷徑到 ACM 教室,他們偷偷地在每一層天花板挖洞,並且每個洞向下放置一個樓梯,因此他們可以藉由這些到達另一個樓層,藉以避面大批人群。


問題為:現在有很多捷徑,計算一個最短路徑抵達目的地。

目標從地面 (0 層)  到達頂樓 (n-1 層),特別注意參賽者只會往上爬。

Input

輸入有多組測資。

對於每組測資,第一行會有一個測資組名稱,長度不超過 12 字元。

接著會有 2 個整數 n, m,分別表示 EME 建築的樓層數量、每一層有的洞數量。

接下來會有 m(n-1) 行,每行上會有 m 個整數,在第 k*m+i 行上,表示在第 k 層的第 i 個洞的資訊,該行的第 j 個整數表示到第 k+1 層的第 j 個洞的時間。

(0 <= k < n-1 < 120, 1 < i, j < m <= 15)

Output

對於每組測資輸出兩行,第一行為測資組名稱,第二行為最少時間從地面到頂樓。

Sample Input

Sample001
3 2
1 2
3 4
5 6
7 8

Sample Output

Sample001
10