軟體設計實務精選進階題

第一題: 山洞探險 

問題敘述 為了尋找傳說中名為「Nice Boat」的寶船，誠哥決定進入一個山洞探險去！ 他經過漫長的日子而走到山洞的中心處後，就打算開始進行他的探險計畫。那麼，這是第幾天呢？他也數不清，所以他決定把這天就當成第一天。 在發現山洞是朝著南北向直直延伸的後，誠哥為了有效率地進行探險，決定這樣規畫他的旅程：假設該天是開始探險計畫後的第X天，若X為奇數，那麼他當天早上就會向北方走X步；若X為偶數，那麼他當天早上就會向南方走X步。除此之外，不會有其他的移動方式。由於山洞的長度非常非常的長，因此也可以假設他再也不會離開山洞。 舉例來說，一開始誠哥位於山洞的中心處，第一天他會向北方走1步，第二天他會向南方走2步，第三天他會向北方走3步，此時，誠哥位於山洞的中心處北方之2步距離。 晚上休息時，他由於神智不清，常常會忘了今天到底是第幾天，但是他可以透過觀察得知目前位置離山洞的中心處之距離。請幫忙誠哥計算今天是開始探險計畫後的第幾天。 輸入說明 測試資料的輸入共有一列，包含非零整數L。假設L為正整數，表示誠哥今天晚上在山洞的中心處之北方，且他離山洞的中心處之距離為L步；假設L為負整數，表示誠哥今天晚上在山洞的中心處之南方，且他離山洞的中心處之距離為(-L)步。 輸出說明 請輸出一列，其中包含一個正整數D，表示今天是開始探險計畫後的第幾天。 正確答案D滿足D≤1000000000。 範例輸入 -1 範例輸出 2

第二題: 同學早安

問題敘述 俠阿校長是一位喜歡和學生互動的校長，而她最為人所知的就是會在上學時，站在校門口和同學們說早安。 有天，一位同學感到好奇，校長接下來究竟會在校門口站著多久呢？他記錄了接下來校長開始站在校門口的時間，以及該次的結束時間，非常神奇的是，在這段時間內校長都一直站著，都不用休息的。 請幫忙算一下校長這次究竟總共站了多久。 提示： 由於俠阿校長實在太熱心了，她是有可能站隔夜的，但最久只會站 23 小時 59 分鐘。 輸入說明 輸入共有兩列。 第一列共有兩個整數 H_1,M_1，表示校長站在校門口的起始時間為H_1時M_1分。 第二列共有兩個整數 H_2,M_2，表示校長站在校門口的結束時間為H_2時M_2分。 輸入資料滿足0≤H_1,H_2≤23; 0≤M_1,M_2≤59。 輸出說明 請輸出一列，其中包含兩個整數H,M，並以一個空白隔開，表示校長這次總共站了 H 小時 M 分，須滿足 0≤H≤23; 0≤M≤59。 範例輸入 7 20 8 15 範例輸出 0 55

第三題：遞迴搜索

題目內容：

溫教授正在用心的出著程式設計競賽的考題。為了讓學生能更快地想到解法，避免給予學生太大的挫折，在幾經思考後，溫教授決定在題目名稱中放上與該題相關的解題方法，但不幸地遇到了一些小麻煩。

有些題目可能會與數種不同的解題方法有相關，而也可能有些不同的題目不巧的都與某種解題方法所相關。溫教授希望對每一題，都挑選恰好一種與該題相關的解題方法，來訂為該題目的名稱。此外，為了避免混淆，溫教授希望不同題目的名稱不可以重複。

教授已經知道每一題與哪些解題方法有相關，若想要在滿足上述條件限制的情形下，對每一題按照上述規則訂定其名稱，是否能找出至少一種符合規則的解法呢？

為了降低決定題目名稱的複雜度，每一套題目都各自獨立，不需要考慮不同套題目之間的題目名稱是否有重複。對每一套題目而言，只需要訂定恰好三題的題目名稱，且每一題恰好都與兩種解題方法有相關。

教授苦思良久後，決定請已經征服遞迴函數與回溯法搜索的你，協助他訂定每一套題目中三題的題目名稱。

輸入說明：

輸入的第一列為正整數𝑇，表示總共有多少套題目需要決定題目名稱。

接著共有𝑇列，每一列各自表示一套題目，總共有三題，也即每一列總共包含 6 個正整數，相同的數表示著相同的解題方法，反之亦然。其中每一列的第 1,2 個數所表示的解題方法與第一題有相關；第 3,4 個數所表示的解題方法與第二題有相關；第 5,6 個數所表示的解題方法與第三題有相關。

輸入滿足 𝑇 ≤ 1000，且所有表示解題方法的正整數皆不超過 100。

輸出說明：

對於每一套題目，請依序輸出一列，若對於該套題目，可以依照題意不重複的訂定每一題的題目名稱，請輸出 Yes，否則輸出 No。

範例輸入一：

1

1 2 3 4 5 6

範例輸出一：

Yes

範例說明一：

三題的題目名稱可以分別訂

為 1、4、5 符合條件且不重複。

範例輸入二：

2

1 2 1 2 1 2

2 1 2 1 2 1

範例輸出二：

No

No

範例說明二：

均不存在不重複之題目名稱訂法。

範例輸入三：

1

1 2 1 3 2 3

範例輸出三：

Yes

範例說明三：

三題的題目名稱可以分別訂

為 2、1、3 符合條件且不重複。

第四題: 瘦身遊戲

問題敘述 小圓養了一隻可愛的小黑狗，但由於一時想不到什麼特別的名字，因此就叫牠" Cute Black Dog"，簡稱CBD。CBD非常聰明，可以認得阿拉伯數字，也因此得到小圓的鍾愛。在小圓的細心照料之下，CBD日漸發福，小圓眼見這樣事情不太妙，於是設計一個遊戲讓CBD在玩的時候可以順便運動。 小圓設計的遊戲是這樣的：他先準備了N張紙卡，上面依序寫著1至N的各個正整數，並將這些紙卡在地上亂序的由左到右排成一列。接著他讓CBD先由最左邊的紙卡跑到最右邊的紙卡，再從最右邊跑回最左邊，不斷折返，並規定途中只要遇到寫著目前所剩餘的紙卡中，數值最小的那張紙卡，就要將該紙卡叼走，否則不能把該紙卡叼走。 舉例來說，假設一開始共有 5 張卡片，由左而右依序為 1,4,2,5,3 ，則CBD第一次由左端跑到右端時，延路會叼走 1,2,3 三張紙卡，折返往左跑時會叼走 4 ，又折返往右跑時再把 5 叼走。 小圓想請你幫他算一下，給定一開始的紙卡排列方式，CBD一共至少需要改變幾次方向才能把所有紙卡都叼走呢？ 輸入說明 測試資料的輸入共有兩列。 第一列為正整數N，表示紙卡的數量。(N≤1000000) 第二列包含N個正整數，以空白隔開，表示由左到右紙卡上所寫的數值，保證1至N都會恰好出現一次。 輸出說明 請輸出一列，其中包含一個整數，為CBD折返(改變方向)的次數。 範例輸入 5 1 4 2 5 3 範例輸出 2

第五題: 項鍊串珠

問題敘述 老溫買了一條環型的項鍊，項鍊中有著各式各樣的珠子，每個珠子都以英文的小寫字母所表示，相同的字母表示同種珠子，而不同的字母表示不同種珠子。老溫希望從這個項鍊中截取連續一段長度為M的珠子來用，並希望都是由同一種珠子組成。 請問共有多少種截取的方法呢？ 輸入說明 測試資料的輸入共有兩列。 第一列為正整數N,M，N表示項鍊中共有多少顆珠子，老溫希望從這個項鍊中截取連續一段長度為M的珠子，如題目所示，M<N≤200000。 第二列由英文小寫字母所組成的字串，表示從項鍊的某處開始，以逆時針順序所表示的各珠子之種類，其長度為N。 最後一個字母所表示的珠子與第一個字母所表示的珠子相連。 輸出說明 請輸出一列，其中包含一個整數，為共有多少種選法。 範例輸入 5 2 aaabb 範例輸出 3

第六題: 圓的聯集

問題敘述 老溫在坐標平面上畫了許多的圓，請問這些圓的聯集面積(也即至少被一個圓所覆蓋的面積)是多少呢？ 輸入說明 測試資料的輸入第一列為正整數N，N表示圓的個數且N不超過5。 接著共有N列，每列包含三個正整數X_i,Y_i,R_i,，表示此圓的圓心為(X_i,Y_i)，半徑為R_i。 保證這些圓的圓心、圓周都會在座標位置(0,0)到(100,100)的範圍內(含)。 計算時若需要，可使用π=3.14159265358979324。 輸出說明 請輸出一列，其中包含一個整數，為這些圓的聯集面積無條件捨去到整數位。 假設其聯集面積的精確值以小數形式可表示為A.B，其中A為整數部分，B為小數部分，則保證B的首位數為4或5。換句話說，結果誤差之絕對值在0.39以內不會影響答案。 範例輸入 2 18 22 7 17 28 8 範例輸出 267

第七題: 異數相減

問題敘述 老溫在睡夢中想到了兩個正整數A與B，接著計算出了(A-B)的結果並寫了下來。 清醒後，老溫忘了當初想到的A與B，只保留著紙上的數值(A-B)。 回想回想著，老溫想到一件神奇的性質：A與B的位數總和正好9位，且總共使用到數字1, 2, 3, 4, 5, 6, 7, 8, 9均恰好一次。 你可以幫忙老溫找出所有可能的A與B，以及其計算式嗎？ 輸入說明 輸入包含一列，為一個正整數，表示(A-B)的值X。X不低於四位數，不超過七位數。 輸出說明 請輸出所有可能的計算式，並以A-B=X的格式輸出，每個計算式輸出一列，只包含數字、「-」與「=」，不得包含空白或其他字元。 若有多組可能的計算式，請由A較小的計算式先輸出。 範例輸入 91111 範例輸出 92468-1357=91111 92486-1375=91111 92648-1537=91111 92684-1573=91111 92846-1735=91111 92864-1753=91111 94268-3157=91111 94286-3175=91111 94628-3517=91111 94682-3571=91111 94826-3715=91111 94862-3751=91111 96248-5137=91111 96284-5173=91111 96428-5317=91111 96482-5371=91111 96824-5713=91111 96842-5731=91111 98246-7135=91111 98264-7153=91111 98426-7315=91111 98462-7351=91111 98624-7513=91111 98642-7531=91111

第八題: 物品探測 問題敘述 遙遠的星空中，有個神祕的物品正悄悄的出現…… 雷達螢幕上顯示著這個物品，而系統偵測的結果為此物品外觀是個正方形，並且由於此物品正對著地球，所以此物品的投影也是個正方形。 眾所皆知的，正方形應該有四個角，然而，由於跟美帝購買的雷達功能並不齊全，只能顯示其中三個角的座標位置，而且這些角沒有固定的順序。 雖然可以從雷達中獲得其中三個角的二維座標位置，但你希望回報這個物品四個角的位置，以便於做萬全的防禦準備。請根據其中三個角的座標位置，推算出第四個角的位置。 輸入說明 輸入共有三列，表示雷達所偵測到的三個角的座標位置。 每一列均有兩個非負整數𝑥, 𝑦，表示其中一個角的座標位置為 (𝑥, 𝑦)。(𝑥, 𝑦 ≤ 100) 保證輸入中三個座標位置為座標平面上正方形的其中三個相異頂點。 輸出說明 請輸出一列，其中包含兩個整數𝑋, 𝑌，並以一個空白隔開，表示第四個角的位置，也就 是該座標平面上正方形的第四個頂點之座標位置為(𝑋, 𝑌)。 範例輸入一：       範例輸入二：           範例輸入三： 0 0                6 6                     1 0 0 1                4 4                     0 1 1 0                6 4                     2 1 範例輸出一：       範例輸出二：           範例輸出三： 1 1                4 6                     1 2

第九題: 二元一次方程式整數解

問題敘述 小涵的桌上有著堆積如山的數學作業，每題有一個方程式，她想要請你幫忙計算題目中方程式的整數解。 題目的形式都是這樣的：ax + by = m 其中 m, a, b 為題目中的已知常數，請你求出未知整數 x 與 y，使得上式成立。 輸入說明 測試資料只有一行，其中有三個正整數，依序為 m, a, b，表示題中方程式之已知常數，測試資料中 m < a < b <= 10^16 。 輸出說明 請你求出該方程式的整數解，第一行輸出 x 的值，第二行輸出 y 的值，並使得 x * y 最大。若有多組解之 x * y 值相同者，請輸出 x 的值較大者。 如果該方程式之整數解不存在，請輸出 "no" (不含引號)。 範例輸入 1 2 5 範例輸出 -2 1

第十題: 神奇的數字轉輪

問題敘述 小涵撿到了一個神奇的轉輪。這個轉輪有 n 個數字，每個數字每轉一次會依照下列的順序變化： 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 0 (接開頭) 因為那是個神奇的轉輪，你不能單獨操作一個轉輪上的數字，你必須依照一些特定的規則操作這個轉輪。 現在告訴你轉輪上原本的數，與一些操作轉輪的規則(如輸入說明所示)，希望你能透過這些規則將轉輪轉為另一個數。 輸入說明 第一行輸入一個正整數 n，表示轉輪上共有幾個數字。 第二行輸入一個正整數 m，表示共有幾種操作轉輪的規則。 接下來的 m 行，每行表示一種操作轉輪的規則。每行共有 n 個整數 R1, R2, ..., Rn ，表示依照此規則操作一次轉輪，可以將轉輪上的第1個數轉 R1 次，將轉輪上的第2個數轉 R2 次，……，將轉輪上的第n個數轉 Rn 次。 最後一行有兩個整數 st, ed，表示轉輪上原本的數是 st ，你希望透過若干次操作使得轉輪上的數成為 ed。 ( 1<= n <= 7; 1<= m <= 50, 0 <= Ri <= 2^31-1) 輸出說明 請輸出最少需要幾次操作，可以使轉輪上的數成為ed 。 測試資料中不會有無法使轉輪上的數成為 ed 的情形。 範例輸入 3 2 1 0 0 0 2 1 568 121 範例輸出 9 說明：原本的數值為568，對轉輪操作6次規則1，成為168，再操作3次規則2，轉輪上的數即為所求之121，共需9次操作。