2025 NCKU CSIE Program Design II - Midterm

# 2025 NCKU CSIE Program Design II - Midterm ## Scoring | 答對 1 題 | 答對 2 題 | 答對 3 題 | 答對 4 題 | 答對 5 題 | 答對 6 題 | | ---- | ---- | ---- | --- | --- | --- | | 20 分 | 40 分 | 60 分 | 80 分 | 90 分 | 100 分 | ## Problem ### Problem A - 東邊日出西邊雨 (30%) #### Problem Statement 「東邊日出西邊雨，南極企鵝北極熊」告訴我們東邊日出時南極有企鵝，西邊下雨時北極也有北極熊。南極的企鵝某一天想要前往北極見到他的好麻吉北極熊，但是北極實在是太遠了，企鵝可能需要花好幾天才能走到。為此，企鵝決定要花一點時間規劃行程。已知南極到北極的距離總共為 $n$ 公里，接下來企鵝共規劃了 $m$ 天的行程，每天企鵝會走 $a_i$ 公里，現在我們想要知道企鵝如果會抵達目的地的話，他總共會需要花幾天才能到達北極。請你設計一個程式來計算！（如果到達不了則輸出 `-1`） #### Input Format ``` n m a_1 a_2 a_3 ... a_m ``` #### Output Format ``` days ``` #### Input Limit 輸入限制是指我們測試你的程式時會保證的一個輸入範圍，你的程式不需要對此做額外判斷。 - $1 \le n \le 10^6$ - $1 \le m \le 1000$ - $1 \le a_i \le 10^6$ #### Sample Input 1 ``` 5 2 1 2 ``` #### Sample Output 1 ``` -1 ``` #### Sample Input 2 ``` 10 5 1 2 3 4 5 ``` #### Sample Output 2 ``` 4 ``` #### Sample Input 3 ``` 100 3 1000 1000 1000 ``` #### Sample Output 3 ``` 1 ``` --- ### Problem B. 資訊系大車隊成大資訊系有著非常著名的腳踏車隊，這一個車隊以在腳踏車上放置不同顏色的小喇叭聞名，這一個小喇叭非常雖然看起來很小，但卻有著非常驚人的音量，第一次按的人都會大吃一驚。 ![image-2-2-2](https://hackmd.io/_uploads/rkgrAYq0yg.png) 某天車隊想要在光復校區練車，不過光復校區的雲平大道旁邊是管理學院的教學場地，因此在他們練車時是無法任意的亂按喇叭的，不過這樣讓車隊的隊長非常困擾，既然都來了就應該開心練車啊，還要被有所限制實在很小氣。為了解決這個問題隊長搜集了管理學院接下來 $n$ 天的教學資訊，以方便他們排定練車計畫。已知接下來 $n$ 天每天都有 $a_i$ 堂課在管理學院進行，且當天超過 $m$ 堂課就不適合練習。為了保有練習的效率，隊長希望能夠選出「剛好」連續 $k$ 天來練習，請你設計一個程式計算共有幾種選擇。 #### Input Foramt ``` n m k a_1 a_2 ... a_n ``` #### Input Limit - $1 \le k \le n \le 1000$ - $1 \le a_i, m \le 10^9$ #### Outut Format ``` ans ``` #### Sample Input 1 ``` 5 3 2 10 2 3 1 4 ``` #### Sample Output 1 ``` 2 ``` #### Description Sample 1 可以選擇第二天與第三天練習或第三天與第四天練習，因此共 2 種可能。 #### Sample Input 2 ``` 5 5 3 1 2 3 4 5 ``` #### Sample Output 2 ``` 3 ``` #### Description Sample 2 可以選擇第 1-3 天、第 2-4 天或第 3-5 天練習，因此共 3 種可能。 #### Sample Input 3 ``` 5 2 2 3 3 3 3 3 ``` #### Sample Output 3 ``` 0 ``` #### Description Sample 3 沒有任何連續 2 天適合練習，因此答案為 0。 #### Sample Input 4 ``` 5 4 1 1 2 3 4 5 ``` #### Sample Output 4 ``` 4 ``` #### Description Sample 4 只有第 5 天不適合練習，因此有 4 天可以選擇。 #### Sample Input 5 ``` 5 3 5 1 2 3 4 5 ``` #### Sample Output 5 ``` 0 ``` #### Description Sample 5 沒有任何連續 5 天都適合練習，因此答案為 0。 #### Sample Input 6 ``` 5 3 2 3 3 3 3 3 ``` #### Sample Output 6 ``` 4 ``` #### Description Sample 6 每天都有剛好 3 堂課，所以每天都適合練習。可以選擇第 1-2 天、第 2-3 天、第 3-4 天或第 4-5 天練習，因此共 4 種可能。 --- ### Problem C. 回文一個字串如果正著讀和反著讀都一樣，就稱為回文。請設計一個程式來判斷給定的字串是否為回文。 #### 輸入格式 ``` s ``` #### 輸入限制 - 字串長度保證不超過 500。 #### 輸出格式 ``` YES 或 NO ``` #### 範例輸入 1 ``` apple ``` #### 範例輸出 1 ``` NO ``` #### 範例說明 1 字串 "apple" 不是回文，因為正著讀和反著讀不一樣。 #### 範例輸入 2 ``` abba ``` #### 範例輸出 2 ``` YES ``` #### 範例說明 2 字串 "abba" 是回文，因為正著讀和反著讀都一樣。 #### 範例輸入 3 ``` racecar ``` #### 範例輸出 3 ``` YES ``` #### 範例說明 3 字串 "racecar" 是回文，因為正著讀和反著讀都一樣。 #### 範例輸入 4 ``` hello ``` #### 範例輸出 4 ``` NO ``` #### 範例說明 4 字串 "hello" 不是回文，因為正著讀和反著讀不一樣。 #### 範例輸入 5 ``` a ``` #### 範例輸出 5 ``` YES ``` #### 範例說明 5 單一字元必定是回文。 #### 範例輸入 6 ``` madam ``` #### 範例輸出 6 ``` YES ``` #### 範例說明 6 字串 "madam" 是回文，因為正著讀和反著讀都一樣。 --- ### Problem D. 霍格華茲的骰子課 #### 題目描述霍格華滋的麥教授決定開一門名為「魔法骰子」的課程，這一門課程會教授許多骰子的奧秘。已知骰子有一個長度為 $n$ 的序列 $a$，這一個序列中的每一個數字 $a_i$ 表示骰子可能的點數。某位學生使用咒語「速速前」(Accio) 來擲骰子，骰子總共有 $3$ 顆，請問這位學生骰出來的點數總共有幾種可能？ #### 輸入格式 ``` n a_1 a_2 ... a_n ``` #### 輸入限制 - $1 \le n \le 500$ - $1 \le a_i \le 1000$ #### 輸出格式 ``` ans ``` #### 範例輸入 1 ``` 3 1 2 3 ``` #### 範例輸出 1 ``` 7 ``` #### 範例輸入 2 ``` 2 1 2 ``` #### 範例輸出 2 ``` 4 ``` #### 範例說明 2 可能的點數組合為： 1+1+1=3 1+1+2=4 1+2+2=5 2+2+2=6 總共有 4 種不同的點數。 #### 範例輸入 3 ``` 4 1 2 3 4 ``` #### 範例輸出 3 ``` 10 ``` #### 範例說明 3 可能的點數組合為： 1+1+1=3 1+1+2=4 1+1+3=5 1+1+4=6 1+2+2=5 1+2+3=6 1+2+4=7 1+3+3=7 1+3+4=8 1+4+4=9 2+2+2=6 2+2+3=7 2+2+4=8 2+3+3=8 2+3+4=9 2+4+4=10 3+3+3=9 3+3+4=10 3+4+4=11 4+4+4=12 總共有 10 種不同的點數。 #### 範例輸入 4 ``` 3 10 20 30 ``` #### 範例輸出 4 ``` 7 ``` --- ### Problem E. 舞蹈練習 Colten 平時非常喜歡看韓團，如果有機會的話你可能會收到他在 IG 傳給你的韓國女團跳舞短影片。具有經驗的人描述，Colten 平時看的是「IVE」、「ILLIT」與「BABYMONSTER」三團，基本上已經看到他自己也非常會跳的程度，但有點可惜的是他自己並不能成為女團的一員。 Colten 某一天沒課想要來好好練舞，他挑了「REBEL HEART」、「Cherish」與「DRIP」來練習，已知這三首歌的難度分別為 $a,b,c$，現在可以任意的排定練舞的順序，如果第一首到第三首的難度依序是 $x,y,z$，那麼 Colten 會需要消耗 $(x + y) | (y - z) | (x \times z - y \times z)$ 的體力，其中 $|$ 是位元 OR 運算，請你設計一個程式幫 Colten 制定練舞的順序使他消耗的體力能越少越好。如果有多種解，請優先練「REBEL HEART」，再者優先練「Cherish」。 #### 輸入格式 ``` a b c ``` #### 輸入限制 - $-1000 \le a,b,c \le 1000$ #### 輸出格式 ``` song1 song2 song3 ``` #### 範例說明 #### 範例 1 輸入： ``` 1 2 3 ``` 輸出： ``` REBEL HEART DRIP Cherish ``` 說明： - 如果選擇順序 REBEL HEART, Cherish, DRIP： $(1 + 2) | (2 - 3) | (1 \times 3 - 2 \times 3) = 3 | -1 | -3 = -1$ - 如果選擇順序 REBEL HEART, DRIP, Cherish： $(1 + 3) | (3 - 2) | (1 \times 2 - 3 \times 2) = 4 | 1 | -4 = -3$ - 其他順序的消耗都未小於 -1 - 因此選擇消耗最小的順序 REBEL HEART, DRIP, Cherish #### 範例 2 輸入： ``` 100 200 300 ``` 輸出： ``` REBEL HEART DRIP Cherish ``` #### 範例 3 輸入： ``` 5 6 7 ``` 輸出： ``` REBEL HEART DRIP Cherish ``` 說明： - 如果選擇順序 REBEL HEART, DRIP, Cherish： $(5 + 7) | (7 - 6) | (5 \times 6 - 7 \times 6) = 12 | 1 | -12 = -3$ - 如果選擇順序 REBEL HEART, Cherish, DRIP： $(5 + 6) | (6 - 7) | (5 \times 7 - 6 \times 7) = 11 | -1 | -7 = -1$ - 其他順序的消耗都大於 -3 - 因此選擇消耗最小的順序 REBEL HEART, DRIP, Cherish #### 範例 4 輸入： ``` -1 0 1 ``` 輸出： ``` REBEL HEART Cherish DRIP ``` 說明： - 如果選擇順序 REBEL HEART, Cherish, DRIP： $(-1 + 0) | (0 - 1) | (-1 \times 1 - 0 \times 1) = -1 | -1 | -1 = -1$ - 如果選擇順序 REBEL HEART, DRIP, Cherish： $(-1 + 1) | (1 - 0) | (-1 \times 0 - 1 \times 0) = 0 | 1 | 0 = 1$ - 其他順序的消耗都未小於 -1 - 因此選擇消耗最小的順序 REBEL HEART, Cherish, DRIP #### 範例 5 輸入： ``` 1000 1000 1000 ``` 輸出： ``` REBEL HEART Cherish DRIP ``` 說明： - 因為所有數字都相同，任何順序的消耗都相同： $(1000 + 1000) | (1000 - 1000) | (1000 \times 1000 - 1000 \times 1000) = 2000 | 0 | 0 = 2000$ - 根據題目要求，優先選擇 REBEL HEART，所以選擇順序 REBEL HEART, Cherish, DRIP --- ### Problem F. 簡單的問題 #### 題目描述通常簡單的題目背後也有一些小巧思，這題就是如此。輸入一組式子，請設計一個程式將該式子的結果計算出來。備註：式子只會是兩個數字相加、相減或相乘。 #### 輸入格式 ``` a+b or a-b or a*b ``` #### 輸入限制保證這兩個數字都是正整數且不會超過 $1000$。 #### 輸出格式 ``` ans ``` #### 範例輸入 1 ``` 10+20 ``` #### 範例輸出 1 ``` 30 ``` #### 範例輸入 2 ``` 10-20 ``` #### 範例輸出 2 ``` -10 ``` #### 範例輸入 3 ``` 10*20 ``` #### 範例輸出 3 ``` 200 ``` --- ### Problem G. 得分遊戲 (不計分) :::warning 本題提供給已經全部寫完但想要再玩一下的同學 ::: 現在有一個大小為 $3 \times m$ 的場地，左上角為 $(1,1)$ 右下角為 $(3, m)$。Colten 一開始位於 $(1,1)$ 的位置，已知每一個座標上都有一個數字 $a_{(x,y)}$，如果經過座標 $(x,y)$ 就可以得到該數字的分數。已知遊戲規則是只能往右走或往下走且最終目標是要抵達 $(3,m)$。請你設計一個程式計算在最佳策略下 Colten 可以獲得幾分 #### 輸入格式 ``` m a_(1,1) ... a_(1,3) a_(2,1) ... a_(2,3) a_(3,1) ... a_(3,3) ``` #### 輸入限制 - $1 \le m \le 5000$ - $1 \le a_{(x,y)} \le 10^9$ - $a_{(1,1)} = a_{(3,m)} = 0$ #### 輸出格式 ``` ans ``` #### 範例輸入 1 ``` 4 0 1 1 1 1 1 1 1 1 1 1 0 ``` #### 範例輸出 1 ``` 4 ``` #### 範例輸入 2 ``` 4 0 10 7 1 7 90 1 1000 3 55 100 0 ``` #### 範例輸出 2 ``` 1101 ``` ![image](https://hackmd.io/_uploads/Sk7GksjAkl.png)