10611 - The Playboy Chimp

Luchu Bandor是一隻猴子，他想找交住的對象，所以他到"猴子女子學校"挑對像，他挑選對像的原則是：希望找到所有比他矮的猴子中最高的，或是所有比他高的猴子中最矮的。早上猴子女子學校的母猴子們會由矮到高依序排成一列(非遞減的順序)。請你幫他選擇其中兩個可能的人選。

Input

輸入只會有一組測試資料，第一列給定一個整數N(1 <= N <= 50000)表示母猴的數目，下一列會有N個整數，其值介於1~(2^31-1)之間，分別表示N隻母猴的身高，每個整數之間會以一個空白字元隔開，且以非遞減的順序列出。下一列有一個整數Q(1 <= Q <= 25000)表示欲查詢的次數，每個查詢會給定Luchu Bandor的身高，即接下來會有Q個整數，其值介於1~(2^31-1)之間，並以一個空白字元隔開。注意，Q個整數並非以遞增或遞減的方式列出。

Output

針對每次查詢，請在一列輸出兩個整數，並以一個空白字元隔開，第一個整數表示較矮的猴子中最高的高度，第二個數數表示較高的猴子中最矮的高度，若不存在請輸出X。

Sample Input                             Output for Sample Input

4 1 4 5 7 4 4 6 8 10

1 5 5 7 7 X 7 X

---

原文出處

10600 - ACM Contest and Blackout

為了舉辦"國際ACM世界學校競賽"，市長決定為每所學校提供穩定可靠的電力，為了達成這個目標，其中某一所學校的電力系統必須與發電廠直接連接，且部份學校間的電力系統亦需互相連接。

用來評估一所學校的電力是否穩定的原則為：1. 若某學校的電力系統與發電廠直接相連，則該學校的電力是穩定的，2. 或某學校與另一所電力穩定的學校直接相連，則該學校的電力也是穩定的。給定學校間彼此連線的成本，市長必須決定兩種可能的連線路線使得成本最小。成本 的計算為學校間的連線成本總和。請你幫市長找出兩種最便宜的連線路徑。

Input

輸入的一開始有一個整數T(1 <= T <= 15)表示測試資料的組數，接下有來T組測試資料，每組資料的一開始有兩個以空白字元隔開的整數N, M，N(3 <= N <= 100)表示學校的總數，M表示學校間可能的連線數，接下來有M組連線，每組有三個整數Ai, Bi, Ci，Ci(1 <= Ci <= 300)表示Ai與Bi兩所學校的連線成本。學校的編號為1~N。

Output

每組測試資料輸出一列，每列有兩個以空白字元隔開的整數S1, S2，分別表示最低連線成本與次低連線成本，S1 <= S2。你可以假設S1, S2必存在。

Sample Input	Sample Output
2 5 8 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 1 2 9 3 5 66 9 14 1 2 4 1 8 8 2 8 11 3 2 8 8 9 7 8 7 1 7 9 6 9 3 2 3 4 7 3 6 4 7 6 2 4 6 14 4 5 9 5 6 10	110 121 37 37

原文出處

10656 - Maximum Sum (II)

給定一列非負整數，請你找出總和最大的子序列。

Input

輸入有多組測試資料，每組資料的開頭有一個整數N(N < 1000)表示序列長度，接下來有N列，每列為一個非負整數，其值小於10000。當N=0表示測試資料結束。

Output

請每組測試資料輸出一列，每列有一到多個整數，表示原序列中其總和最大的子序列，請儘量使得子序列的長度最短。子序列長度最短為1。每個整數請以一個空白字元隔開。

Sample Input                               Output for Sample Input

2 3 4 0

3 4

---

原文出處

10642 - Can You Solve It?

請參考下圖的二維座標系統(迪卡爾座標系)，垂直為X軸，水平為Y軸。從座標上的一點移動到另一點的路徑如下圖所示，路徑的距離定義為：經過的座標點數加1，例如從(0, 3)到(3, 0)必須先經過(1, 2)與(2, 1)兩點，所以距離等於2+1=3，本題會給定兩個座標點，請你計算從出發點到目的點的距離，你可以假定所給的兩個座標點之距離一定是正的。

Input

輸入的第一列為一個整數 n (0 < n <= 500)表示測試資料的組數，接下來有 n 列測試資料，每列四個整數，其值介於0~100000之間(包含)，第一對整數表示出發點，第二對表示目的點，其格式皆為(x, y)。

Output

請以範列資料的格式輸出從出發點到目的點的距離，你可以假定從出發點一定可以到達目的點。

Sample Input

3
0 0 0 1
0 0 1 0
0 0 0 2
Sample Output
Case 1: 1
Case 2: 2
Case 3: 3

---

原文出處