>
# 113-2 NCKU Program Design-II Final

## 注意事項

- 每一題拿到 `Correct` 才算得到分數。
- `pA` ~ `pC` 這三題請依照題目要求上傳對應檔案，檔案名稱分別為 `pA.cpp`、`pB.cpp`、`pC.cpp` ，其餘題目皆為 `main.cpp`，請確保檔案名稱一致。
- 前三題每一題分別一定要 `#include "pA.hpp"`、`#include "pB.hpp"`、`#include pC.hpp` 否則該題不計分。

## Problm A. 疾疾！護法現身 (pA.cpp, 5%)


護法咒源自於哈利波特魔法世界，這是是唯一能夠擊退催狂魔的咒語，施展時，必須在腦海中回想自己生命中最美好或最重要的人事物。護法咒每個人使用出來不一定會有實體，實體通常會是據該人代表性的動物，能出現實體動物的都通常都具有一定的魔法天賦。

就在今天，黑魔法防禦課教授想要教大家學習如何使用護法咒，並抓了一些催狂魔提供給大家練習，這一堂課會進行分組，每一組 $2 \sim 3$ 個人。如果 $2$ 個人一組會派出 $2$ 隻催狂魔，$3$ 個人則為 $3$ 隻。

為了方便課程進行，教授想要寫一個程式讓學生們自己輸入名字，並讓這個程式自動偵測有幾個人並輸出對應的催狂魔數量，請你將這個程式設計出來吧！

### main.cpp (不可動)

#include <iostream>
#include "pA.hpp"
using namespace std;
int main() {
    ExpectoPatronum solve;
    cout << solve.get_num() << "\n";
}

### pA.hpp (不可動)

class ExpectoPatronum {
    int num;
    public:
        ExpectoPatronum();
        int get_num() const { return this -> num; }
};

### pA.cpp

你的任務是在 Constructor 完成輸入並將 `num` 的值設定正確，以確保功能正常。

#include "pA.hpp"
#include <iostream>
using namespace std;
ExpectoPatronum::ExpectoPatronum() {
    // write code here
}

### Compile Commands

g++ -o pA pA.cpp main.cpp

### Input Limits

- 保證輸入人數只會有 $2\sim3$ 人
- 人名可能會有空格字元。
- 姓名長度不超過 $30$。

### Example

#### Input 1

Colten Chen
Apple

#### Output 1

2

#### Input 2

Colten
Berry
Apple

#### Output 2

3

## Problem B. 活動管理 (pB.cpp, 10%)

成大資工系想要在五六亭辦理一個音樂會活動，這個活動吸引了上萬人的參與，為了方便管理活動與維護系館的安全，系辦提出了一項安全措施：

- 每一位參與者都必須登入 `id` 與 `name`。
- 如果該為使用者的 `name` 用 ASCII code 加總後比 `id` 小，那麼他就是管理者。

系辦想要設計一份程式依序輸出每一位參與者是否為管理者 (admin)，如果該該人是管理者則輸出 `1`，反之則輸出 `0`，你能把剩下的 Function 完成，使其正常運作嗎嗎？

### main.cpp (不可動)

#include <iostream>
#include <vector>
#include "pB.hpp"
using namespace std;

int main() {
    int q;
    cin >> q;
    vector<GroupB> groups;
    while(q--) {
        int id;
        string name;
        cin >> id >> name;
        GroupB new_people(id, name);
        groups.push_back(new_people);
    }    

    for(int i=0;i<groups.size();i++) {
        if( groups[i].admin_check() == true) cout << 1 << "\n";
        else cout << 0 << "\n";
    }

    return 0;
}

### pB.hpp (不可動)

#include <iostream>
class GroupA {
    int id;
    std::string name;
    public:
        GroupA(int id, std::string name);
};
class GroupB : public GroupA {
    bool is_admin;
    public:
        GroupB(int id, std::string name);
        bool admin_check();
};

### pB.cpp

請你創建並完成 `pB.cpp`，使整份程式能夠正常運作。

### Compile Command

g++ -o pB pB.cpp main.cpp

### Input Limits

- $1 \le q \le 10$
- $1 \le id \le 10^9$
- 保證所有人的名字都是由英文字母組成。 (大小寫都有可能)
- 姓名長度不超過 $10$。

### Example

#### Input 1

2
1000 aa
10 a

#### Output 1

1
0

- $97 + 97 < 1000$

## Problem C. 小北家灶咖 (pC.cpp, 20%)

小北家灶咖是 Colten 的愛店之一，今天我們來做一個簡單的訂位系統。

這個訂位系統需要滿足以下要求：

- 一開始輸入一個正整數 $n$ 表示共有 $n$ 筆訂位。
- 每一筆訂位依序輸入訂位人姓名、訂位人數、時間、類型 (可不填，沒填預設為一般訂位)
- 最後輸出當前所有訂單的詳細資訊 (由上到下必須由時間早到晚輸出。)
- 如果為一般訂位，訂位類型輸出 "Standard"

訂位資訊格式範例如下 (輸出也是這一個格式)：

name count time type

**Sample:**

Alice 4 18:00
Bob 10 19:00 Birthday

在這一個題目中，你必須觀察 `main.cpp` 與 `pC.hpp` 完成相關 Function 的實作，使其功能正確。

:::warning
從早到晚定義是 `00:00` ~ `23:59`，時間輸入的格式保證會是 `HH:MM`，例如：凌晨 3 點的話會是 `03:00`。
:::

### main.cpp (不可動)

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include "pC.hpp"
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<Reservation*> reservations;
    cin.ignore();
    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);
        stringstream ss(s);
        vector<string> v;
        string temp;
        while( ss >> temp ) {
            v.push_back(temp);
        }
        
        if( v.size() == 4 ) {
            reservations.push_back(new VIPReservation(v[0], stoi(v[1]), v[2], v[3]));
        }
        else {
            reservations.push_back(new StandardReservation(v[0], stoi(v[1]), v[2]));
        }
    }
    
    sort(reservations.begin(), reservations.end(), cmp);
    for(int i = 0; i < reservations.size(); i++) {
        cout << reservations[i]->getDetails() << "\n";
    }
}

### pC.hpp (不可動)

#include <iostream>


class Reservation {
    protected:
        std::string customerName;
        int numGuests;
        std::string reservationTime;
        std::string type;

    public:
        Reservation(const std::string& name, int guests,
                    const std::string& time)
            : customerName(name),
                numGuests(guests),
                reservationTime(time) {}

        virtual std::string getDetails() const = 0;
        std::string getReservationTime() const { return reservationTime; }
};
class StandardReservation : public Reservation {
    public:
        StandardReservation(const std::string& name, int guests,const std::string& time);
        std::string getDetails() const override;
};
class VIPReservation : public Reservation {
    public:
        VIPReservation(const std::string& name, int guests,const std::string& time, const std::string& type);
        std::string getDetails() const override;
};

bool cmp(Reservation* a, Reservation* b);

### pC.cpp

請自行創建 `pC.cpp` 並根據 `main.cpp` 的實作，完成 `pC.hpp` 的所有 Function。

### Compile Commands

g++ -o pC pC.cpp main.cpp

### Input Limits

- 輸入格式保證正確，與 `main.cpp` 相符。
- $1 \le n \le 10$。
- 保證沒有人同時到場。

### Sample

#### Input: 1

5
rrruuu56 4 18:00
Bob 10 19:00 Birthday
Charlie 2 17:30 VIP
David 6 18:30 Dinner
Eve 3 20:00

#### Output: 1

Charlie 2 17:30 VIP
rrruuu56 4 18:00 Standard
David 6 18:30 Dinner
Bob 10 19:00 Birthday
Eve 3 20:00 Standard

## Problem D. 妙麗的學習興趣 (10%, pD.cpp)


妙麗是葛來分多學院的學霸，平時常常會到霍格華滋的圖書館學習。

在新任魔藥學老師上任後，妙麗注意到了哈利的魔藥學天賦，但殊不知，那其實是因為一本混血王子的課本，上面有著許多筆記，讓哈利成為那一堂課唯一完成課堂上作業的人。

經過這一堂課後妙麗決定自己也要再加把勁追過哈利，因此這天他來到了圖書館想要繼續開始努力唸書，並順便找與他興趣相近的人。

圖書館有總共有 $n$ 位學生，魔法世界共有 $m$ 個不同的知識，第 $i$ 個學生對第 $j$ 個知識的興趣度為 $a_{i,j}$。

興趣的相近程度妙麗決定使用 **餘弦相似度** 來計算：

如果某位學生對所有科目的興趣度依序為 ${p_1,...,p_m}$，另一位學生對所有科目的興趣依序為 ${q_1,...,q_m}$，那麼他們兩個的餘弦相似度為：

$$\frac{\sum\limits^m_{i=1} p_iq_i }{\sqrt{\sum\limits^m_{i=1}p_i^2}\sqrt{\sum\limits^m_{i=1}q_i^2}}$$

請你設計一個程式依序輸出妙麗跟其他人的餘弦相似度，每一個餘弦相似度請 **無條件捨去到小數點後第二位 (輸出完均換行)**。

### Input Format

n m
h_1 ... h_m
a_{1,1} ... a_{1,m}
.
.
.
a_{n,1} ... a_{n,m}

$h_i$ 表示妙麗依序對所有科目的興趣度。

- $1 \le n \le 5$
- $1 \le m \le 50$
- $1 \le h_i,a_{i,j} \le 100$。
- 保證所有興趣度都是正整數。

### Sample

#### Input 1:

2 3
10 20 30
40 50 60
40 50 60

#### Output 1:

0.97
0.97

#### Input 2:

1 39
52 88 78 46 95 84 98 55 3 68 42 6 18 98 27 38 43 68 83 12 69 12 30 6 2 54 74 45 41 49 21 59 16 6 32 6 11 64 66
26 19 50 37 79 100 40 81 77 15 50 83 62 25 76 27 48 66 61 46 4 78 96 61 28 64 81 20 6 86 9 4 55 67 65 34 49 1 43

#### Output 2:

0.69

#### Input 3:

1 39
21 95 89 73 90 9 55 85 32 30 21 68 59 82 91 20 64 52 70 6 88 53 47 30 47 34 14 11 22 42 15 28 54 37 48 29 3 14 13
18 77 90 58 54 38 94 49 45 66 13 74 11 14 64 72 95 54 73 79 41 35 40 84 53 9 17 23 98 26 12 54 23 13 67 59 73 36 52

#### Output 3:

0.80

### Hints:

注意浮點數誤差的問題。

## Problem E. 定石筆記本 (pE.cpp, 10%)


Colten 這學期嘗試了許多跟資訊無關的興趣，其中一個就是下圍棋！

圍棋中有個術語叫做「定石」，定石就類似於一種模板，常用於佈局階段，如果雙方都照著這
個模板走，那基本上會是雙方都不太吃虧的一個局面。定石這一個概念從古時候就開始，後來 AI 出來之後對許多古老的定石做了許多的翻新，也給了人類許多不一樣的思考方式。


為了避免記定石記到自己忘了，Colten 想要設計一個定石筆記本的程式，這個程式一開始會讓使用者依序以棋盤座標 **(格式：大寫英文字母-數字)** 輸入每一手棋要下在的位置，最後依照上圖的棋盤座標輸出一個 $19 \times 19$ 的二維陣列，並將剛剛每一手棋的順序以數字編號 (從 $1$ 開始) 輸出，如果該位置沒有任何棋子則輸出字元 `-` (可參考範例輸出，最後均換行)。

:::warning
請特別注意，棋盤上的座標沒有 `I`。
:::

### Input Format

n
[A-T]-[1-19]
.
.
.
[A-T]-[1-19]

$n$ 表示這一個定石的總手數。 (簡單來說就是要下幾步棋的意思)

- $1 \le n \le 10$。
- 保證輸入格式符合規定，且不會超出棋盤外。
- 棋盤上沒有 `I` ，所以保證不出現 `I`

### Sample

#### Input 1 (木谷定石)

8
Q-3
Q-5
R-5
R-6
R-4
Q-6
O-3
Q-10

#### Output 1

-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
---------------8---
-------------------
-------------------
-------------------
---------------64--
---------------23--
----------------5--
-------------7-1---
-------------------
-------------------

<img src="https://hackmd.io/_uploads/B1SrA557xx.png" alt="435703187_7467726613345177_3162609758713994207_n-2-2" width="500">

#### Input 2 (點三三變化其一)

6
Q-4
R-3
Q-3
R-4
Q-5
S-6

#### Output 2

-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-------------------
-----------------6-
---------------5---
---------------14--
---------------32--
-------------------
-------------------

<img src="https://hackmd.io/_uploads/B12qki5Xxl.png" alt="435703187_7467726613345177_3162609758713994207_n-2-2" width="500">

## Problem F. 傲慢與偏見 (pF.cpp, 10%)


傲慢與偏見非常著名的英國名著，小說內容描寫著 19 世紀英格蘭攝政時代英國鄉紳階層的禮節與婚姻的狀態。

達西是這一本書的男主角，是一名非常有錢的人，某天他想要為他的莊園購買一些昂貴的畫像來裝飾，他總共挑了 $n$ 個畫像，每一個畫像的非常昂貴，第 $i$ 個畫像的金額為 $p_i$。

為了快速的知道每一個畫像的價位，達西希望你能幫忙把這一些畫像由大到小排序好，你能設計一個程式幫忙他嗎？ **(輸出每個數字後請記得換行)**

### Input Format

n
p_1 ... p_n

- $1 \le p_i \le 10^{100}$
- $1 \le n \le 10$
- 保證輸入都是正整數。

### Example

#### Input 1

5
1 2 3 4 5

#### Output 1

5
4
3
2
1

#### Input 2

2
329479174981748973189347981141 3

#### Output 2

329479174981748973189347981141
3

## Problem G. 分數計算機 (20%, pG.cpp)

Colten 的暑假作業拿到了很多題的分數運算題目，這些題目他一下子就用計算機計算完了，不過都沒有計算過程，於是他決定要透過程式把計算過程補上。

但是 Colten 不是寫程式的高手，請你設計一個程式，該程式必須做到以下事項: 給你兩個分數，請你輸出這兩個分數進行運算的結果 (化成最簡分數)。

**特別注意的是，輸入的分數有可能是真分數、假分數或帶分數。 最簡分數的定義:分數必須為真分數或帶分數，且分子與分母互質，如果只有整數部分，則輸出一個整數即可 (請參考範例 4)。**

### Input Format

輸入只有一行，格式為: [分數 A] [運算符號] [分數 B]

如果分數為真分數或假分數，格式為: [分子]/[分母]。

如果為帶分數則是: [整數] [分子]/[分母]。

- 運算符號只會出現 `+`、`-`、`*`、`/`。
- 保證所有數字都是正整數且不超過 $10^4$。
- 保證輸入格式正確。

### Output Format

輸出運算的過程，第一行與第二行依序先輸出 A 跟 B 的分數類型。
- 如果是真分數則輸出 "[A or B] is a Proper Fraction."(不含引號)。
- 如果是假分數則輸出 "[A or B] is a Improper Fraction."(不含引號)。
- 如果是帶分數則輸出 "[A or B] is a Mixed Fraction."(不含引號)。

接下來第三行輸出”[分數 A 化成最簡分數] [運算符號] [分數 B 化成最簡分數]”。 第四行輸出運算完的結果，該結果必須是最簡分數，輸出的格式跟輸入分數時的格式一樣。

**特別注意:如果分數不是帶分數，請不用輸出帶分數整數位的 0，除此之外如果分子 為 0，輸出整數部分即可。**

(最後均有換行)

:::warning
如果同時為帶分數與假分數，則以帶分數為主。

真分數：分子 < 分母
假分數：分子 >= 分母
:::

### Example

#### Input 1

1 2/3 + 2 3/4

#### Output 1

A is a Mixed Fraction.
B is a Mixed Fraction.
1 2/3 + 2 3/4
4 5/12

#### Input 2

2/3 * 4/2

#### Output 2

A is a Proper Fraction.
B is a Improper Fraction.
2/3 * 2 
1 1/3

#### Input 3

1/1 / 1/1

#### Output 3

A is a Improper Fraction.
B is a Improper Fraction.
1 / 1
1

#### Input 4

10000 1/1 * 10000 1/1

#### Output 4

A is a Mixed Fraction.
B is a Mixed Fraction.
10001 * 10001 
100020001

#### Input 5

10000 9999/1000 / 10000/9999

#### Output 5

A is a Mixed Fraction.
B is a Improper Fraction.
10009 999/1000 / 1 1/9999
10008 9980001/10000000

## Problem H. 函數計算問題 (15%, pH.cpp)

現在有三個函數 $f,g,h$ 這三個函數的定義分別如下：

$$f(x,y,z) = 10x + 9y + z$$

$$g(x) = 8x+71$$

$$h(x,y) = 4x-7y$$

現在請你設計一個程式，輸入一串滿足上方函數定義的式子並輸出計算結果。

### Input Format

輸入只有一行，包含一個字串，字串的第一個字元一定是 $f,g,h$ 其中一個。

- 如果參數是一個數字，保證大小介於 $0 \sim 9$ 且是非負整數。
- 整串式子的長度不超過 $100$。
- 兩個參數之間以 `,` 隔開。
- 保證計算過程中，答案不會超過 $10^{18}$。
- 保證運算式符合規範。

### Output Format

輸出一個整數表示計算結果，最後記得換行。

### Example

#### Input 1

f(g(7),h(1,2),f(1,1,5))

#### Output 1

1204

#### Input 2

f(1,2,3)

#### Output 2

31

#### Input 3

g(1)

#### Output 3

79

#### Input 4

g(f(g(2),f(1,2,3),g(2)))

#### Output 4

9959