2020年2月17日 星期一

軟體設計實務精選進階題


第一題山洞探險 


問題敘述
為了尋找傳說中名為「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_1M_1分。
第二列共有兩個整數 H_2,M_2,表示校長站在校門口的結束時間為H_2M_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
範例說明一:
三題的題目名稱可以分別訂
145 符合條件且不重複。


範例輸入二:
2
1 2 1 2 1 2
2 1 2 1 2 1
範例輸出二:
No
No
範例說明二:
均不存在不重複之題目名稱訂法。
範例輸入三:
1
1 2 1 3 2 3
範例輸出三:
Yes
範例說明三:
三題的題目名稱可以分別訂
213 符合條件且不重複。



第四題瘦身遊戲


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


輸入說明
測試資料的輸入共有兩列。
第一列為正整數N,表示紙卡的數量。(N≤1000000)
第二列包含N個正整數,以空白隔開,表示由左到右紙卡上所寫的數值,保證1N都會恰好出現一次。


輸出說明
請輸出一列,其中包含一個整數,為CBD折返(改變方向)的次數。

範例輸入
5
1 4 2 5 3


範例輸出
2


第五題項鍊串珠


問題敘述
老溫買了一條環型的項鍊,項鍊中有著各式各樣的珠子,每個珠子都以英文的小寫字母所表示,相同的字母表示同種珠子,而不同的字母表示不同種珠子。老溫希望從這個項鍊中截取連續一段長度為M的珠子來用,並希望都是由同一種珠子組成。
請問共有多少種截取的方法呢?

輸入說明
測試資料的輸入共有兩列。
第一列為正整數N,MN表示項鍊中共有多少顆珠子,老溫希望從這個項鍊中截取連續一段長度為M的珠子,如題目所示,M<N≤200000
第二列由英文小寫字母所組成的字串,表示從項鍊的某處開始,以逆時針順序所表示的各珠子之種類,其長度為N
最後一個字母所表示的珠子與第一個字母所表示的珠子相連。

輸出說明
請輸出一列,其中包含一個整數,為共有多少種選法。

範例輸入
5 2
aaabb


範例輸出
3



第六題圓的聯集


問題敘述
老溫在坐標平面上畫了許多的圓,請問這些圓的聯集面積(也即至少被一個圓所覆蓋的面積)是多少呢?

輸入說明
測試資料的輸入第一列為正整數NN表示圓的個數且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的首位數為45。換句話說,結果誤差之絕對值在0.39以內不會影響答案。


範例輸入
2
18 22 7
17 28 8


範例輸出
267



第七題異數相減



問題敘述
老溫在睡夢中想到了兩個正整數AB,接著計算出了(A-B)的結果並寫了下來。
清醒後,老溫忘了當初想到的AB,只保留著紙上的數值(A-B)
回想回想著,老溫想到一件神奇的性質:AB的位數總和正好9位,且總共使用到數字1, 2, 3, 4, 5, 6, 7, 8, 9均恰好一次。
你可以幫忙老溫找出所有可能的AB,以及其計算式嗎?

輸入說明
輸入包含一列,為一個正整數,表示(A-B)的值XX不低於四位數,不超過七位數。
輸出說明
請輸出所有可能的計算式,並以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次操作。


沒有留言:

張貼留言

注意:只有此網誌的成員可以留言。