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

2013年8月13日 星期二

1198 - The Geodetic Set Problem

G = (V, E) 表示一連通圖,不存在 loops(自己連自己) 和重覆的邊,V, E 分別表示節點與邊。

對於 u, v V 必然會存在一條最短路徑,而 I (u, v) 定義為在 u - v 最短路徑上的點所產生的集合,而 S V


如果 I(D) = V,則這節點集合 D 被稱作為 G 的其中一個 geodetic set The geodetic set problem 就是要檢驗 D 是否為 geodetic set

以上圖為例,I(2, 5) = {2, 3, 4, 5},即所有可能在最短路徑上的所有點,然而
I(2, 5) 並不是一個 geodetic set,因為並不等於 {1, 2, 3, 4, 5}。

假如 D = {1, 2, 5},則 I(D) = V,同時 {1, 3, 4} {1, 4, 5} 也都是 geodetic set,但
{3, 4, 5} 卻不是,因為節點 1 並不在 I(D) 中。


Input

輸入有多組測資,每組第一行有一個整數 n (2 <= n <= 40) 表示圖有多少節點。


接下來會有 n 行,在第 i(1 <= i <= n)上會有數個整數,表示與節點編號 i 相連的點。

接著會有一行一個整數 q,表示接下有多少組詢問
 

每組詢問一行,行上的每個整數 D 集合內的節點編號。
Output

對於每組詢問的 D,判斷 D 是否為
geodetic set

Sample Input

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

 
Sample Output

yes
yes
no
yes
yes
no

925 - No more prerequisites, please!

最近,我正在準備給予少部分學生的畢業課程指導,向同事要課程之間的關係,而有部分課程需要先修課程,定義這先修課程的集合為 c,也就是說學生必須先修過 c 的所有課程,才能修這門課。

不過同事太熱心了,給了過多的資訊,過多是什麼意思,接下來我會解釋 ...:

  • 假設有課程名為 ca, cb, cc, cd, cd
  • 必須先修過 ca 才能修 cb必須先修過 cb 和 cc 才能修 cd
    必須先修過 cd 才能修 ce。
  • John 負責課程 cd,告訴我先修課程為 cc, cb, ca
  • Elizabeth 負責課程 ce,告訴我先修課程為 cd, cc, cb, ca
但我發現只需要說明先修課程 cc, cb,就可以修 cd 課程,因為 ca 已經在 cb 的先修課程中。同樣地,只需要說明 cdce 的先修課程即可,因為 cd 已經有 cc, cb, ca 的先修課程條件了。

不幸地,並不是每個同事都給予最小化的先修課程,太多太多的資訊蜂擁而來,希望有個機器人可以幫忙處理這些資訊,並寫告訴我最小化的先修課程。


Input

輸入第一行有一個整數,表示接下來會有多少測資組,至多 1000 組。

每組第一行會有一個整數 k,表示課程總數,而接下來會有 k 行,分別為課程名稱。
課程名稱由小寫英文字母構成,長度最多為 20。


接下來有一個整數 j,表示接下來有 j 行先修課程的資訊。
每一行第一個為課程名稱,第二個整數為先修課程的個數,接下來為先修課程的名稱。

(0 < k, j <= 120)

Output

按照輸入順序,依序輸出該課程的先修課程清單,對於先修課程清單同樣按照輸入順序輸出。

Sample Input

2
5
cc
ca
ce
cb
cd
3
ce 4 cd cb cc ca
cd 3 cb cc ca
cb 1 ca
9
dg
di
dc
df
de
dd
da
dh
db
7
dg 3 da de df
dd 2 da db
df 1 de
dc 1 db
dh 5 da de dg df dc
de 2 da dd
di 2 df dd


Sample Output 

cb 1 ca
cd 2 cb cc
ce 1 cd
dc 1 db
dd 2 da db
de 1 dd
df 1 de
dg 1 df
dh 2 dc dg
di 1 df