---
# System prepended metadata

title: '[109-cpi] HW3'
tags: [' 109', ' cpi', homework]

---

---
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 (超出範圍，之後再說)
<!--
### Description

請寫一個程式來計算兩個帶分數的加減乘除，題目會給定兩個帶分數 --- $a \frac{b}{c}$ 和 $e \frac{f}{g}$。舉個例子，當 $a=1, b=3, c=4$ 時，你會得到 $1.75$。你也可以透過一個負的 $a$ 來表示負數，所以當 $a=-1, b=3, c=4$ 時，結果會變成 $-1.75$。

為了簡化問題，我們可以假設
- $a$ 和 $e$ 永遠為非零值
- $b$ 和 $f$ 永遠為非負值
- $c$ 和 $g$ 永遠為是正數

另外，$b$ 和 $c$ 是必須被約分的。舉個例子，你不能有 $a=1, b=6, c=8$ 這種情況。另外當 $b$ 或 $f$ 為零時，$c$ 和 $g$ 一定要是 $1$。

我們會拿一個額外的數字 $d$ 當作運算子，$0, 1, 2, 3$ 分別對應到加減乘除。

現在，給你 $a, b, c, d, e, f, g$，計算最後的結果 $h \frac{i}{j}$。

### Input

輸入僅一行七個整數，以空格隔開，分別代表 $a, b, c, d, e, f, g$

#### Limits

- $-100 \le a, e \le 100$
- $a, e \ne 0$
- $0 \le b, f \le 100$
- $0 < c, g \le 100$
- $0 \le d \le 3$

### Output

輸出規則與輸入一樣，你需要將 $h, i, j$ 分別輸出於三行

### Sample Input

```
1
3
4
0
-2
3
4
```

### Sample Output

```
-1
0
1
```

### Sample Input 

```
2
0
1
2
-1
1
3
```

### Sample Output

```
-2
2
3
```

### Hint

改編自 Judge Girl，[原題連結](https://judgegirl.csie.org/problem/0/202)於此

-->
