[109-cpi] HW2 - HackMD

--- tags: homework, 109, cpi title: '[109-cpi] HW2' --- # Homework 2 > Week 3 (9/28), Due: 10/5 09:00:00 * 範圍：Operation * NOJ ## 大小姐的生日禮物 > [name=博傑] ### 敘述最近又快到了大小姐的生日了，學生會的其他三人決定要一起集資，派出與大小姐相識已久的書記去買禮物替大小姐慶祝，不過就在禮物買回來後，禮物的價格卻與本來的預算差了 $n$ 元，所以需要退錢或是再跟大家收錢。不過要計算這麼複雜的數學對於 IQ 只有 3 的書記來說實在是太困難了，請你寫個程式來幫書記計算，每個人需要再付或是可以拿回多少錢，以及最後剩下的金額。 ### 測資說明 #### Input 輸入僅一個整數 $n$，代表的是與本來預算的差距金額。其中 $-100 \le n \le 100$ #### Output 請輸出兩個數字 $q, r$ 於一行，並以一個空白隔開 $q$ 表示大家需要付出或是可以拿回多少錢 $r$ 表示最後會多出多少錢 ### Example Input 0 ``` 7 ``` ### Example Output 0 ``` 2 1 ``` ### Example Input 1 ``` -5 ``` ### Example Output 1 ``` -2 1 ``` ### Hint - 以第一筆範例測資 $n=7$ 來說，因為剩下了七塊錢，每人可以拿回兩元，最後會剩下一元充公，因此要輸出 `2 1`。 - 第二筆範例測資 $n=-5$ 代表不夠五塊錢，所以每人要再付兩元，並且最後會多出一元充公，因此要輸出 `-2 1`。 --- ## 桌遊部的各位 > [name=映達] ### Description 槙前辈、書記、Giga 子三人皆是桌遊部的成員，平時最喜歡玩各式各樣的桌遊，甚至將整個校園當做遊戲的地圖。今天，不，不只今天，每當她們玩桌遊前，經常需要先煩惱一件事：誰可以先手？該桌遊部自古流傳著一句話：「千花的千，是老千的千」。猜拳，雖然只能算是桌遊開始前的準備，可以決定玩家的先後順序。但其本質仍然是一種遊戲；既然是遊戲，當然會有人為了勝負不擇手段、甚至作弊！為了公平起見，請你寫一支程式，來幫助桌遊部的各位判定猜拳的勝負吧！ ### Input 有三個整數，$x_0$、$x_1$、$x_2$ 依序代表槙前辈、書記、Giga 子的選擇。數字對應的意義為： 0. 剪刀 1. 石頭 2. 布 ### Output 若結果出現**唯一**一位贏家，則輸出該玩家編號： 0. 槙前辈 1. 書記 2. Giga 子否則輸出 $-1$。（這是當然的，因為我們要選出先手的那**一位**玩家。若有兩位贏家出現，相當於尚未得到結果。） ### Example Input 0 ``` 0 2 2 ``` ### Example Output 0 ``` 0 ``` ### Example Input 1 ``` 0 0 2 ``` ### Example Output 1 ``` -1 ``` ### Hint 1. 善用餘數找規律 2. 拿出紙筆算算看對於所有輸入，$x_0, x_1, x_2 \in \{0, 1, 2\}$。 #### Subtask 1: 95% 輸入保證出現恰好一位贏家。 #### Subtask 2: 5% 無其他限制。 > 一些優秀的同學大概會想到可以用 if 來解。但在老師還沒教到條件選擇的情況下，這題有辦法解嗎？答案是肯定的。事實上對於 95% 的測資（必定恰好一位贏家的情況），用 if 寫未必比較簡單： > ```c > #include <stdio.h> > > int main() { > int x = 0, y = 0, z = 0; > scanf("%d %d %d", &x, &y, &z); > > // 如果不知道取模運算（%），一樣可以用國小教的方法算出餘數 > int d = y - z + 3; > int winner = d - 3*(d / 3); > // 上面兩行相當於 > // int winner = (y - z + 3) % 3; > > printf("%d\n", winner); > } > ``` > 處理答案有 $-1$ 的情況（5%）： > ```c > #include <stdio.h> > > int main() { > int x = 0, y = 0, z = 0, d = 0; > scanf("%d %d %d", &x, &y, &z); > > // int a = (x - y + 3) % 3; > d = x - y + 3; > int a = d - 3*(d / 3); > > // int b = (y - z + 3) % 3; > d = y - z + 3; > int b = d - 3*(d / 3); > > // int c = (a - b + 3) % 3; > d = a - b + 3; > int c = d - 3*(d / 3); > > // Magic > int winner = b - (b + 1)*(c - 1)*(c - 1); > printf("%d\n", winner); > } > ``` > 我預設第一子題組應該不難想，因為要縮小「會 if」和「不會 if」的人間分數的差距，所以第二子題組只給了 5 分。 --- ## 謎底揭曉 > [name=育辰] ### Description $\text{Willy}$ 沈迷一款解謎遊戲，他進入到一個雪地，並用鏟子挖掘後發現一個神秘的盒子，打開後只寫著一個整數 $n$。回到主畫面，意外發現紅色門的門把上刻了數字 $S_1$，以及天花板與牆角的縫隙也寫了一數字 $S_2$。到了一個隱密的場景，有個沖天炮被一數字鎖鎖著，其共有 $8$ 位數，在上頭放置有 $h_1$ 小時、 $m_1$ 分鐘、$s_1$ 秒數的時鐘，下頭亦放置類似的時鐘，時間未必相同，其時、分、秒依序為 $h_2, \, m_2, \, s_2$。因為怎麼解都解不開，於是偷偷去 $\text{Youtube}$ 看了攻略... ![](https://i.imgur.com/jRfHKu1.jpg) **攻略大秘籍** 1. $n$ 表示最大可接受的數值，若今後得到一數值 $n+1$，則從 $0$ 開始繼續計算，若數值小於 $0$ 則從 $n$ 往下倒數： > 例如： $n = 1000$ > * $1001$ 則結果為 $0$ > * $5342$ 則結果為 $337$ > * $-200$ 則結果為 $801$ 2. 計算 $S_1 - S_2$，並以攻略第一步中的 $n$ 去計算結果 $A_1$ 3. 接著計算由上方的開始時間，到下方的結束間所經過的**秒數**，並以單位**秒**表示，結束時間不會早於開始時間，且不會到隔天。 4. 將第三步驟所得之結果加上 $A_1$，其數值再以攻略第一步之方式計算最後結果，最終數值即為密碼鎖之答案，若有空格處則補 $0$ 請你按照攻略寫出一個程式幫助 $\text{Willy}$ 破關吧！！ ### Input $\text{Line 1: }$ 一整數 $n$\ $\text{Line 2: }$ 兩個整數 $S_1, \, S_2$，以空格間隔\ $\text{Line 3: }$ 三個整數 $h_1, \, m_1, \, s_1$，以空格間隔\ $\text{Line 4: }$ 三個整數 $h_2, \, m_2, \, s_2$，以空格間隔 **limit** * $1 \leq n \leq 2 \times 10^{5}, \, n \in \mathbb{N}$ * $0 \leq S_1, S_2 \leq 2^{30}, \ S_1, S_2 \in \mathbb{N}$ * $0 \leq h_1 \leq h_2 < 24, \ h_1, h_2 \in \mathbb{N}$ * $0 \leq m_1, m_2 < 60, \ m_1, m_2 \in \mathbb{N}$ * $0 \leq s_1, s_2 < 60, \ s_1, s_2 \in \mathbb{N}$ * $| \, \text{經過的時間} + (S_1 - S_2) \, | \leq (1000 \times n + 1000)$ ### Output $\text{Line 1: }$ 一整數 $A$，即密碼鎖密碼，需換行，且共八位數，不足需補零 ### Example Input 1000 2800 4200 4 5 30 23 59 59 ### Example Output 00000199 ### Hint * 善用`+` `-` `x` `/` `%`運算 * **經過的秒數**是求 **開始時間到結束時間，中間共經過幾秒**，而非最短時間差，此外第二個時間不會到隔天 (滿足 $h_1 \leq h_2 < 24$) ### Subtask #### Subtask 1: 25% $0 \leq \text{經過的秒數} \ + \ (S_1 - S_2) \leq n$ #### Subtask 2: 35% $0 \leq \text{經過的秒數} \ + \ (S_1 - S_2)$ #### Subtask 3: 40% 無其他限制 * [測資載點](https://drive.google.com/open?id=1GvLH1YFqDKnh3yT9Lf8lNjM0kdo-5rFi&authuser=40771131h%40gapps.ntnu.edu.tw&usp=drive_fs) --- ## Chicken, Rabbit, and Crab in a Cage > [name=Judge Girl] ### Description 有雞、兔子和螃蟹在同一個籠子裡，先不論其是否會打架，是否會履行其生態鏈的角色，我們先假設他們暫時忘卻本能，直到你的程式運行完畢，輸出正確結果後，不用再管他們的生或死... 承上，現給定這些動物的總數($s$)、動物腳的總數($f$)以及動物尾巴的總數($t$)，請依序輸出雞、兔子、螃蟹的數量。 * **給定的數字保證有解** ### Input * $\text{Line} \, 1$: 三個整數以空格分隔，依序為 $s, \, f, \, t$ #### Limit * $0 \leq s, \, f, \, t \leq 2^{31} -1$ ### Output * $\text{Line} \, 1$: 一整數 $A_{1}$ 表示**雞**的數量 * $\text{Line} \, 2$: 一整數 $A_{2}$ 表示**兔子**的數量 * $\text{Line} \, 3$: 一整數 $A_{3}$ 表示**螃蟹**的數量 ### Example Input 9 48 5 ### Example Output 2 3 4 ### Hint * 在本題中，雞預設為2隻腳, 1尾巴，兔子為4隻腳, 1尾巴，螃蟹為8隻腳（不算螯足) > from `Judge Girl` * [測資載點(已包好)](https://drive.google.com/file/d/1GnYuxfIKV0lZCX3z13RQRUsr2VdM9U9W/view?usp=sharing) --- ## Surface Area and Volume of a Box > [name=Judge Girl] ### Description 請寫出一個程式，給定 $a, \, b, \, c, \, d, \, e$，並參考下圖輸出其表面積和體積。 ![](https://i.imgur.com/QBY8sPY.png) ### Input * $\text{Line} \, 1 \text{~} 5$: 分別為 $a, \, b, \, c, \, d, \, e$，皆為整數 ### Output * $\text{Line} \, 1$: 表面積 $P, \ P \in \mathbb{P}$ * $\text{Line} \, 2$: 體積 $V, \ V \in \mathbb{N}$ ### Example Input 6 8 10 1 2 ### Example Output 472 392 ### Hint * 中間為**實心**，六面向**內凹** > from `Judge Girl` * [測資載點(已包好)](https://drive.google.com/file/d/1GmUpzBg4xFMHUfTAw9YxZ_E7wAqpRYtU/view?usp=sharing) --- ## Divide & Conquer > [name=(前) Algo 助教 - Uier] Divide 是四則運算中的其中一種隨便啦題敘你們自己想題名我覺得蠻棒的可以留著 Input: 兩個整數，代表被除數和除數 Output: 輸出兩行第一行：做除法的結果，四捨五入到小數點第二位，或預設的顯示，隨便第二行：做除法的結果，但是格式是 `Q ... R`，其中 Q 是商數 R 是餘數範例測資可以有一個負數的讓他們知道 C 餘數的特性 > 感謝！博傑已出在題目內了~ > [name=mathlin]