[109-cpi] HW3 - HackMD

--- tags: homework, 109, cpi title: '[109-cpi] HW3' --- # Homework 3 > Week 4 (10/5), Due: 10/12 09:00:00\ > ps. 這次來換一下出題順序 * 範圍：Conditional * NOJ --- ## 會長的工作 > [name=映達] ### Description 學生會的會長除了是個資優生，在課業以外的地方更是一個名符其實的工作狂。會長嘗試在各式各樣的地方打工，不論是夏日祭典的炒麵攤，或是海水浴場的海之家。不過其中最特殊的，非賭場莫屬了。在賭場工作不但報酬可觀，同時還能和黑白兩道、政商名流有所接觸。賺錢的同時又能拓展人脈，是個難能可貴的經驗。在賭場工作了一段時間，會長漸漸的對「 Blackjack 」的玩法有一套心得。會長將觀察的結果畫成了表格，代表的是玩家在各種情況下應該做出的最佳策略。要請你寫一支程式來模仿查表的行為。為了方便起見，假設判斷的皆是玩家的「第三張牌」拿或不拿。換句話說，目前場上的牌有：莊家一張、玩家兩張。 ![image alt](https://imgur.com/HLVfd7W.jpg) 縱軸數字代表的是莊家的點數。橫軸數字三張圖（左至右）意義稍有不同： - 第一張圖最單純，數字代表的是兩張牌的點數總和。 - 第二張圖代表的是，一張 A 配上另一張其他點數的牌。 - 第三張圖則是當兩張牌點數相同的情況。（在 Blackjack 的規則中，J、Q、K 皆視為 **10 點**。 A 在情況允許（點數和尚未超過 21 點）時，也視作 10 點。） ### Input 依照實際發牌的順序，**玩家、莊家、玩家**，依序輸入三個整數，用空白隔開。代表撲克牌 $n$。 - $1 \le n \le 13$ ### Output 根據上表輸出最佳的操作（ `ht`, `st`, `dd`, `sp` ）。補充）表中縮寫代表的意義分別是： - ht: Hit - st: Stand - dd: Double Down - sp: Split ### Example Input ``` 10 8 7 ``` ### Example Output ``` st ``` ### Hint - de Mesentier Silva F, Isaksen A, Togelius J, Nealen A (2016) Generating heuristics for novice players. In: Proceedings of the 2016 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, pp 1–8 ### Subtask --- ## 「危機」分的惡趣味 > [name=育辰] ### Description 芮芮興高采烈考進了NU大學，所屬科系隸屬於理學院，修習了很多硬課，其中包括了「程式設計（一）」，此外，還有...許多學長姐被當掉的曾經...那些痛苦的血淚以及辛酸史——「微積分乙（一）」。\ \ 「微積分乙（一）芮芮興高采烈考進了NU大學，所屬科系隸屬於理學院，修習了很多硬課，其中包括了「程式設計（一）」，此外，還有...許多學長姐被當掉的曾經...那些痛苦的血淚以及辛酸史——「微積分乙（一）」。\ \ \ 為了實現翻轉教學，阿修架設了線上的遊戲平台，給學生作為回家作業... **(參考圖)**\ ![](https://i.imgur.com/zupwaOu.png) \ 阿修小時候玩了一款爬梯大富翁，起初時玩家輪流擲骰，若移動到「特定」格子，則可爬梯到「特定」格子，除了...有機會讓你一瞬間「獨佔鰲頭」，也可以一瞬間勝利「灰飛煙滅」...\ \ 今天阿修規定了這樣一款遊戲： 1. 起初玩家由數字 $0$ 的位置出發，並由系統隨機給定一個**正整數** $x$，接著玩家根據下列式子計算出結果 $n$，此結果即為該玩家「本次移動的步數」，當然...阿修的修課同學都是學霸，絕不會算錯！ $$n =\begin{cases} \frac{5 \times (x-2)}{x-2}, & 0 < x < 4\\ \frac{x}{2}, & x \geq 4 \text{ and } x \text{ is even.}\\ x-4, & x \geq 4 \text{ and } x \text{ is odd.}\\ \end{cases}$$ > 阿修覺得擲骰太無趣了，於是出了本次作業的範圍**分段函式**讓同學計算移動步數。 2. 阿修的爬梯大富翁，若玩家計算出 $n$ 後，並且移動完畢，此時玩家位於位置 $P$，若數值滿足**下列式子**，則該位置 $P$有設置「升天梯子」，將移動到 $(2 \times P)$ 的位置上： $$A = \frac{(P-4)(P-3)}{3}, \text{and A is positive integer}$$ 3. 「地獄梯子」則會讓玩家移動到 $\frac{P}{2}$ 的格子上 (若為小數，則無條件捨去到整數位)，此梯子坐落在**所有 $5$ 的倍數**的格子上 **注意** 1. 若該格子同時有「升天梯子」以及「地獄梯子」則玩家芮芮會陷入「兔子疑惑」，因此**不移動**。 2. 計算 $n$ 數值時的分段函式，若為 **無定義** 但其極限存在，則玩家必須輸出 "**Not defined! Limit exist!**"，阿修為了獎勵正確答題的同學，該玩家移動步數改為 $n = (3 \times x) + 1$ 3. 若僅有一種梯子，則玩家「必定」須攀爬該梯子。芮芮是阿修微積分課的修課學生，他雖然是學霸但不太會寫程式。\ \ 奇妙的是阿修可能程式太強了，沒意識到這堂課的同學未必學過程式...他架設微積分課程的線上學習平台，卻是採用 Online Judge 的繳交方式，必須上繳程式碼並得到 Accepted，才算拿到本次作業分數！\ \ 請寫出一個程式，幫幫芮芮完成作業吧！ ### Input 輸入一行，只包含一**正整數** $x$ > 該輸入，**保證**計算後： $$0 \leq P \leq 2^{31}-1$$ ### Output 若 $n$ 計算結果未定義，則先輸出 "**Not defined! Limit exist!**"，並換行，接著，無論 $n$ 起初是否定義，皆輸出一行整數 $P$，為玩家最終所在位置，並需換行。 > 未定義(即 $x=2$) 輸出指定字串後，阿修會獎勵同學將移動步數 $n$ 改為 $(3 \times x) + 1$，所以最終 $n$ 不會有未定義的情況發生。 ### Example Input \#1 2 ### Example Output \#1 Not defined! Limit exist! 14 ### Example Input \#2 4 ### Example Output \#2 2 ### Hint * 看清楚題目，尤其是 **注意** 的事項 * 善用判斷式，起初玩家是在位置 **0** 上，計算 $n$ 完移動後，**該位置**還要再判斷是否有梯子，並根據上述狀況得出最終所在位置 $P$ * 範例測資 1： * 起初 $x=2$，代入到式子得到： $$\frac{5 \times (2-2)}{2-2} = \frac{0}{0}$$得到未定義的答案，但 $\lim_{x \to 2}(\frac{5 \times (x-2)}{x-2}) = 5$，根據題幹，先輸出一行 "Not defined! Limit exist!" * 根據題目，由於未定義，因此移動步數改為 $(3 \times x) + 1 = 7$，因此玩家移動到位置 $7$ 上 * 由於 $\frac{(P-4)(P-3)}{3} = \frac{3 \times 4}{3} = 4$，4為正整數，因此我們得知位置 $7$ 上有「升天梯子」，但 $7$ 不為 $5$ 的倍數，故無「地獄梯子」，由此，玩家必須爬上「升天梯子」移動到 $7 \times 2 = 14$ 的位置上 * 再輸出最終位置 $14$ 即可 * 範例測資 2： * 起初 $x=4$，故代入得 $\frac{x}{2} = 2$ * 計算 $\frac{(2-4)(2-3)}{3}$ ，結果不為整數，因此無「升天梯子」 * $2$ 不為 $5$ 的倍數，故無「地獄梯子」 * 直接輸出最終位置 $2$ 即可 ### Subtask #### Subtask 1：40% 該任務保證移動後格子不會有「升天梯子」，也不會有「地獄梯子」，此外，也不會有"not defined”(x=2) 的狀況出現。 #### Subtask 2: 20% 移動後格子「可能」有梯子，但不會兩種梯子同時出現。 #### Subtask 3: 40% 無特殊限制 * [測資載點](https://drive.google.com/file/d/1wOeoGwKvkEIE6RSAafU4p8wQM2jduBEo/view?usp=sharing) --- ## 決勝！撿石頭 > [name=博傑] ### Description 社團活動，那是身為高中學生，要度過一個充實的高中時光的重要途徑。而社團經費，更是維持社團可以正常運作的命脈。最近，由於經濟不景氣，捐款有所減少，學生會的大家正在討論今年的社團經費應當如何刪減，就在會長與會計爭論究竟該不該因為社團內的情侶課徵「幸福稅」的時候，大小姐提出了「文化系社團的開銷通常不大，活動也較不認真，應當優先刪減」這種論點。身為文化系社團 --- 桌遊部成員的書記，自然極力反抗，提出了與大小姐決鬥的請求，要用遊戲來證明桌遊部可是都有認真在做社團活動的，這個遊戲規則如下： 1. 在桌上擺了總共 $N$ 個石頭 2. 猜拳決定開始玩家，贏家先手 3. 雙方玩家輪流從中拿走 $1 \sim M$ 顆石頭 4. 拿走最後一個石頭的玩家即獲勝然而，看似公平的規則中，其實隱藏著必勝的法則。勝負，早已在猜拳時被決定了。而身為出老千專家的書記，自然不會放過這種獲勝的機會。現在，告訴你 $N$ 跟 $M$，請你幫書記決定，他到底要猜贏還是猜輸，才能保證拿下這場遊戲的勝利吧。 ### Input 輸入僅一行兩個正整數，分別代表 $N, M$ 其中 $N > M$ 對於所有輸入，保證 $1 < N, M < 2^{31}$ ### Output 請輸出一行字串輸出 `Win` 表示書記需要猜贏才能獲得遊戲勝利輸出 `Lose` 表示她需要猜輸才能獲得遊戲勝利 ### Example Input 0 ``` 4 3 ``` ### Example Output 0 ``` Lose ``` ### Example Input 1 ``` 4 2 ``` ### Example Output 1 ``` Win ``` ### Hint 1. 對於第一筆範測，不管先手的玩家拿的是幾顆，後手一定可以把剩下的石頭拿完，所以後手必勝，因此書記必須猜輸才能贏得遊戲。 2. 第二筆範測中，先手只要拿走 1 顆石頭，後手不管拿走幾顆，最後都會是後手拿完全部的石頭，因此這個時候先手必勝。 3. 幸福稅是單身狗會計因為忌妒而提議的不合理規定，大意是社團內每有一對情侶，社費便要減少五萬元。 ### Subtask --- ## 湊題目區 * 本次命題範圍 [Judge Girl](https://judgegirl.csie.org/problems/domain/0#3) * 偏好一個簡單、一個難的，例如 power配上Square兩題 * 或同樣 Triangle vs Square （類型太相同可能會有點膩) ## Triangle ### Description 平面上座標上，給定三角形的三個頂點座標，決定是否為等腰(*isosceles*)、銳角(*acute*)、鈍角(*obtuse*)或者是直角(*right*)三角形。你可以假設所有座標皆為整數。特別注意，如果一個三角形為等腰三角形，那麼就不必回報它是否為銳角或鈍角。為了防止計算誤差，若需要紀錄三角形的三邊長，最好使用其邊長的平方儲存，假設三邊長由長到短分別為 $a, b, c$，那麼只需要比較 $a^2, b^2, c^2$ 之間的關係即可得到。 ### Input 輸入總共有一行六個整數 $x_1, y_1, x_2, y_2, x_3, y_3$，分別代表三角形三個點的座標。所有整數皆為小於 $1000$ 的非負整數。所有輸入皆保證可以形成合法的三角形。 ### Output 輸出三角形的類別於一行，可能的輸出有 - `isosceles` - `acute` - `obtuse` - `right` ### Sample Input 0 ``` 0 0 1 1 1 0 ``` ### Sample Output 0 ``` isosceles ``` ### Sample Input 1 ``` 0 0 1 3 3 0 ``` ### Sample Output 1 ``` acute ``` ### Hint 改編自 Judge Girl，[原題連結](https://judgegirl.csie.org/problem/0/80)於此 ## Origin in Quadrilateral ### Description 給一個凸四邊形 $Q$ 的四個頂點座標，請問原點 $(0, 0)$ 是否在四邊形內部，如果原點在四邊形內部，輸出 `1`，反之，請輸出 `0` ![](https://judgegirl.csie.org/images/problems/p241-1.png =x400) 範例一：原點在 $Q$ 裡面 ![](https://judgegirl.csie.org/images/problems/p241-2.png =x400) 範例二：原點不在 $Q$ 裡面 ### Input 輸入包含八個整數 $a, b, c, d, e, f, g, h$，按照逆時針順序給定座標 $(a, b), (c, d), (e, f), (g, h)$。請注意：四邊形的邊不一定平行於座標兩軸，座標的絕對值小於等於 $100$。 ### Output 輸出 `1` 或是 `0`，代表原點是否有在 $Q$ 裡面。 ### Sample Input ``` 2 1 -1 2 -2 -1 -1 -3 ``` ### Sample Output ``` 1 ``` ### Sample Input ``` 12 1 9 2 8 -1 9 -3 ``` ### Sample Output ``` 0 ``` ### Hint 題目搬運自 Judge Girl，[原題連結](https://judgegirl.csie.org/problem/0/241)在此 #### Hint 1 > In computational geometry of the plane, the cross product is used to determine the sign of the acute angle defined by three points $p_1 = (x_1, y_1)$, $p_2 = (x_2, y_2)$ and $p_3 = (x_3, y_3)$. It corresponds to the direction of the cross product of the two coplanar vectors defined by the pairs of points $p_1$, $p_2$ and $p_1$, $p_3$, i.e., by the sign of the expression $P = (x_2 − x_1)(y_3 − y_1) − (y_2 − y_1)(x_3 − x_1)$... > [Cross product Computational geometry - wiki](https://en.wikipedia.org/wiki/Cross_product#Computational_geometry) 以第一筆範例測資為例，我們可以得到四個向量 $\vec{a} = (2, 1), \vec{b} = (−1, 2), \vec{c} = (−2, −1), \vec{d} = (−1, −3).$ 原點會落在 $Q$ 若且唯若滿足下列條件 - $\vec{a} \times \vec{b} = 2 \cdot 2 − 1 \cdot (−1) = 5 > 0,$ - $\vec{b} \times \vec{c} = (-1) \cdot (-1) - 2 \cdot (-2) = 5 > 0,$ - $\vec{c} \times \vec{d} = (-2) \cdot (-3) - (-1) \cdot (-1) = 3 > 0, \text{and }$ - $\vec{d} \times \vec{a} = (-1) \cdot (1) - (-3) \cdot (2) = 5 > 0$ #### Hint 2 [Ray casting algorithm O(n) - Wiki](https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm) / [Convex Polygon O(logn)](http://erich.realtimerendering.com/ptinpoly/) #### Hint 3 計算面積總和 (Note: 注意 overflow) --- ## Mixed Fractions (超出範圍，之後再說)