| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 7015 | 最短格子距離 |
|
| 7018 | 子序列(Bonus) |
|
| 7019 | Interstar Transport |
|
| 7114 | Permutation 2.0 |
|
| 7115 | 清大狗博士布魯師的煩惱 |
|
Description
平面上有MxN個格子，每格的寬和高都是一個單位長度。
今天這些格子裡面有一些被標記起來，稱之為障礙格，我們要從指定的兩個非障礙格A和B，找出從A走到B的最短距離 ，
對於每個格子都只能往他上下左右相鄰的四個非障礙格走動，每走一格就會多一個距離。
舉例來說：
上圖中深藍色的格子為障礙格，我們從A走到B的最短距離是：
從A往下走4格，往右走4格，往上走2格，往右走2格，往下走3格。
所以A走到B的最短距離是15。
Input
第一行表示有T (T <= 30) 組測試資料。
對於接下來T組測試資料中：
第一行有兩個正整數M, N(0 < M < 100, 0 < N < 100)表示格子寬和高的數量
第二行有兩個數字(XA, YA)表示格子A的座標(0 <= XA < M, 0 <= YA < N)
第三行有兩個數字(XB, YB)表示格子B的座標(0 <= XB < M, 0 <= YB < N)
第四行有一個整數B表示接下來有幾個障礙格
接下來的B行中各有兩個數字(X, Y)表示障礙格子座標 (0 <= X < M, 0 <= Y < N)
Output
對於每一組輸出A到B的最短距離，如果A無法走到B，則輸出 -1表示。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
給一個字串S，該字串由不重複的小寫字母組成，且長度最長為15
列出從字串S挑出k個字母可以組成所有可能的子序列(就是在原字串S中的前後關係不會變動)
例如S = "bac"，k = 2
那麼所有可能的字串為："ba", "bc", "ac"
Input
第一行T (T <= 30)表示有幾筆測資
對於每筆測資都有兩行，第一行為字串S，第二行為數字k (0 < k <= 字串長度)
Output
對於每組測試資料，第一行輸出"Case #i:"表示第幾組測資
接下來按照字典排序輸出所有可能的子序列
Sample Input Download
Sample Output Download
Tags
Discuss
Description
2100年，宇宙傳輸將會成為事實。宇宙傳輸公司計畫了一些航班在一些人潮洶湧的行星上。
這些航班的花費已經預先決定了，而花費的單位叫做「嘎洛洛」。
對一些沒有直接航班的行星間而言，他們可以選擇一些直接航班可到之處當作中繼站(ex: A-B, B-C，那麼A可以到C)。
為了協助旅客們查詢航班，宇宙傳輸公司想要提供一個軟體讓旅客們可以直接找到最好的方式(花費最少的方式)從某星球到某星球，
輸出最好路徑上所有點。而如果有兩種以上的最好方法的話，就選擇編號較小的星球。
每個測試資料保證只有一個最好路徑。
技術規格
- 星球的最多26個，最少1個。星球用大寫字母來表示(A~Z)
- 各個星球的直接連線數最多200條，最少1條，每兩個星球之間最多只有一條直接連線。
- 各個連線的花費是一個自然數，最多到100嘎洛洛。
Input
第一行有兩個整數s, p，中間空一空白。s代表星球數，p代表直接連線數。
接下來一行有一個整數n(n <= 20)表示有多少個問題。
接下來的n行，每一行包含兩個字每ek和em，表示使用者正在找的最便宜的方式從星球ek到em。
Output
對每個詢問，輸出一行最好的路徑，起點、中繼點以及終點，每個點之間空一個空白格。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
有一個字串S，該字串僅包含大寫字母A-Z，且字串內不會有重複的字母。
假設S = "CAB"，我們要求S是字典排列中的第幾個排列，如下：
1. ABC
2. ACB
3. BAC
4. BCA
5. CAB <- S
6. CBA
所以我們知道S在字典排列中是第五個排列。
請你寫一個程式計算S是字串排列中的第幾個排列。
Input
第一行有一個數字T (T <= 100)表示有幾筆測試資料。
接下來T行中，每行都有一個字串S，字串長度不超過20。
Output
對於每筆測資各輸出一行 "Case #i: n"。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
布魯師是清大狗博士，他對於清大的校狗有很深的了解。根據他多年的觀察，他發現
校狗分很多幫派，布魯師想了一個很聰明的方法，他認為只要對每個幫派的其中一隻
狗下命令，通過他們彼此之間的訊息傳達，所有的狗就知道布魯師下了什麼的命令。
但是布魯師只知道任兩隻狗是不是同幫派的關係，他想請你幫他寫程式計算清大到底
有幾個狗幫派。
Input
每行會有兩個字串，代表兩個校狗的名字，也代表這兩隻狗之間是同幫派
如果讀到#，表示這組測資結束
每組測資最少有一種關係
每一行兩隻狗名不會相同
狗的名稱只會有大小寫英文字母
測資最多有200組，每組最多有70行，校狗最多有30隻，最少2隻, 校狗名稱最多20個英文字母
Output
對於每一筆測資輸出"Case i: n"，表示有幾個不同的幫派。