| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 7101 | 寶石奇兵 |
|
| 7102 | 完美洗牌 2.0 |
|
| 7103 | 切割木棍 |
|
| 7104 | 陣列和問題 |
|
| 7105 | 陣列和問題 2 |
|
Description
寶石奇兵是一個簡單的動作遊戲，主要是打敗遊戲中的敵人與收集關卡中的各式寶石，因為遊戲的場景細緻，並且容易上手，所以吸引了不少玩家。為了增加遊戲的樂趣，遊戲公司新增了線上排名的功能，透過連上網路將自己的紀錄上傳，就能夠加入排名。每個紀錄包含玩家名稱、分數、以及過關時間，為了讓玩家能夠快速知道其他排名的分數和時間，遊戲公司提供了一項查詢功能，能夠查到所有第 k 名的紀錄。排名的規則如下：如果紀錄 A 的分數比紀錄 B 還要高，則 A 的排名較高；如果兩者分數一樣的話，則過關時間較少的紀錄排名較高；如果分數和時間都一樣，則並列同一名。
|
名次 |
玩家名稱 |
分數 |
過關時間 |
|
1 |
hanazawa |
1989 |
225 |
|
1 |
kana |
1989 |
225 |
|
2 |
yamato |
1900 |
300 |
|
3 |
kate |
1900 |
600 |
|
3 |
amethyste |
1900 |
600 |
|
4 |
george |
1900 |
650 |
|
5 |
manticore |
1850 |
215 |
表一
例如：表一是從第 1 名到第 5 名的紀錄。如果查詢第 4 名，則顯示 george 的紀錄；如果查詢第 3 名，會顯示 kate 和 amethyste 的紀錄。假設目前有 N 筆紀錄以任意順序排列，並且需要查詢 M 個名次，請你寫一個程式模擬這個功能。
Input
第一行是一個整數 T (T £ 20)，接下來有 T 組測試資料。
每組測試資料的第一行是兩個正整數 N (N £ 10,000) 和 M (M £ 10,000)，接下來 N 行代表 N 筆紀錄，每筆紀錄包含玩家名稱、分數和通關時間，玩家名稱最多由 20 個小寫英文字母所組成，分數和時間是小於 1,000,000,000 的非負整數。之後有 M 行，表示有 M 個查詢，每一行只有一個數字 k (k > 0)，表示要查詢第 k 名的紀錄。
Output
一共有 T 組輸出。每組的第一行輸出 “Record Set #C”，代表第 C 組測試資料，之後對每個查詢輸出兩個部分，第一部分是分數和過關時間，兩個數以一個空白隔開，輸出在同一行，第二部分是所有第 k 名的玩家名稱，每個名稱各占一行，並且以字典排序的順序輸出。
你可以假設第 k 名一定存在。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
現在給你一副特製的撲克牌，總共有 2n 張牌，每張牌有一個編號，編號的範圍從 1 到 2n，而且任兩張牌的編號是不相同的。
考慮一副新的撲克牌，其編號從上到下剛好是由小到大排列，以下說明如何對這副牌做完美洗牌。首先將撲克牌由上到下平分成兩堆，第一次洗牌之前，會分成 {1, 2,…, n} 和 {n, n + 1 , …, 2n} 左右兩堆，一般洗牌是將撲克牌面朝下左右交錯的洗，之所以稱作為完美洗牌，代表他有以下的特性：
1. 同一堆的牌在洗完牌之後必定不會放在相鄰的位置，也就是洗牌每次都是左右各一張的交錯。
2. 每次洗牌的兩堆牌必定平分成等量的兩份。
3. 左手邊是撲克牌上面的 n 張，右手是剩下的 n 張。
4. 每次洗牌交錯時必定先從左邊開始。
根據這樣的規則，一副撲克牌在第一次洗牌之後的順序會變成：
{n + 1, 1, n + 2, 2, n + 3, 3, …, 2n - 1, n - 1, 2n, n}
請你寫一個程式去得到一副撲克牌經過完美洗牌 k (0 £ k £ 10,000,000) 次後，撲克牌的排列情況。
Hint: 作業的完美洗牌可以直接用k = k%52，但是這個數字和牌的張數一樣只是作業題湊巧而已。
Input
第一行有一個正整數 T (T £ 30)，代表接下來有幾筆測試資料。
接下來 T 行，每行都有兩個數字 n ( 1 £ n £ 500) 和 k (0 £ k £ 10,000,000)，代表一副新的撲克牌經過 k 次的完美洗牌。
Output
每筆測試資料各佔兩行。
每筆測試資料，第一行輸出 "Case C:" 表示第 C 筆測資，下一行輸出經過 k 次完美洗牌後由上到下的排列順序，相鄰兩個數字之間以一個空白隔開，第一個數字前面以及最後一個數字後面不可以有空白。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
你的任務是替一家叫 Analog Cutting Machinery (ACM) 的公司切割木棍。切割木棍的成本是根據木棍的長度而定，而且切割木棍的時候每次只切一段。
很顯然的，不同切割的方式會有不同的成本。例如：有一根長 14 公尺的木棍必須切成 2, 2, 5, 5 公尺。這個時候就有幾種選擇了。你可以選擇先切成兩段 7 公尺長的木棍，再分別將兩段切成 2 和 5 公尺，其成本為：14 + 7 + 7 = 28。但是如果你選擇先切成 5 和 9 公尺，然後再將 9 公尺的木棍切成 4 和 5 公尺，最後將 4 公尺的木棍分成 2 半，其成本為：14 + 9 + 4 = 27，這成本就是一個較好的選擇。
請你寫一個程式找出切割一根木棍所需最小的成本。
Input
第一行是一個正整數 T (T £ 20)，表示有幾組測資。
每組測試資料有 2 列，第一列包含 2 個整數 N (1 £ N £ 50) 和 L (2 £ L £ 1,000)，代表需要切出來的段數以及需要切割的木棍的長度。第二列是 N 個正整數，代表需要切出來的木棍長度。
Output
對每一組測試資料，輸出最小的切割成本。請參考 Sample Output。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
給一個 m ´ n 大小的二維陣列(array) A，並且每個數都是非負整數，此外給一個非負整數 x。現在湯姆想要知道是否存在一個較小的子陣列(sub-array) A’，裡面的數加起來的和是 x。例如：一個 4 ´ 3 大小的陣列 A (如下圖所示)，x = 20，則以 a2,1 為左上角、a3,2 為右下角的子陣列 A’ 的和等於 x = 20。請寫一個程式幫湯姆判斷找出這個陣列。
Input
測試資料的第一行是一個正整數 T (T £ 50)，表示接下來有 T 筆測試資料。
每一筆測試資料包含三個部份，第一部分是兩個正整數 m 和 n (1 £ m，n £ 10) 表示陣列大小為 m ´ n。第二部分有 m 行，每一行有 n 個數字，兩個整數之間以一個空白隔開，第 i 行代表在陣列中的第 i 列的 n 個數字。第三部分是一個非負整數 x。
每筆測資保證陣列中所有的數字和小於 1,000,000,000。
Output
每一筆測資各占一行，如果存在一個子陣列 (sub-array) 的和是 x，輸出四個整數 “r1, c1, r2, c2”，表示以 
Sample Input Download
Sample Output Download
Tags
Discuss
Description
給一個 m ´ n 大小的二維陣列(array) A，並且每個數都是非負整數，此外給一個非負整數 x。現在湯姆想要知道是否存在一個較小的子陣列(sub-array) A’，裡面的數加起來的和是x。例如：一個 4 ´ 3 大小的陣列 A (如下圖所示)，x = 20，則以 a2,1 為左上角、a3,2 為右下角的子陣列 A’ 的和等於 x = 20。請寫一個程式幫湯姆判斷找出這個陣列。
注意！本題測試資料的範圍較大，請參考 Input 說明。
Input
測試資料的第一行是一個正整數 T (T £ 20)，表示接下來有 T 筆測試資料。
每一筆測試資料包含三個部份，第一部分是兩個正整數 m 和 n (1 £ m，n £ 50) 表示陣列大小為 m ´ n。第二部分有 m 行，每一行有 n 個數字，兩個整數之間以一個空白隔開，第 i 行代表在陣列中的第 i 列的 n 個數字。第三部分是一個非負整數 x。
每筆測資保證陣列中所有的數字和小於 1,000,000,000。
Output
每一筆測資各占一行，如果存在一個子陣列 (sub-array) 的和是 x，輸出四個整數 “r1, c1, r2, c2”，表示以 為左上角，