16
上機程式設計
環境練習試題
17
Hello World !(Hello)
Time limit:
1 Second
Memory limit:
512 MB
好的開始是成功的
㇐半，很多人第㇐個撰寫的程式就是
Hello World !
這
㇐題來讓我們回味寫程式最初的感動。
Input
輸入只有
㇐行，為㇐個人名
S。
• 1 ≤ |S| ≤ 30
• S 由英文字母大小寫，以及空白組成
Output
請對輸入的人名打招呼，格式參見範例輸出。
Example
Standard Input
Standard Output
Yamada
Hello, Yamada
Constraints
題目額外限制：
• 50% 名字不包含空白字元。
• 50% 無其他限制。
18
A + B 問 題 (Plus)
Time limit:
1 Second
Memory limit:
512 MB
著急的小明需要計算各位的成績，但是因為今天的計算機被電壞了，無法使用，因此希望你可以
幫忙寫
㇐個程式來快速計算成績，只要把兩個數字的加總起來就可以了。你可以幫忙嗎
?
Input
有多筆測資，以
EOF 結束。
每筆測資佔
㇐行，有兩個正整數
x, y。
• 1 ≤ x, y ≤ 2
31
− 1
Output
對於每
㇐筆輸入，輸出㇐行，為㇐個整數，即輸入兩數字的總和。
Example
Standard
Input
Standard Output
2
3
4
7
Constraints
題目額外限制：
• 10% x, y ≤ 10。
• 90% 無其他限制。
19
最小公倍數問題
(LCM)
Time limit:
1 Second
Memory limit:
512 MB
我們定義兩個正整數
a, b 的最小公倍數 c ，是滿足數字同時為 a 與 b 的倍數中，最小的正
整數。給你兩個正整數，你能找出他們的最小公倍數嗎
?
Input
有多筆測資，以
EOF 結束。
每筆測資佔
㇐行，有兩個正整數
x, y。
• 1 ≤ x, y ≤ 2
31
− 1
Output
對於每
㇐筆輸入，輸出㇐行，為㇐個整數，即輸入兩數字的最小公倍數。
Examples
Standard
Input
Standard Output
6
30
8
56
Constraints
題目額外限制：
• 10% x, y ≤ 10。
• 15% x, y ≤ 1000。
• 75% 無其他限制。
20
上機程式設計試題
A.
髮廊服務優化問題
(barbershop)
問題描述
瑪莉是美美髮廊裡手藝高超的髮型設計師，這天美美髮廊同時來了
n
位客人指定瑪莉設計髮型，因
每位客人所指定的服務不同，所需的時間也不盡相同。一位客人所需等待的時間為他前面所有客人的
服務時間與自己服務時間的總和。為了提高髮廊的服務品質，瑪莉希望這
n
位客人總共等待的時間
最短，請幫瑪莉決定服務順序並計算這
n
位客人最短的等待時間總和。
假設有三位客人
A
、
B
、
C
，這三位客人分別需要的服務時間為
1
、
2
、
3
。如果瑪莉提供服務的
順序為
A → B → C
，那麼
A
需要等待
1
分鐘，
B
需要等待
1 + 2 = 3
分鐘，
C
則需要等待
1 + 2 + 3 = 6
分鐘。這三個客人總共等待時間為
1 + (1 + 2) + (1 + 2 + 3) = 10
。如果瑪莉提供服務
的順序為
C → B → A
，那麼這三個客人總共等待時間為
3 + (3 + 2) + (3 + 2 + 1) = 14
。因為
10
是所有服務順序中總等待時間最短的，因此本例的答案需輸出
10
。
輸入格式
n
t
1
t
2
· · · t
n
• n
代表客人數量
• t
i
為第
i
位客人所需的服務時間
輸出格式
S
• S
為整數，代表最小的等待時間總和
測資限制
• 1 ≤ n ≤ 200
• 1 ≤ t
i
≤ 200
•
上述變數皆為整數
21
範例測試
Sample Input
Sample Output
3
3 1 2
10
5
5 2 1 4 3
35
10
9 5 3 4 10 1 7 6 8 2
220
評分說明
本題共有三組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。
子任務 分數 額外輸入限制
1
20
t
i
≤ 3
2
30
t
i
≤ 100
3
50
無額外限制
22
B.
校園公車
(bus)
問題描述
H
大學設有校園公車在固定路線上來回行駛。想搭乘校園公車的師生或訪客，可以在公車路線上的
任意地點以招手方式請駕駛停靠後上車。由於校園廣大，為方便師生與訪客利用校園公車，校方打算
開發一個手機
app
，其中一個服務是透過
GPS
來定位出使用者在校園中的位置，提供最接近的上車
地點。
H
大學校園內的任一位置皆能用二維座標
(x, y)
表示。校園公車的路線是由
n
條線段所組
成，我們以出發點
P
0
(x
0
, y
0
)
、轉折點
P
1
(x
1
, y
1
), P
2
(x
2
, y
2
), . . . , P
n−1
(x
n−1
, y
n−1
)
、以及終點
P
n
(x
n
, y
n
)
來描述。在任意兩個相鄰的轉折點之間，公車以直線運行。以下圖為例，公車路線為
P
0
(1, 3), P
1
(3, 3), P
2
(5, 1), P
3
(7, 2), P
4
(7, 4), P
5
(9, 3)
。如果手機使用者在
O
1
(2, 1)
，那麼
app
會回
報最接近的上車地點在
A(2, 3)
，距離是
2
；如果手機使用者在
O
2
(5, 0)
，那麼
app
會回報最接近的
上車地點在
B(5, 1)
，距離是
1
。
P
0
P
1
P
2
P
3
P
4
P
5
A
B
O
1
O
2
d = 2
d = 1
給定一位
app
使用者的位置以及校園公車的路線，請寫一支程式來計算該使用者與最近上車地點
的距離。
輸入格式
x y n
x
0
y
0
x
1
y
1
...
x
n
y
n
• (x, y)
為使用者的位置
• n
為校園公車路線的線段數
• (x
0
, y
0
), (x
1
, y
1
), . . . , (x
n
, y
n
)
為校園公車的路線（包含起點、轉折點與終點）
23
輸出格式
ans
• ans
為一非負浮點數，代表使用者與最近上車地點的距離
測資限制
• 1 ≤ n ≤ 100
• 0 ≤ x, y ≤ 10
6
•
對於所有的
i ∈ {0, 1, . . . , n}
，皆有
0 ≤ x
i
, y
i
≤ 10
6
•
對於所有的
i ∈ {0, 1, . . . , n − 1}
，皆有
(x
i
, y
i
) 6= (x
i+1
, y
i+1
)
•
輸入的數皆為整數
24
範例測試
Sample Input
Sample Output
2 1 5
1 3
3 3
5 1
7 2
7 4
9 3
2
5 0 5
1 3
3 3
5 1
7 2
7 4
9 3
1
10 3 1
4 4
9 4
1.414213562373095
10 3 2
9 4
9 13
10 13
1.414213562373095
評分說明
本題共有三組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。若正確答案非
0
，輸出和正確答案的絕對或相對誤差在
10
−6
就算正確。若
答案為
0
，輸出必須要和正確答案絕對誤差在
10
−6
以內。
子任務 分數 額外輸入限制
1
30
校園公車路線為一垂直或水平線段，且所有座標皆在
100
以內
2
30
校園公車路線的每一個線段都是垂直或水平
3
40
無額外條件限制
25
C.
街頭藝人
(busker)
問題描述
阿甘是一位街頭藝人，他到各地旅行，沿途表演賺取生活花費。
此次阿甘旅行到妙世界國，妙世界國的地圖上有很多節點，每個節點可以細分成兩種：都市和村莊。
已知妙世界國有
n
座都市，都市的節點編號分別為
1, 2, · · · , n
，有
m
條單向大道連接這些都市，每
條大道單向連接兩相異都市，並且在都市間會經過恰
k
座村莊。第
j
條大道沿途經過的村莊節點編
號分別為
(n + (j − 1)k + 1), (n + (j − 1)k + 2), · · · , (n + jk)
。
阿甘正思索著要如何規劃一條演藝路線。演藝路線必須從一個節點開始，沿著大道經過其他節點，
且沿途去過的節點不再經過，最後再回到一開始出發的節點。
另外，各地的物價有所不同，有時表演得到的小費足以應付他的開支，有時卻不�，已知編號
i
的
節點表演所獲取的總收支為
c
i
元，阿甘希望在這條演藝路線上，不能有入不敷出的情況發生，也就
是說如果一條演藝路線經過的節點依序是
δ
1
, δ
2
, · · · , δ
r
(
其中
δ
1
= δ
r
)
，那對所有整數
y ∈ [1, r]
要
滿足
P
y
x=1
c
δ
x
≥ 0
。阿甘把這種演藝路線叫做入能敷出演藝路線。
下圖的例子中有
m = 6
、
n = 5
、
k = 1
。圖中的紅色圓圈代表都市節點，藍色方形代表村莊節點。
圓圈與方形中的數字代表進入此節點後會得到的收支。節點右上角的數字則代表節點編號。
5
1
-1
2
3
3
2
4
-5
5
0
6
-4
7
-3
10
-3
8
-1
9
3
11
圖一
一條入能敷出演藝路線可以依序經過都市
1
(
此時阿甘口袋有
5
元
)
、村莊
10
(
口袋剩
5 − 3 = 2
元
)
、都市
4
(
口袋剩
2 + 2 = 4
元
)
、村莊
9
(
口袋剩
4 − 1 = 3
元
)
、都市
2
(
口袋剩
3 − 1 = 2
元
)
、
村莊
6
(
口袋剩
2 + 0 = 2
元
)
，而最後回到都市
1
(
口袋剩
2 + 5 = 7
元
)
，沿途都沒有入不敷出的
26
狀況。
如果兩條演藝路線經過的的大道集合相同只是起點不同，我們說這兩條演藝路線在同一個迴路上。
若和前一個例子在同一個迴路上，從都市
4
出發或是村莊
6
出發，也是入能敷出演藝路線。但從
村莊
9
出發第一站便入不敷出，不是入能敷出演藝路線。
由於妙世界國很龐大，手算過於耗時，阿甘拜託你幫忙輸出任何一條入能敷出演藝路線，並計算在
同一個迴路上有幾個都市和幾個村莊可以當作入能敷出演藝路線的起始節點。
輸入格式
n m k
c
1
c
2
...
c
n
x
1
y
1
c
n+1
c
n+2
· · · c
n+k
x
2
y
2
c
n+k+1
c
n+k+2
· · · c
n+2k
...
x
m
y
m
c
n+(m−1)k+1
c
n+(m−1)k+2
· · · c
n+mk
• n
代表都市數量。
• m
代表單向大道數量。
• k
代表每條單向大道上有幾個村莊。
• c
i
代表在第
i
個節點表演的收支。
• x
j
代表第
j
條單向大道的起點都市。
• y
j
代表第
j
條單向大道的終點都市。
27
輸出格式
請依照以下格式輸出一組入能敷出演藝路線。若存在多組入能敷出演藝路線，輸出任意一組即可：
r
δ
1
δ
2
· · · δ
r
city village
• r
代表入能敷出演藝路線走過的節點數量
• δ
i
代表入能敷出演藝路線的第
i
站的節點編號
•
輸出必須滿足
δ
1
= δ
r
• city
代表在同一個迴路上有幾個都市可以當入能敷出演藝路線的起始節點
• village
代表在同一個迴路上有幾個村莊可以當入能敷出演藝路線的起始節點
•
輸出的數皆為整數
若不存在演藝路線，則輸出唯一一行
0
：
0
測資限制
• 1 ≤ n ≤ 2000
• 1 ≤ m ≤ 8000
• 1 ≤ k ≤ n
• −10
8
≤ c
i
≤ 10
8
•
對所有整數
j ∈ [1, m]
保證
x
j
6= y
j
•
對所有整數
a, b ∈ [1, m]
保證若
a 6= b
則
x
a
6= x
b
或
y
a
6= y
b
•
輸入的數皆為整數
28
範例測試
Sample Input
Sample Output
5 6 1
5
-1
3
2
-5
2 1 0
3 2 -4
4 3 -3
4 2 -1
1 4 -3
5 1 3
7
6 1 10 4 9 2 6
2 1
2 2 1
-1
-1
1 2 1
2 1 0
0
2 2 1
-1
-1
1 2 1
2 1 1
5
4 1 3 2 4
0 2
評分說明
本題共有三組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。
子任務 分數 額外輸入限制
1
18
n ≤ 20
2
15
n ≤ 90
3
67
無額外限制
29
D.
汽車不再繞圈圈
(car)
問題描述
小戸川市以觀光和計程車的發達聞名，外國遊客們常常在城巿裡搭計程車往返各個景點。城巿裡的
道路交通網是一個有向圖（
directed graph
），每條道路的通行方向可以透過特殊的權限由主控台改
變。詳細一點來說，城市共有
n
個景點（編號由
1
至
n
）與
m
條道路（編號由
1
到
m
）。第
i
條道
路由
u
i
單向通往
v
i
，並且需要至少
c
i
（
c
i
≥ 1
）的管理者權限才能改變方向。管理權限可以由一個
正整數表示，數字越大代表權限越大；若管理者有
P
的權限，則他可以透過系統改變任意
c
i
≤ P
的
道路方向。
某天小戸川市的交通局被觀光客投訴部份計程車司機會利用城巿裡的道路載著乘客繞圈圈以收取更
高的費用。為了避免這個亂象，城巿的交通局長決定透過改變城市中某些道路的方向，使得城市中不
存在環，讓計程車司機們無法在城巿裡繞圈圈。交通局長請資訊專長的你幫忙計算至少要多大的權限
才能達成目標。請注意由於城市的都市規劃不佳，兩景點間可能有複數條道路存在或者完全無法到達
的情況發生。
以下圖為例，其中邊上的數字代表改變該條道路方向所需的權限，若管理者權限為
2
，並改變
(2, 1)
、
(2, 3)
這兩條道路的方向即可達成目標。這也是能達成交通局長目標的管理者權限最小�。
1
2
3
4
5
1
4
6
2
3
2
改變道路方向前
1
2
3
4
5
1
4
6
2
3
2
改變道路方向後
輸入格式
n m
u
1
v
1
c
1
u
2
v
2
c
2
...
u
m
v
m
c
m
• n
、
m
分別代表城市數與道路數
• u
i
、
v
i
、
c
i
代表第
i
條道路單向連接
u
i
到
v
i
，且改變方向需要的權限為
c
i
30
輸出格式
P R
e
1
e
2
...
e
R
• P
為一整數，代表達成交通局長目標需要最少的權限大小。若不需要改變任何道路方向即可達
成交通局長的要求，
P
請輸出
0
• R
為一整數，代表需要改變方向的道路個數
• e
i
為一整數，代表第
i
條想要改變方向的道路編號。注意同一條道路編號不可以在
e
出現兩
次以上，並且改變此條道路所需的權限也不可以超過
P
（意即必須滿足
c
e
i
≤ P
）
請注意雖然輸出的權限大小必須最小，但改變的道路數量可以是任意數量。若有多組改變方案可以
滿足要求，請輸出任意一組即可。
測資限制
• 2 ≤ n ≤ 10
5
• 0 ≤ m ≤ 10
5
• 1 ≤ u
i
, v
i
≤ n
，且
u
i
6= v
i
（
i ∈ {1, 2, . . . , m}
）
• 1 ≤ c
i
≤ 10
9
（
i ∈ {1, 2, . . . , m}
）
•
上面所有變數皆為整數
31
範例測試
Sample Input
Sample Output
5 6
2 1 1
1 5 4
5 2 6
2 3 2
3 4 3
4 5 2
2 2
1
4
2 1
1 2 6
0 0
6 7
5 2 6
2 1 1
2 3 10
3 4 3
4 5 2
1 5 4
4 5 1
2 3
2
5
7
評分說明
本題共有三組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。
子任務 分數 額外輸入限制
1
6
n, m ≤ 20
2
8
c
i
≤ 100
3
86
無額外限制
32
E.
天空競技場
(colosseum)
問題描述
臘月寒冬，小傑來到天空競技場磨練競技程式的技術並賺取金幣。天空競技場是一棟非常高的建築
物，遠遠看去彷彿有一百萬層那麼高。小傑來到的競技場是一棟
n
層樓的建築物，樓層標號為
1
到
n
，樓層編號越大代表所在位置越上面。參加者會在時間
0
時選擇任一樓層作為起點進入或直接離開
放棄挑戰，並可以在任意時間點任意樓層選擇結束挑戰並獲得累積的金幣獎勵。進到競技場後，參賽
者會從選擇的起點樓層開始一層一層往上直到離開，到結束挑戰前都不可跳過樓層也不可以往下面樓
層走。競技場設有高速移動的電梯，可以讓參賽者一瞬間移動到樓上一層，所以樓層之間的移動時間
可以視為
0
不計。
競技場每個樓層都有一位樓主，第
i
層的開設時間為
x
i
，挑戰門檻為
y
i
。參加者到樓層
i
時若所
持金幣未滿
y
i
則無法參加這個樓層的競技，參加者只能繼續往上走或結束挑戰。任何滿足金幣門檻
（所持金幣
y
i
以上）的參加者如果恰在開設時間
x
i
或之後到達第
i
樓的話就會強制發生戰鬥與樓主
競技，不能拒絕。此競技將耗費
t
i
的時間並於競技結束時獲取
w
i
的金幣。如果在時間
x
i
之前到達
i
樓且滿足金幣門檻的參賽者，則可以選擇在這層樓等待至開設時間或是直接繼續往上走。
小傑對競技場的挑戰非常感興趣，但不巧他今天得在時間
m
或以前離開競技場回去參加程式比賽，
請幫小傑規劃從哪一個樓層開始以及要在哪些樓層等待，讓他可以在
m
的時間內得到最多的金幣。
33
下面是一個
n = 6, m = 9
的例子，左方表格內是各樓層的開始時間
x
i
、門檻�
y
i
、競技耗時
t
i
與可獲金幣
w
i
，右圖中列舉了三種可能（但非全部）的路線。
(a)
路線從
1
樓進入，因為到達時
1
樓
已達開設時間且滿足挑戰門檻所以必須競技，在一樓耗費
4
時間獲得
1
金幣。然後依序在
2, 3
樓獲
得
3
與
1
枚金幣。在時間
9
時共獲得
5
枚金幣離開。
(b)
路線由
2
樓進入，先在
2
樓等到
x
2
= 1
時參加競技，耗費
2
時間獲得
3
金幣。到達
3
樓時因為門檻不滿足直接進入
4
樓，
4
樓的開始時間
x
4
= 6
未到，選擇不等待直接進入
5
樓，之後等待
1
時間與耗費
5
時間獲得
5
枚金幣，總共獲取
8
枚金幣離開，這是本例中可獲得最多金幣的策略之一。
i
x
i
y
i
t
i
w
i
6
1
0
7
6
5
4
3
5
5
4
6
1
1
4
3
2
4
3
1
2
1
0
2
3
1
0
0
4
1
各樓層的開始時間及門檻
時間
樓層
m = 9
1F
競技
(1$)
2F
競技
(3$)
3F
競技
(1$)
(a)
等待
2F (3$)
上
5F
等待
5F (5$)
(b)
等待
6F (6$)
(c)
輸入格式
n m
x
1
y
1
t
1
w
1
x
2
y
2
t
2
w
2
...
x
n
y
n
t
n
w
n
• n, m
分別代表競技場樓層數與小傑可以參加競技的時間
• x
i
, y
i
, t
i
, w
i
分別為樓層
i
的開設時間、競技門檻、競技所需時間以及完成競技的獎勵
34
輸出格式
ans
• ans
為一個整數，代表最多可以得到的金幣數量
測資限制
• 1 ≤ n ≤ 3 × 10
5
• 0 ≤ m, x
i
, y
i
≤ 10
9
（
i ∈ {1, 2, . . . , n}
）
• 1 ≤ t
i
, w
i
≤ 1000
（
i ∈ {1, 2, . . . , n}
）
•
上面所有變數皆為整數
範例測試
Sample Input
Sample Output
7 15
0 0 3 1
0 0 2 3
0 4 3 1
0 0 1 4
0 7 5 5
0 3 4 3
0 7 2 5
20
6 9
0 0 4 1
1 0 2 3
2 4 3 1
6 1 1 4
4 3 5 5
1 0 7 6
8
1 5
0 0 100 100
0
35
評分說明
本題共有四組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。
子任務 分數 額外輸入限制
1
9
n ≤ 1000
2
19
x
i
= y
i
= 0
3
18
x
i
= 0
4
54
無額外限制
36
F.
鳳梨關稅
(pineapple)
問題描述
大洋上有
n
個島嶼聚落，為了方便起見將這些聚落從
1
到
n
編號。這些島嶼聚落使用著共通的貨
幣大洋銀幣。聚落間有繁盛的貿易，並且在這些聚落之間有一些固定的航線往來，這些航線是聚落間
的交流與物產貿易的主要手段。每一條航線都是往返於固定兩個聚落。若一航線是往返於聚落
u
與聚
落
v
，則以
{u, v}
或
{v, u}
表示該航線，兩種表示方法相同，代表聚落
u
與聚落
v
可以直航交易兩
地物產。如果聚落
u
與聚落
v
之間沒有航線直接往返，也可能透過複數條航線進行貿易。若存在一系
列的航線
{u, p
1
}, {p
1
, p
2
}, . . . , {p
r−1
, p
r
}, {p
r
, v}
，則聚落
u
與聚落
v
之間便可以進行貿易，反之
則不可以。
為了保護大洋的生態，所有聚落的共識是在任兩個島嶼聚落之間都能�進行貿易往來的前提下維持
盡可能少的航線，而經過一番推算後，僅需有
n − 1
條航線便足�。這些可以進行貿易的固定航線，
編號從
1
到
n
–
1
，分別以
{u
1
, v
1
}, {u
2
, v
2
}, . . . , {u
n−1
, v
n−1
}
表示。
在這片大洋上，每個聚落為了保護自己內部的產業不受到外部的低價商品傾銷、惡性競爭，因此針
對各項商品都設定有關稅。而在大洋上關稅課徵的方式是針對航線，在每一航線上，船上所裝載的商
品都要被抽一次稅金。依據商品的種類不同有不同的抽稅方式；而針對鳳梨，則是每一顆裝載在船上
的鳳梨都要被課徵一枚大洋銀幣。
貢丸居住在大洋上的米粉島，最近退休了在種鳳梨想要販售到大洋的其他聚落去。貢丸建立了自己
的品牌「貢丸鳳梨」，由於品質優良，口碑良好，他開始收到來自其他聚落的鳳梨訂單。為了要賺多一
點錢，他總會想辦法準備好鳳梨出口到其他島嶼去，並且依照被收取的關稅來調整售價。
近年自由貿易的風潮興起，有些航線開始針對特定的商品免除關稅，鳳梨也在其中。隨著時間經過，
貢丸需要不斷的依據變更的關稅來調整貢丸鳳梨的價格，避免過高的定價，傷害到貢丸鳳梨在市場上
的競爭力。
37
下面是一個例子，假設有
n = 5
個島嶼聚落，與
4
條航線
{1, 2}, {2, 3}, {2, 4}, {5, 2}
，米粉島的
編號是
1
，並有
3
筆訂單如下：
1.
出貨
5
顆鳳梨到編號
5
的島嶼
2.
出貨
2
顆鳳梨到編號
3
的島嶼
3.
出貨
5
顆鳳梨到編號
5
的島嶼
在前兩筆訂單之間，航線
{2, 3}
將會免除鳳梨的關稅，在後兩筆訂單之間，航線
{5, 2}
將會免除
鳳梨的關稅，所以三筆訂單分別會被課徵每顆鳳梨
2
、
1
、
1
枚大洋銀幣。下面三個圖為每一次免稅後
的航線圖，其中虛線為免關稅路線。
1
2
3
4
5
(a):
初始航線圖
1
2
3
4
5
(b):
第一次免稅調整後
1
2
3
4
5
(c):
第二次免稅調整後
貢丸的祕書幫忙他整理明年需要出貨的訂單，以及航線調整關稅的時程，貢丸想要請精打細算的
你，幫忙撰寫一個程式，算出每一筆訂單需要繳交多少關稅才能出貨給顧客。
38
輸入格式
n s t w
u
1
v
1
u
2
v
2
...
u
n−1
v
n−1
Query
1
Query
2
...
Query
t+w
• n
、
s
、
t
、
w
分別代表島嶼聚落數量、米粉島的編號、明年訂單總數及調整關稅航線的總數。
• u
i
、
v
i
代表第
i
條航線會在島嶼聚落
u
i
、
v
i
間往返。
• Query
i
代表第
i
個出貨或變更航線的資訊，越前面代表事件越先發生。
Query
i
有以下兩種可
能的格式
:
1.
出貨
x
顆鳳梨到編號
y
的聚落
1 x y
2.
航線
z
免稅
2 z
輸出格式
a
1
a
2
...
a
t
• a
i
代表第
i
筆訂單所需繳納的關稅總額
39
測資限制
• 1 ≤ n ≤ 10
5
• 1 ≤ s ≤ n
• 1 ≤ t ≤ 10
5
• 0 ≤ w < n
• 1 ≤ u
i
, v
i
≤ n
，且
u
i
6= v
i
•
任意聚落都可以透過給定航線互相航行
• 1 ≤ x ≤ 10
5
• 1 ≤ y ≤ n
• 1 ≤ z ≤ n − 1
，免稅資訊中相同的
z
不會重複出現
• Query
1
到
Query
t+w
中恰有
t
個出貨詢問以及
w
個免稅事件
•
上述變數皆為整數
範例測試
Sample Input
Sample Output
5 1 3 2
1 2
2 3
2 4
5 2
1 5 5
2 2
1 2 3
2 4
1 5 5
10
2
5
4 1 2 0
1 2
1 4
2 3
1 2 3
1 3 4
4
3
40
評分說明
本題共有三組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。
子任務 分數 額外輸入限制
1
17
n ≤ 100
，
x ≤ 1000
2
36
只有一條航線會停靠米粉島，且其餘島嶼聚落至多只有兩條航線會停靠
3
47
無額外限制
41
G.
天竺鼠遊行
(puipui)
問題描述
車車農場養了一些天竺鼠，這些天竺鼠很可愛也有很多粉絲，而農場在每週末舉辦的天竺鼠遊行更
是遊客的焦點之一。農場裡共有
n
隻天竺鼠，牠們的高度都不盡相同，我們用
h
i
來表示第
i
隻天竺
鼠的高度。農場主人希望挑選一些天竺鼠來參加遊行，由於這週恰逢連休遊客眾多，他希望能組成
p
個遊行隊伍來參加一場盛大的遊行，其中每個隊伍都由
k
隻天竺鼠排成環狀組成。並且為了讓本週遊
行更有看點，農場主人決定要調整隊伍的順序增加整齊度，讓每一個隊伍裡天竺鼠與其相鄰天竺鼠的
高度差距都不會太大，請你幫他計算所有可能的隊伍順序裡，相鄰天竺鼠最大高度差的最小�是多少。
舉例來說，
n = 14
、
k = 6
且
p = 2
，天竺鼠高度各為
(6, 9, 6, 4, 5, 5, 3, 6, 4, 8, 8, 7, 6, 1)
。農場主
人想要選出其中
12
隻天竺鼠排出兩個環狀隊伍，若選擇高度
(9, 6, 6, 5, 5, 4)
的天竺鼠順時針排在第
一個隊伍，高度
(3, 6, 4, 8, 8, 7)
的天竺鼠依順時針排在第二個隊伍。此時第一個隊伍的最大高度差為
|9 − 4| = 5
，第二個隊伍的最大高度差為
|4 − 8| = 4
。我們說這個排列方式最大的高度差為
5
。
另一個排列方式為如下圖的兩個環狀隊伍（剩下高度
9
與
1
的天竺鼠本週休息不參加遊行）。圖中
每個圓圈代表一隻天竺鼠，圓圈內數字代表天竺鼠高度，而兩個圓圈之間的數字則是他們的高度差。
這個選取與排列方式的最大高度差是
2
，是所有可能選取與排列方式中最小的，因此本範例的答案是
2
。
6
5
6
5
3
4
1
1
1
2
1
2
隊伍一
8
7
8
6
4
6
1
1
2
2
2
2
隊伍二
42
輸入格式
n k p
h
1
h
2
· · · h
n
• n, k, p
分別代表天竺鼠個數、每個隊伍的天竺鼠數以及隊伍數
• h
i
為第
i
隻天竺鼠的高度
輸出格式
ans
• ans
為整數，代表所有隊伍相鄰天竺鼠高度差的最小�
測資限制
• 1 ≤ n ≤ 10
6
• 2 ≤ k ≤ n
• 1 ≤ p ≤ n
• kp ≤ n
• 1 ≤ h
i
≤ 10
9
•
上面所有變數皆為整數
範例測試
Sample Input
Sample Output
5 5 1
3 8 5 9 4
4
14 6 2
6 9 6 4 5 5 3 6 4 8 8 7 6 1
2
43
評分說明
本題共有四組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。
子任務 分數 額外輸入限制
1
15
k = n
，
n ≤ 10
，
p = 1
2
25
k = n
，
n ≤ 10
5
，
p = 1
3
17
p = 1
4
43
無額外限制
44
H.
鐵路鋪設
(rail)
問題描述
古力德市是一座相當特殊的城市。不同於一般的同心圓狀，古力德市是
2 × L
的棋盤狀，從空中俯
瞰就像一條巨大壯觀的蟒蛇，這個景色也吸引了不少觀光客。近年來，為了提升觀光客訪問古力德市
的體驗，古力德市政府決定在每一格的正中央設立火車站，並鋪設鐵路路線來連接這
2L
座火車站。
一段鐵路連接相鄰兩個方格的車站，並根據這兩個方格是否為對角線相鄰分為長鐵路與短鐵路，如
下圖所示。
兩種長鐵路
兩種短鐵路
若兩段鐵路共用同一座車站，則稱這兩段鐵路屬於同一條路線，當然每座車站都要有一條路線經
過。另，鋪設多條路線是被允許的，但因成本問題每一條路線最多只能有一段長鐵路。最後，為了避
免外地觀光客坐錯車降低訪問體驗，每條路線都必須是環狀的（確保搭乘順時針或逆時針方向的車都
會抵達目的地），且任兩條路線不會有任何的重疊或交叉（意即每座車站皆恰有一條路線經過一次）。
給定古力德市的寬度
L
，請求出有多少種可能的鋪設方式。因為這個數字可能很大，你只要求出鋪
設方法數除以
10
9
+ 7
的餘數就行了。
以下為
L = 4
的範例：在
2 × 4
的地圖中，共有
6
種鋪設方式。
45
輸入格式
L
• L
為古力德市的寬度
輸出格式
ans
• ans
為一整數，代表鐵路鋪設方法數除以
10
9
+ 7
的餘數
測資限制
• 1 ≤ L ≤ 10
10
•
輸入的數皆為整數
範例測試
Sample Input
Sample Output
3
3
10
686
327
265488547
評分說明
本題共有四組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需
答對才會獲得該組分數。
子任務 分數 額外輸入限制
1
10
L ≤ 7
2
20
L ≤ 10
3
3
34
L ≤ 10
5
4
36
無額外限制
46