# 郭老題目
# 1 一元二次方程式

:::spoiler

001. 一元二次方程式

一元二次方程式，aX^2 + bx + c = 0，輸入a, b, c, 求 方程式的兩個實根。(測資只有重根的情況)

---------------
輸入說明

第一個數(int) a
第二個數(int) b
第三個數(int) c

---------------
輸出說明

第一個實根 x1 = ((-b)+sqrt(b*b-4*a*c))/(2*a)
第二個實根 x2 = ((-b)-sqrt(b*b-4*a*c))/(2*a)

x1, x2 輸出到小數點第一位
printf("%.1f", x1);

---------------
Input
1
-2
1

Output
1.0
1.0

---------------
Input
1
10
25

Output
-5.0
-5.0

---------------
Input
1
0
0

Output
0.0
0.0

:::
# 2 跑壘問題
:::spoiler

002. 跑壘問題

輸入棒球隊球員打擊結果，計算出隊得分。假設球員打擊情況：
安打：以1, 2, 3 和 H代表一、二、三和全(四)壘打。
出局：以 O表示 (OUT)。
簡化版的規則如下：
球場 上有四個壘包， 稱為本壘、一、二和三壘。
本壘握球棒打的稱「擊球員」 ，在另外三個壘包的稱為「跑員」。
當擊球員打擊「安打」時， 擊球員與跑壘員可移動；「出局」時，跑壘員不動，擊球員離場換下一位。
比賽開始由第 1位打擊，接著2, 3, 4, 5位球員。
打出 K 壘打時，場上球員(擊球員和跑壘員)會前進 K個壘包。本壘到一壘，接著二、三壘，最後回到本壘。回到本壘可得 1分。
每達到三個出局數時，壘包清空(跑壘員都得離開)，重新開始。
輸入5位打者打擊資料，輸出最後一、二、三壘狀況，有人為1，沒人為0。

---------------
Input
1
1
O
O
1

Output
1
1
1

---------------
Input
1
O
O
H
1

Output
1
0
0

---------------
Input
H
H
H
H
H

Output
0
0
0

---------------
Input
O
O
O
1
1

Output
1
1
0

:::
# 3 工資計算
:::spoiler

003.工資計算

假設工作一小時x元(整數) ，全部薪資所得的8%取到小數第一位是稅金，而勞保費為最低工資y元(整數)的5%取到小數第一位。
請分開輸入二個月工作時數(整數) 、還有x與 y。
輸出扣完稅與勞保後實際所得、勞保費、稅金。
(浮點數宣告請用float)
(勞保費兩個月繳一次)

---------------
範例輸入說明
100 (第一個月工作時數)
200 (第二個月工作時數)
160 (時薪x)
23000 (最低工資y)

範例輸出說明
43010.0 (扣完稅與勞保後實際所得 (100+200)*160-1150-3840=43010)
1150.0 (勞保費 23000*5%=1150)
3840.0 (稅金 (100+200)*160*8%=3840)

---------------
Input
100
200
160
23000

Output
43010.0
1150.0
3840.0

---------------
Input
0
300
200
20000

Output
54200.0
1000.0
4800.0

---------------
Input
0
0
500
40000

Output
-2000.0
2000.0
0.0

:::
# 4 面積周長
:::　spoiler

004

輸入一正浮點數a，為一圓形之半徑，計算面積和周長並依序輸出。
(運用定義常數#define PI 3.14159定義PI=3.14159)
---------------
輸入說明

正浮點數a
---------------
輸出說明

面積 = 半徑 * 半徑 * PI
周長 = 2 * 半徑 * PI

面積, 周長 四捨五入輸出至小數點第三位
---------------
sample Input 1
5.0

sample Output 1
78.540
31.416

---------------
sample Input 2
3.8

sample Output 2
45.365
23.876

:::
# 5 衝堂節數
:::spoiler

005
查詢三門課程的衝堂節數(固定衝堂一節)，
依序輸入課程編號(數字)、
上課小時數(1-3小時)、
上課時間(星期1-5, 第1-9節)
---------------
輸入說明
1001 (第一門課課程編號)
3 (3小時)
11 (星期1 第1節課)
59 (星期5 第9節課)
25 (星期2 第5節課)
2020 (第二門課課程編號)
2
25
16
2030 (第三門課課程編號)
1
31

輸出說明 (兩課程編號衝突在哪一節)
1001 and 2020 conflict on 25
---------------
Sample Input 1：
1001
3
11
12
13
1002
3
21
22
23
1003
3
31
32
13

Sample Output 1：
1001 and 1003 conflict on 13
---------------
Sample Input 2：
111
1
11
122
3
21
22
11
133
3
31
32
33

Sample Output 2：
111 and 122 conflict on 11

:::
# 6 每月通信
:::spoiler

006
輸入每月通信數據，包含網內、網外語音秒數、市話通話時間及網內、網外簡訊則數，計算並比較各資費類型所需繳交通信費，求出最佳資費類型。

費率如下表：
*繳交費用四捨五入至個位數
*月租費可抵等額通信費
ie. 通信費若高於月租費則繳交通信費之費用金額，若低於月租費則繳交月租費之費用金額

資費類型 183型 383型 983型
月租費 183元 383元 983元
網內語音(元/秒) 0.08 0.07 0.06
網外語音(元/秒) 0.1393 0.1304 0.1087
市話(元/秒) 0.1349 0.1217 0.1018
網內簡訊(元/則) 1.1287 1.1127 0.9572
網外簡訊(元/則) 1.4803 1.2458 1.1243

https://ppt.cc/fxFF2x
*此連結為費率表格整理，方便同學閱讀理解
---------------
輸入說明
分別輸入 網內語音(sec)、網外語音(sec)、市話(sec)、網內簡訊數、網外簡訊數

輸出說明
輸出最佳資費類型
---------------
範例輸入說明：
200 網內語音200sec
200 網外語音200sec
200 市話200sec
200 網內簡訊數200則
200 網外簡訊數200則

範例輸出說明：
383

以下為計算過程：
分別計算三種資費類型所需繳交費用
183型：200*0.08+200*0.1393+200*0.1349+200*1.1287+200*1.4803 = 592.64
383型：200*0.07+200*0.1304+200*0.1217+200*1.1127+200*1.2458 = 536.12
983型：200*0.06+200*0.1087+200*0.1018+200*0.9572+200*1.1243 = 470.4

由於183型及383型的通信費皆超過本身資費，故皆繳交通信費之費用金額
而983型的通信費未超過本身資費，故繳交983型資費之費用金額

需繳交金額：
183型：593元
383型：536元
983型：983元
經比較過後，選擇383型所繳交之資費金額最少，故輸出383
---------------
Sample Input 1：
500
120
13
2
5

Sample Output 1：
183
---------------
Sample Input 2：
200
200
200
200
200

Sample Output 2：
383
---------------
Sample Input 3：
459
166
83
177
93

Sample Output 3：
383
---------------
Sample Input 4：
411
413
417
429
423

Sample Output 4：
983
---------------
Sample Input 5：
0
0
0
0
0

Sample Output 5：
183

:::
# 7 撲克牌
:::spoiler

007
撲克牌

牌面有以下13種：A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
各牌面點數分別為：A~10 為 1~10，J, K, Q 為 0.5。

A, B 兩個人各發三張撲克牌，加總點數越接近 10.5 的贏；超過 10.5 則爆掉且分數為 0。
---------------
輸入說明
分別輸入 A, B 兩人各三張撲克牌。

輸出說明
輸出A, B 兩人的總點數(輸出至小數點後第一位)
以及比較結果(A wins.或B wins.或It's a tie.)
---------------
Sample Input 1：
5
2
3
J
3
4

Sample Output 1：
10.0
7.5
A wins.
---------------
Sample Input 2：
K
2
3
2
2
3

Sample Output 2：
5.5
7.0
B wins.
---------------
Sample Input 3：
A
A
A
A
A
A

Sample Output 3：
3.0
3.0
It's a tie.
---------------
Sample Input 4：
Q
J
K
10
10
10

Sample Output 4：
1.5
0.0
A wins.
---------------
Sample Input 5：
7
K
7
A
2
3

Sample Output 5：
0.0
6.0
B wins.
---------------
Sample Input 6：
7
7
7
7
7
7

Sample Output 6：
0.0
0.0
It's a tie.

:::
# 8 圖形
:::spoiler

008
請使用 while loop或for loop
第一個輸入為選擇三種圖形:
1 三角形方尖方面向右邊
2 三角形方尖方面向左邊
3 菱形

第二個輸入意義為畫幾行
(奇數，範圍為 3,5,7,9,....,21)
--------------------------
sample input 1
1 (第一種圖形，三角形尖方面向右邊)
3 (共 3 行)

sample output 1
*
**
*
--------------------------
sample input 2
1 (第一種圖形，三角形尖方面向右邊)
21 (共 21 行)

sample output 2
*
**
***
****
*****
******
*******
********
*********
**********
***********
**********
*********
********
*******
******
*****
****
***
**
*
---------------------------
sample input 3
2 (第二種圖形，三角形尖方面向左邊)
3 (共 3 行)

sample output 3
.*
**
.*
---------------------------
sample input 4
2 (第二種圖形，三角形尖方面向左邊)
21 (共 21 行)

sample output 4
..........*
.........**
........***
.......****
......*****
.....******
....*******
...********
..*********
.**********
***********
.**********
..*********
...********
....*******
.....******
......*****
.......****
........***
.........**
..........*
--------------------------
sample input 5
3 (第三種圖形: 菱形 )
3 (共 3 行數)

sample output 5
.*
***
.*
--------------------------
sample input 6
3 (第三種圖形: 菱形 )
21 (共 21 行數)

sample output 6
..........*
.........***
........*****
.......*******
......*********
.....***********
....*************
...***************
..*****************
.*******************
*********************
.*******************
..*****************
...***************
....*************
.....***********
......*********
.......*******
........*****
.........***
..........*

:::
# 9 葛雷碼
:::spoiler

009
葛雷碼 (Gray code)
反射二進位編碼-葛雷碼 (Gray code)，是編碼成兩個連續的不同位元
其編碼規則如下：
G_1 = {0, 1}
G_1_r = {1, 0}
G_n = {0G_(n-1), 1G_(n-1)_r }
G_n_r 是 G_n 的逆向順序
其中n為Gray code的位元數

ex :
G_2 = {0G_1, 1G_1_r} = {00, 01, 11, 10}
G_2_r = {10, 11, 01, 00}
G_3 = {0G_2, 1G_2_r } = {0{00, 01, 11, 10}, 1{10, 11, 01, 00}} = {000, 001, 011, 010, 110, 111, 101, 100}
-------------
輸入說明 :
連續輸入多筆測試案例，且案例之間以一行 0 分隔，
每筆測試案例分別輸入兩整數n k，以空格分隔，
其中n代表Gray code的位元數
k代表G_n中的第幾個元素(從0開始)
輸入直到 -1 結束

輸出說明 :
輸出各筆測試案例的二進位 Gray code，以隔行分隔
-------------
Sample Input 1
1 0
-1

Sample Output 1
0
-------------
Sample Input 2
2 3
0
3 6
-1

Sample Output 2
10
101
-------------
Sample Input 3
4 12
0
5 3
0
6 10
-1

Sample Output 3
1010
00010
001111
-------------
Sample Input 4
7 19
0
8 1
0
9 80
0
10 10
-1

Sample Output 4
0011010
00000001
001111000
0000001111
-------------
Sample Input 5
11 99
0
12 13
0
13 22
0
14 17
0
15 6
-1

Sample Output 5
00001010010
000000001011
0000000011101
00000000011001
000000000000101

:::
# 10 數位電路模擬
:::spoiler

010 數位電路模擬

數位IC輸入m 是二進位 8 位元，輸出是二進位 4 位元。
輸入範圍從 00000000 到 11111111 (十進位 0~255)。
輸出範圍從 0000 到 1111 (十進位 0~15)
=================
數位IC內有一個回饋電路接收輸入m，視為一個函數C(m)，其回饋方式如下：
1. 若m為偶數(十進位)，則C(m) = C(m/2)
2. 若m為奇數(十進位)，則C(m) = C((m+1)/2)
3. 若m = 1 or 0，則回饋電路結束

數位IC內有一個紀錄器，會記錄回饋電路的回饋次數。
R(m) = [C(m)的回饋次數]，例如：R(10) = 4。

數位IC的輸出為紀錄器所記錄之回饋電路的回饋次數。
=================
題目要求：
1. 設計數位IC的function
2. 主程式中可接受多組輸入，並經過數位IC後，一次輸出所有數位IC的輸出結果
=================
輸入說明：
可接受多組二進位8位元的輸入m，
每組輸入以一行0區隔，直到-1後停止輸入。

輸出說明：
輸出每組二進位8位元的輸入m進入數位IC後的輸出結果，每組輸出以隔行區隔。
Note：切勿輸入一組m後就印出數位IC結果，請於輸入-1後才一次印出所有結果
=================
數位IC範例說明：
1. 00001010 輸入二進位8位元m (十進位為10)
2. 進入回饋電路C(10)
3. 10為偶數，因此第一輪回饋為C(10) = C(5)
4. 5為奇數，因此第二輪回饋為C(5) = C(3)
5. 3為奇數，因此第三輪回饋為C(3) = C(2)
6. 2為奇數，因此第四輪回饋為C(2) = C(1)
7. m=1，因此回饋電路結束
8. 總計回饋4次，因此輸出0100(十進位為4)
=================
Sample Input 1：
00000000
-1

Sample Output 1：
0000
=================
Sample Input 2：
11111111
0
10000000
-1

Sample Output 2：
1000
0111
=================
Sample Input 3：
00001111
0
00010000
0
00010001
0
00010010
-1

Sample Output 3：
0100
0100
0101
0101
=================
Sample Input 4：
11110000
0
00001111
0
10101010
0
01010101
0
10100101
-1

Sample Output 4：
1000
0100
1000
0111
1000
=================
Sample Input 5：
11001100
0
10100101
0
10100110
0
01011010
0
01110110
0
11111100
0
00011000
0
01101111
0
00011110
0
01110000
-1

Sample Output 5：
1000
1000
1000
0111
0111
1000
0101
0111
0101
0111

:::
# 11 數位電路模擬II
:::spoiler

011
數位電路模擬II

數位IC輸入m 是二進位 8 位元，輸出是二進位 11 位元。
輸入範圍從 00000000 到 11111111 (十進位 0~255)。
輸出範圍從 00000000000 到 11111111111 (十進位 0~2047)
=================
數位IC內有一個回饋電路接收輸入m，視為一個函數C(m)，其回饋方式如下：
1. 若m為偶數(十進位)，則C(m) = C(m/2)
2. 若m為奇數(十進位)，則C(m) = C((m+1)/2)
3. 若m = 1 or 0，則回饋電路結束

數位IC內有一個紀錄器，會記錄回饋電路的回饋次數。
R(m) = [C(m)的回饋次數]，例如：R(10) = 4。

數位IC的輸出為紀錄器所記錄之回饋電路的累積回饋次數。
Out(m) = [R(0)+R(1)+R(2)+…+R(m)]，
例如：Out(3) = R(0)+R(1)+R(2)+R(3) = 0+0+1+2 = 3
=================
題目要求：
1. 設計數位IC的function
2. 主程式中可接受多組輸入，並經過數位IC後，一次輸出所有數位IC的輸出結果
=================
輸入說明：
可接受多組二進位8位元的輸入m，
每組輸入以一行0區隔，直到-1後停止輸入。

輸出說明：
輸出每組二進位11位元的輸入m進入數位IC後的輸出結果，每組輸出以隔行區隔。
Note：切勿輸入一組m後就印出數位IC結果，請於輸入-1後才一次印出所有結果
=================
數位IC範例說明：
1. 00001010 輸入二進位8位元m (十進位為10)
2. 進入回饋電路Out(10)
3. 分別計算R(0)至R(10)
4. 上述11筆回饋電路總合為25
5. 轉換為二進位11bit，因此輸出00000011001
=================
Sample Input 1：
00000000
-1

Sample Output 1：
00000000000
=================
Sample Input 2：
11111111
0
10000000
-1

Sample Output 2：
11011111001
01100000001
=================
Sample Input 3：
00001111
0
00010000
0
00010001
0
00010010
-1

Sample Output 3：
00000101101
00000110001
00000110110
00000111011
=================
Sample Input 4：
11110000
0
00001111
0
10101010
0
01010101
0
10100101
-1

Sample Output 4：
11010000001
00000101101
10001010001
00111010100
10000101001
=================
Sample Input 5：
11001100
0
10100101
0
10100110
0
01011010
0
01110110
0
11111100
0
00011000
0
01101111
0
00011110
0
01110000
-1

Sample Output 5：
10101100001
10000101001
10000110001
00111110111
01010111011
11011100001
00001011001
01010001010
00001110111
01010010001

:::
# 12 分數四則運算
:::spoiler

012
分數四則運算

計算兩個分數四則運算 。
=================
輸入說明：
輸入四行，第一、二行各代表一個分數，第三行代表數學運算符號(+-*/)，第四行代表是否繼續運算(y表示繼續運算、n表示不繼續運算)
=================
輸出說明：
輸出分數結果
=================
輸入輸出注意事項：
1. 輸入分數可能為假分數
2. 若輸入分數的分母為0，則該筆output輸出ERROR
3. 輸出分數必須以帶分數形式表示，且其真分數部分需化簡為最簡分數
4. 若輸出分數大於1，則分數部分要加括號，例如：一又六分之一輸出為1(1/6)
5. 輸入或輸出若為負數，則負號必於最前面。
6. 若輸出為0，則顯示0
7. 處理除法且第二個分數的分母為0時，仍然須輸出ERROR(詳見範例測資1的倒數兩組四則運算)
8. 程式無需處理非零分數除以零(分子為0但分母不為0)的情況
=================
Sample input 1：
3/0
9/70
+
y
5/60
87/0
+
y
13/0
17/0
+
y
8/0
29/90
-
y
9/50
1/0
-
y
3/0
7/0
-
y
38/0
2/70
*
y
9/10
91/0
*
y
55/0
77/0
*
y
20/0
2/30
/
y
1/70
90/0
/
y
32/0
79/0
/
n

Sample output 1：
ERROR
ERROR
ERROR
ERROR
ERROR
ERROR
ERROR
ERROR
ERROR
ERROR
ERROR
ERROR
=================
Sample input 2：
2/3
-12/18
+
y
-13/3
65/15
+
y
0/39
0/44
+
y
-7/9
-63/81
-
y
7/11
49/77
-
y
0/31
0/37
-
y
0/98
7/57
*
y
29/33
0/87
*
y
0/22
0/82
*
y
0/53
37/64
/
n

Sample output 2：
0
0
0
0
0
0
0
0
0
0
=================
Sample input 3：
3/2
15/6
+
y
91/21
-4/3
+
y
-14/8
43/4
+
y
52/7
21/49
-
y
17/2
-18/4
-
y
-55/55
-99/11
-
y
4/3
12/8
*
y
-14/2
-8/7
*
y
7/4
28/80
/
y
-6/15
-2/5
/
n

Sample output 3：
4
3
9
7
13
8
2
8
5
1
=================
Sample input 4：
5/13
-88/26
+
y
-97/7
100/35
+
y
-4/3
-88/24
+
y
38/8
35/4
-
y
-20/50
8/5
-
y
-97/3
-282/9
-
y
-7/5
90/21
*
y
11/9
-72/4
*
y
-16/9
32/126
/
y
1/11
-3/99
/
n

Sample output 4：
-3
-11
-5
-4
-2
-1
-6
-22
-7
-3
=================
Sample input 5：
7/13
-4/3
+
y
-6/7
2/9
+
y
-1/5
-1/7
+
y
7/13
4/3
-
y
-1/5
1/7
-
y
-6/7
-2/9
-
y
-5/7
9/11
*
y
13/23
-2/3
*
y
-5/7
9/11
/
y
13/23
-2/3
/
n

Sample output 5：
-31/39
-40/63
-12/35
-31/39
-12/35
-40/63
-45/77
-26/69
-55/63
-39/46
=================
Sample input 6：
2/3
25/15
+
y
9/7
-1/5
+
y
-3/5
29/13
+
y
9/7
1/5
-
y
2/3
-25/15
-
y
-3/5
-29/13
-
y
29/13
7/3
*
y
-7/9
-11/4
*
y
29/13
3/7
/
y
-7/9
-4/11
/
n

Sample output 6：
2(1/3)
1(3/35)
1(41/65)
1(3/35)
2(1/3)
1(41/65)
5(8/39)
2(5/36)
5(8/39)
2(5/36)
=================
Sample input 7：
3/7
-53/11
+
y
-11/9
1/13
+
y
-2/3
-23/8
+
y
3/7
53/11
-
y
-2/3
23/8
-
y
-11/9
-1/13
-
y
-23/29
4/3
*
y
19/21
-11/5
*
y
-23/29
3/4
/
y
19/21
-5/11
/
n

Sample output 7：
-4(30/77)
-1(17/117)
-3(13/24)
-4(30/77)
-3(13/24)
-1(17/117)
-1(5/87)
-1(104/105)
-1(5/87)
-1(104/105)
=================
Sample input 8：
16/84
26/21
+
y
57/39
-10/78
+
y
-111/231
128/77
+
y
57/39
10/78
-
y
16/84
-26/21
-
y
-111/231
-128/77
-
y
13/7
21/2
*
y
-17/5
-25/34
*
y
13/7
2/21
/
y
-17/5
-34/25
/
n

Sample output 8：
1(3/7)
1(1/3)
1(2/11)
1(1/3)
1(3/7)
1(2/11)
19(1/2)
2(1/2)
19(1/2)
2(1/2)
=================
Sample input 9：
23/10
-138/20
+
y
-48/14
26/28
+
y
-29/6
-58/12
+
y
23/10
138/20
-
y
-29/6
58/12
-
y
-48/14
-26/28
-
y
-13/7
35/29
*
y
19/9
-27/2
*
y
-13/7
29/35
/
y
19/9
-2/27
/
n

Sample output 9：
-4(3/5)
-2(1/2)
-9(2/3)
-4(3/5)
-9(2/3)
-2(1/2)
-2(7/29)
-28(1/2)
-2(7/29)
-28(1/2)

:::
# 13 兩個點，求直線方程式
:::spoiler

013

輸入平面上兩個點，求直線方程式
輸入兩點座標，(x1, y1), (x2, y2)
輸出 y = mx + b(其中，m=(y1-y2)/(x1-x2)、b = (x2y1-x1y2)/(x2-x1))
=================
輸入說明：
輸入兩行x,y分別代表兩點座標 (x1, y1), (x2, y2)，其中x1、x2、y1、y2皆為整數
x,y 之間以一個逗號區隔

輸出說明：
輸出直線方程式y=mx+b
=================
輸入輸出注意事項：
1.無需考慮斜率不存在的直線方程式(垂直於x軸的直線方程式)
2.若斜率為0(垂直於y軸的直線方程式)，則輸出y=b (詳見範例測資1、2)
3.若直線方程式通過原點，則輸出y=mx (詳見範例測資13~16)
4.若m為正數，則無須輸出正號，若為負數，則需輸出負號，負號置於m最前方
5.若m為正負1，則無需輸出1的部分 (詳見範例測資13、14)
6.若m或b為整數，皆直接輸出整數
7.若m或b為分數，皆須以帶分數形式表示，且其真分數部分需化簡為最簡分數
8.若m或b為分數且取絕對值後大於1，則分數部分皆須加括號，例如：一又六分之一輸出為1(1/6)
9.請務必記得初始化變數
=================
sample input 1：
-8,0
13,0

sample output 1：
y=0
=================
sample input 2：
17,-8
-7,-8

sample output 2：
y=-8
=================
sample input 3：
0,2
1,7

sample output 3：
y=5x+2
=================
sample input 4：
1,-10
-2,11

sample output 4：
y=-7x-3
=================
sample input 5：
1,1
6,4

sample output 5：
y=3/5x+2/5
=================
sample input 6：
12,1
5,-1

sample output 6：
y=2/7x-2(3/7)
=================
sample input 7：
6,-5
-4,3

sample output 7：
y=-4/5x-1/5
=================
sample input 8：
1,2
-5,7

sample output 8：
y=-5/6x+2(5/6)
=================
sample input 9：
1,8
-3,-11

sample output 9：
y=4(3/4)x+3(1/4)
=================
sample input 10：
9,1
-18,-41

sample output 10：
y=1(5/9)x-13
=================
sample input 11：
4,-9
-5,6

sample output 11：
y=-1(2/3)x-2(1/3)
=================
sample input 12：
7,-12
-7,20

sample output 12：
y=-2(2/7)x+4
=================
sample input 13：
8,8
-10,-10

sample output 13：
y=x
=================
sample input 14：
-10,10
8,-8

sample output 14：
y=-x
=================
sample input 15：
9,-5
-18,10

sample output 15：
y=-5/9x
=================
sample input 16：
4,-14
-6,21

sample output 16：
y=-3(1/2)x

:::

# 14 1A2B遊戲
:::spoiler

014
1A2B遊戲

小明和小萱在玩猜數字遊戲，
由小明先輸入四個數字為謎底(數字不重複，0可置於首位)，
小萱輸入想要猜的四個數字(數字不重複)。
若猜中數字則遊戲結束並輸出win
若猜錯則顯示XAYB（X表示位置和數字皆正確的個數，而Y表示數字正確而位置不對的個數）
遊戲最多猜六次，若6次後仍未猜對則遊戲結束(最後一次仍需顯示XAXB)
=================
範例輸入說明：
1234 (謎底)
5678
5178
1578
1478
1724
1234

範例輸出說明：
0A0B (皆未符合)
0A1B (1為B)
1A0B (1為A)
1A1A (1為A，4為B)
2A1B (1、4為A，2為B)
win
=================
sample input 1：
0936
0936

sample output 1：
win
=================
sample input 2：
1953
4270
1953

sample output 2：
0A0B
win
=================
sample input 3：
1953
9315
1953

sample output 3：
0A4B
win
=================
sample input 4：
1953
1359
1953

sample output 4：
2A2B
win
=================
sample input 5：
0192
1029
1920
0192

sample output 5：
0A4B
0A4B
win
=================
sample input 6：
0192
0129
0912
0192

sample output 6：
2A2B
2A2B
win
=================
sample input 7：
0192
8324
4027
0192

sample output 7：
0A1B
0A2B
win
=================
sample input 8：
1324
3142
3241
4132
1324

sample output 8：
0A4B
0A4B
0A4B
win
=================
sample input 9：
1324
1423
1234
2314
1324

sample output 9：
2A2B
2A2B
2A2B
win
=================
sample input 10：
1324
7132
1790
0349
1324

sample output 10：
0A3B
1A0B
1A1B
win
=================
sample input 11：
9870
7098
0987
8709
7908
9870

sample output 11：
0A4B
0A4B
0A4B
0A4B
win
=================
sample input 12：
9870
9807
8970
9078
0879
9870

sample output 12：
2A2B
2A2B
2A2B
2A2B
win
=================
sample input 13：
9870
7806
9708
9812
9074
9870

sample output 13：
1A2B
1A3B
2A0B
2A1B
win
=================
sample input 14：
5620
2056
2506
6205
6502
0265
5620

sample output 14：
0A4B
0A4B
0A4B
0A4B
0A4B
win
=================
sample input 15：
5620
5602
6520
0625
5260
2650
5620

sample output 15：
2A2B
2A2B
2A2B
2A2B
2A2B
win
=================
sample input 16：
5620
0562
5629
1348
5026
9173
5620

sample output 16：
0A4B
3A0B
0A0B
2A2B
0A0B
win
=================
sample input 17：
0987
9078
7098
8709
9870
8709
7890

sample output 17：
0A4B
0A4B
0A4B
0A4B
0A4B
0A4B
=================
sample input 18：
0987
0978
0789
0897
7980
8907
9087

sample output 18：
2A2B
2A2B
2A2B
2A2B
2A2B
2A2B
=================
sample input 19：
0987
0897
9708
0789
1079
8907
7650

sample output 19：
2A2B
0A4B
2A2B
0A3B
2A2B
0A2B
=================
sample input 20：
0987
7980
0912
0795
6931
8079
1094

sample output 20：
2A2B
2A0B
1A2B
1A0B
0A4B
0A2B

:::

# 15 大數運算
:::spoiler

015

首先輸入大數運算的模式，
以1代表大數相加；2代表大數相減；3代表大數相乘。
再輸入兩行20~40位數(包含上下限)的正整數做運算，
並輸出計算過後的結果。
=================
sample input 1：
1
10000000000000000000
10000000000000000000

sample output 1：
20000000000000000000
=================
sample input 2：
1
9999999999999999999999999999999999999999
10000000000000000000

sample output 2：
10000000000000000000009999999999999999999
=================
sample input 3：
1
10000000000000000000
9999999999999999999999999999999999999999

sample output 3：
10000000000000000000009999999999999999999
=================
sample input 4：
1
9999999999999999999999999999999999999999
9999999999999999999999999999999999999999

sample output 4：
19999999999999999999999999999999999999998
=================
sample input 5：
1
9578977894569458768957689498576
3879820923099819028419182498493572571412

sample output 5：
3879820932678796922988641267451262069988
=================
sample input 6：
1
12903129413974305729385092389023492
17984731893298742340

sample output 6：
12903129413974323714116985687765832
=================
sample input 7：
1
9749823749999999999991284901093564590
9749823749999999999991284901093564590

sample output 7：
19499647499999999999982569802187129180
=================
sample input 8：
2
10000000000000000000
10000000000000000000

sample output 8：
0
=================
sample input 9：
2
9999999999999999999999999999999999999999
10000000000000000000

sample output 9：
9999999999999999999989999999999999999999
=================
sample input 10：
2
10000000000000000000
9999999999999999999999999999999999999999

sample output 10：
-9999999999999999999989999999999999999999
=================
sample input 11：
2
9999999999999999999999999999999999999999
9999999999999999999999999999999999999999

sample output 11：
0
=================
sample input 12：
2
9578977894569458768957689498576
3879820923099819028419182498493572571412

sample output 12：
-3879820913520841133849723729535883072836
=================
sample input 13：
2
12903129413974305729385092389023492
17984731893298742340

sample output 13：
12903129413974287744653199090281152
=================
sample input 14：
2
9749823749999999999991284901093564590
9749823749999999999991284901093564590

sample output 14：
0
=================
sample input 15：
3
10000000000000000000
10000000000000000000

sample output 15：
100000000000000000000000000000000000000
=================
sample input 16：
3
9999999999999999999999999999999999999999
10000000000000000000

sample output 16：
99999999999999999999999999999999999999990000000000000000000
=================
sample input 17：
3
10000000000000000000
9999999999999999999999999999999999999999

sample output 17：
99999999999999999999999999999999999999990000000000000000000
=================
sample input 18：
3
9999999999999999999999999999999999999999
9999999999999999999999999999999999999999

sample output 18：
99999999999999999999999999999999999999980000000000000000000000000000000000000001
=================
sample input 19：
3
9578977894569458768957689498576
3879820923099819028419182498493572571412

sample output 19：
37164718857261238475272616357976303756722706439685013931690425232309312
=================
sample input 20：
3
12903129413974305729385092389023492
17984731893298742340

sample output 20：
232059323094864807208258211161094268960043424315051280
=================
sample input 21：
3
9749823749999999999991284901093564590
9749823749999999999991284901093564590

sample output 21：
95059063156064062499830058643396874023482100952948948951679265512501868100

:::

# 16 大數除法
:::spoiler

016 大數除法

輸入說明：
輸入兩行20~40位數(包含上下限)的正整數做除法運算
第一行為被除數，第二行為除數

輸出說明：
輸出除法運算後的商數(測資不一定皆可整除)
=================
範例輸入說明：
1000000000000000000000005 (被除數)
10000000000000000000 (除數)

範例輸出說明：
100000 (餘5但僅需輸出商數)
=================
sample input 1：
10000000000000000000
10000000000000000000

sample output 1：
1
=================
sample input 2：
1000000000000000000000000000000000000000
1000000000000000000000000000000000000000

sample output 2：
1
=================
sample input 3：
9999999999999999999999999999999999999999
9999999999999999999999999999999999999999

sample output 3：
1
=================
sample input 4：
50000000000000000000
10000000000000000000

sample output 4：
5
=================
sample input 5：
90348905290835683096
22587226322708920774

sample output 5：
4
=================
sample input 6：
9999999999999999999999999999999999999999
3333333333333333333333333333333333333333

sample output 6：
3
=================
sample input 7：
6322083025804530270923509282757380346975
1264416605160906054184701856551476069395

sample output 7：
5
=================
sample input 8：
3249872592333552350955555576
41137627751057624695639944

sample output 8：
79
=================
sample input 9：
82314783420550387123
52309850272053572532

sample output 9：
1
=================
sample input 10：
141234234353456436392
21497181748250274194

sample output 10：
6
=================
sample input 11：
54564582314783420550387123
52309850272053572532

sample output 11：
1043103
=================
sample input 12：
92342348902526234023433342
46320495364434430538

sample output 12：
1993552
=================
sample input 13：
4120428120421421849024945203957209002335
3120348124073598237483590782984678922344

sample output 13：
1
=================
sample input 14：
8487528979174018417498589236759279346745
1912490723489072389729385792835792371975

sample output 14：
4
=================
sample input 15：
1230947809145820375820342304872398432759
112274598732598726162189471982466124

sample output 15：
10963
=================
sample input 16：
7483579872987295872027089725982395823255
3749189247891277821664786328746278

sample output 16：
1996052
=================
sample input 17：
90000001421400000002000013300
12000124000045600005

sample output 17：
7499922619
=================
sample input 18：
9000000124000000460000000002400056000003
302113000000053000070070070200002040

sample output 18：
29790

:::
# 17 進位制轉換
:::spoiler

017 進位制轉換

將無號2進制數字轉換為7進制
=================
輸入說明：
輸入一行最多15bit的無號數字

輸出說明：
若數字為2進制，則將數字轉換為7進制並輸出
若數字不為2進制，則輸出ERROR
=================
範例輸入說明：
11111 (此為10進制的31)

範例輸出說明：
43 (7^1*4 + 7^0*3 = 31)
=================
sample input 1：
0

sample output 1：
0
=================
sample input 2：
1

sample output 2：
1
=================
sample input 3：
100000000000000

sample output 3：
65524
=================
sample input 4：
111111111111111

sample output 4：
164350
=================
sample input 5：
2

sample output 5：
ERROR
=================
sample input 6：
111111111161111

sample output 6：
ERROR
=================
sample input 7：
222222222222222

sample output 7：
ERROR
=================
sample input 8：
938572389573256

sample output 8：
ERROR
=================
sample input 9：
101010101010

sample output 9：
10650
=================
sample input 10：
100000010001100

sample output 10：
66114
=================
sample input 11：
111111011011101

sample output 11：
163454
=================
sample input 12：
100110011001100

sample output 12：
111214
=================
sample input 13：
100000110100111

sample output 13：
100000
=================
sample input 14：
100110010011000

sample output 14：
111111
=================
sample input 15：
100000110100110

sample output 15：
66666

:::
# 18 分散度
:::spoiler

018 分散度

給定一串整數序列，m分散度定義為，序列中擁有長度為m 且有m 種不同數字的連續子序列之數量。
=================
輸入說明：
先輸入一串整數序列(長度1~30)，
接著輸入大於0的整數m表示試求m分散度

輸出說明：
輸出給定整數序列m的分散度
=================
範例輸入說明：
1235454 (整數序列)
3 (分散度3)

範例輸出說明：
3
總計有{1 2 3}, {2 3 5}, {3 5 4}三個含有3種不同數字的連續子序列
註：{5 4 5}及{4 5 4}因4和5重複因此不計入其中
=================
sample input 1：
12345
6

sample output 1：
0
=================
sample input 2：
12345
5

sample output 2：
1
=================
sample input 3：
55555
5

sample output 3：
0
=================
sample input 4：
55555
2

sample output 4：
0
=================
sample input 5：
12345
1

sample output 5：
5
=================
sample input 6：
55555
1

sample output 6：
5
=================
sample input 7：
123456789
2

sample output 7：
8
=================
sample input 8：
187444131
2

sample output 8：
6
=================
sample input 9：
123456789
3

sample output 9：
7
=================
sample input 10：
187444131
3

sample output 10：
3
=================
sample input 11：
123456789
4

sample output 11：
6
=================
sample input 12：
187444131
4

sample output 12：
1
=================
sample input 13：
123456789
5

sample output 13：
5
=================
sample input 14：
187444131
5

sample output 14：
0
=================
sample input 15：
12333331983732353777719231
2

sample output 15：
18
=================
sample input 16：
12333331983732353777719231
3

sample output 16：
12
=================
sample input 17：
12333331983732353777719231
4

sample output 17：
6
=================
sample input 18：
12333331983732353777719231
5

sample output 18：
2
=================
sample input 19：
12333331983732353777719231
6

sample output 19：
0
=================
sample input 20：
12333331983732353777719231
7

sample output 20：
0

:::
# 19 DF-expression
:::spoiler

019 DF-expression

DF-expression是儲存圖片資訊的表達方式。

在一個n*n方陣中，
若全部方格皆為白色則記為0；
若皆為黑色則記為1；
若方格不全為白或不全為黑，則記為2，並將方格分割為更小的4塊全等方陣(左上、右上、左下、右下)，再依序(左上→右上→左下→右下)記錄這四塊方陣的資訊。
=================
DF-expression example 1：
□□□□
□□□□
□□□□
□□□□
方格全為白色，所以輸出為0。
=================
DF-expression example 2：
■■■■
■■■■
■■■■
■■■■
方格全為黑色，所以輸出為1。
=================
DF-expression example 3：
□□□□
□□■□
■■□□
■■□□
方格不全為白或不全為黑，因此先記為2，
接著將4*4的方格分隔為4塊2*2的方陣，
再依序檢視左上→右上→左下→右下四塊方陣，

□□
□□
左上方格全為白色，因此記為0，當前序列為20

□□
■□
右上方格不全為白或黑，因此記為2，
再分割為四塊1*1的方陣，並依序檢視左上→右上→左下→右下四塊方陣，
得到0010，當前序列為2020010

■■
■■
左下方格全為黑色，因此記為1，當前序列為20200101

□□
□□
右下方格全為白色，因此記為0，當前序列為202001010

方陣皆輸出完成，因此最終DF-expression為202001010
=================
輸入說明：
先輸入一張圖像的DF-expression(長度1~100)，
接著輸入該張圖像的寬度(必為2的非負整數次方)

輸出說明：
輸出該張圖像中黑色方格的座標位置
輸出座標順序由左而右、由上到下，且最左上方格設為0,0，
如該張圖像無黑色方格則輸出all white
=================
範例輸入說明：
202001010
4

範例輸出說明：
由輸入的DF-expression可推出DF-expression example 3的方陣，
因此由左而右、由上到下輸出黑色方格座標
1,2
2,0
2,1
3,0
3,1
=================
Sample Input 1：
1
1

Sample Output 1：
0,0
=================
Sample Input 2：
1
2

Sample Output 2：
0,0
0,1
1,0
1,1
=================
Sample Input 3：
21001
2

Sample Output 3：
0,0
1,1
=================
Sample Input 4：
0
4

Sample Output 4：
all white
=================
Sample Input 5：
22100120110021011
4

Sample Output 5：
0,0
0,3
1,1
1,2
2,2
3,2
3,3
=================
Sample Input 6：
221010201102110120111
4

Sample Output 6：
0,0
0,3
1,0
1,2
2,0
2,1
2,3
3,1
3,2
3,3
=================
Sample Input 7：
22201100020010220001200101102020100120101
8

Sample Output 7：
0,1
1,0
1,5
1,6
2,4
2,5
2,6
2,7
3,2
3,4
3,5
3,6
3,7
4,7
6,4
6,5
6,7
7,4
7,5
7,7
=================
Sample Input 8：
2220100000200020001200200100200021000
8

Sample Output 8：
0,1
3,7
6,6
7,0
=================
Sample Input 9：
2020220110021000210102102000112200010002000220001000222000100102200102001021000210000
16

Sample Output 9：
0,13
1,12
2,12
2,14
3,14
4,8
4,9
5,8
5,9
5,13
6,10
6,11
7,9
7,10
7,11
9,9
10,10
10,11
11,10
11,11
13,5
13,8
13,10
14,8
14,10
=================
Sample Input 10：
2020021000021002200010000
16

Sample Output 10：
4,8
4,9
5,8
5,9
8,0
8,1
8,2
8,3
9,0
9,1
9,2
9,3
10,0
10,1
10,2
10,3
11,0
11,1
11,2
11,3
13,5

:::

# 20 擲骰子遊戲
:::spoiler

020 擲骰子遊戲

十八骰子是一種常見的擲骰子遊戲，用四顆骰子計點。
四顆一開始都是點數 1 朝上，點數 4 朝向玩家，點數 2 朝右，
骰子擺放示意圖如連結所示 (https://imgur.com/Ntds1Ri)，
骰子展開如連結所示 (https://imgur.com/xEVHA5h)。
=================
接下來 N 次修改操作，每次操作包含四個整數代表依序針對四個骰子操作。
輸入整數之操作意義如下：
1表示向前滾一次。(往玩家視角的前方滾動)
2表示向後滾一次。(往玩家視角的後方滾動)
3表示向右滾一次。
4表示向左滾一次。
註：以上修改操作，皆只針對骰子做操作，並不會改變玩家的視角方向

操作完成後輸出得分，計點方式如下：
1. 若四顆點數均相同，稱一色，計18分，例如6, 6, 6, 6 或 3, 3, 3, 3。
2. 若四顆點數均不同；或有三顆點數相同，一顆不同，計 0分，例如 1, 2, 3, 4 或 2, 2, 2, 6。
3. 若兩顆點數相同，另兩顆點數也相同，但兩組兩顆點數不同，則得分計算為：加總兩顆較大點數，例如 2, 2, 5, 5，加總兩顆較大點數為 5+5=10分。
4. 若兩顆點數相同，另兩顆點數不同，則得分計算為加總兩顆不同點數，例如 2, 2, 4, 5，加總兩顆不同點數為 4+5=9分。
註：骰子點數以操作後最終朝上的那面點數為準
=================
輸入說明：
先輸入一個自然數N代表接下來有N次修改操作，
接著輸入N行修改操作，每行皆由4個1~4的數字組成，數字間以空格區隔

輸出說明：
輸出骰子最終的得分
=================
範例輸入說明：
2
1 4 3 2
4 2 1 3

範例輸出說明：
第一次操作後4顆骰子朝上的那面分別是4253
第二次操作後4顆骰子朝上的那面分別是2345
由於最終點數皆不同，因此得分為0並輸出
=================
Sample Input 1：
0

Sample Output 1：
18
=================
Sample Input 2：
1
4 3 1 2

Sample Output 2：
0
=================
Sample Input 3：
1
3 3 3 3

Sample Output 3：
18
=================
Sample Input 4：
2
1 3 4 2
2 4 3 1

Sample Output 4：
18
=================
Sample Input 5：
2
3 2 4 1
1 4 1 4

Sample Output 5：
8
=================
Sample Input 6：
2
1 1 2 3
3 1 2 4

Sample Output 6：
6
=================
Sample Input 7：
2
4 1 2 4
3 1 2 4

Sample Output 7：
0
=================
Sample Input 8：
3
2 3 3 1
4 3 1 2
1 3 2 4

Sample Output 8：
6
=================
Sample Input 9：
3
1 4 2 3
1 3 1 3
2 2 4 1

Sample Output 9：
5
=================
Sample Input 10：
5
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4

Sample Output 10：
0
=================
Sample Input 11：
10
4 2 2 1
4 2 2 4
1 2 3 4
2 2 3 2
3 2 1 2
3 4 4 2
3 3 1 3
1 4 1 1
4 1 4 2
1 1 4 4

Sample Output 11：
8

:::

# 21 互補字串
:::spoiler

21. 互補字串
互補字S1, S2的定義是字串S1, S2沒有重複出現的字，且字串S1, S2內的字需包含在字串S內的字。

此處的字串是英文字的一個集合，亦即元素即使重複也只算一個，也不管排列情況。
例如"Happy Happy Day"與"Day Happy Day"是相同的字串。

給予字串S，以及輸入的n個字串，
請輸出這n個字串互補的個數。
----------------
輸入說明 :
第一行，字串S
第二行，輸入字串個數n
接下來n行，每行輸入一個字串
----------------
輸出說明 :
互補字串的個數

=================
範例輸入說明：
happy birthday to you (字串S)
4 (接下來會輸入n個字串)
happy to you
birthday birthday
to you
happy birthday

範例輸出說明：
2

happy to you 跟 birthday birthday 是互補字串 (S1跟S2的字沒有重複，且S內的字恰好都被S1, S2所包含)
happy to you 跟 to you 不是互補字串 (to you 重複)
happy to you 跟 happy birthday 不是互補字串 (happy重複)
birthday birthday 跟 to you 不是互補字串 (S1跟S2的字雖然沒重複，但S中的happy沒有在S1或S2中)
birthday birthday 跟 happy birthday 不是互補字串 (birthday重複)
to you 跟 happy birthday 是互補字串 (S1跟S2的字沒有重複，且S內的字恰好都被S1, S2所包含)
有兩個互補字串，因此輸出2
=================

Sample Input 1:
happy birthday to you
4
happy to you
birthday birthday
to you
happy birthday

Sample Output 1:
2

=================

Sample Input 2:
red blue green yellow black white
2
red blue green
white yellow black

Sample Output 2:
1

=================

Sample Input 3:
what are you doing
3
what what are
doing doing
what are are you you

Sample Output 3:
1

=================

Sample Input 4:
what are you doing
4
what what are you
you
doing
what are you doing

Sample Output 4:
1

=================

Sample Input 5:
GOOGLE APPLE IBM MICROSOFT AMAZON
5
APPLE IBM GOOGLE
GOOGLE MICROSOFT AMAZON
APPLE GOOGLE MICROSOFT AMAZON
GOOGLE IBM IBM GOOGLE
AMAZON AMAZON APPLE GOOGLE

Sample Output 5:
0

=================

Sample Input 6:
APPLE BANANA BANANA APPLE
5
APPLE BANANA APPLE BANANA APPLE
APPLE APPLE APPLE
APPLE BANANA
BANANA BANANA
APPLE BANANA BANANA APPLE

Sample Output 6:
1

=================

Sample Input 7:
pencil pen eraser ruler
6
pencil pen
eraser ruler
pencil eraser ruler
pen
pencil
ruler eraser pen

Sample Output 7:
3

=================

:::
# 22 英文字取代、插入、刪除、分析
:::spoiler

22. 英文字取代、插入、刪除、分析

輸入一篇英文文章 A，文章中英文字以一個空白間隔。另外輸入 2 個英文字(word) P、Q。
然後執行下面四種操作：
(1) 將文章 A 中 P 字串以 Q 字串取代，並輸出。
(2) 在文章 A 中 P 字串前插入 Q 字串，並輸出。
(3) 將文章 A 中 P 字串刪除，並輸出。
(4) 分析文章 A 所有英文字 (word) 的頻率，依頻率由大自小排序，頻率相同則以 word由小自大排序輸出。

備註:
word是區分大小寫的，如 "The"跟”the”是兩個不同的word。

word排序規則
1. 長度短的在前
2. 如果長度一樣，則依照ASCII編碼排序，編碼小的在前
如:
a → is、That → that 、as → bot、That → This
a → as → is → bot → That → This → that

----------------
輸入說明 :
第一行，文章 A
第二行，英文字 P
第三行，英文字 Q

文章A只會出現大小寫英文字母與空白
英文字P、Q只會出現大小寫英文字母
----------------
輸出說明 :
第一行，輸出將文章 A 中的 P 字串以 Q 字串取代之結果
第二行，輸出在文章 A 中的 P 字串前插入 Q 字串之結果
第三行，輸出將文章 A 中的 P 字串刪除之結果
第四行，輸出文章A中，所有英文字(word)以及出現的頻率，中間以空格做間隔。
輸出順序依頻率由大自小排序，若頻率相同，則以word由小自大排序。

=================
範例輸入說明：
This is a book That is a cook (文章A)
is (word P)
was (word Q)

範例輸出說明：
This was a book That was a cook (用was取代is)
This was is a book That was is a cook (在is前面插入was)
This a book That a cook (刪除is)
a 2 (a 出現2次，且a長度比is小，所以a在is前面)
is 2 (is 出現2次，出現次數比That、This、book、cook多)
That 1 (That出現1次，且That中a的ASCII較This中的i的ASCII小，所以That在This前面)
This 1 (This出現1次，且T的ASCII較b的ASCII小，所以This在book前面)
book 1 (book出現1次，且book中b的ASCII較cook中的c的ASCII小，所以book在cook前面)
cook 1
=================

Sample Input 1:
This is a book That is a cook
is
was

Sample Output 1:
This was a book That was a cook
This was is a book That was is a cook
This a book That a cook
a 2
is 2
That 1
This 1
book 1
cook 1

---------------------

Sample Input 2:
This is a pen That is a banana
apple
banana

Sample Output 2:
This is a pen That is a banana
This is a pen That is a banana
This is a pen That is a banana
a 2
is 2
pen 1
That 1
This 1
banana 1

---------------------

Sample Input 3:
The book is so funny
book
comic

Sample Output 3:
The comic is so funny
The comic book is so funny
The is so funny
is 1
so 1
The 1
book 1
funny 1

---------------------

Sample Input 4:
The book is so funny and the comic is so funny too
funny
boring

Sample Output 4:
The book is so boring and the comic is so boring too
The book is so boring funny and the comic is so boring funny too
The book is so and the comic is so too
is 2
so 2
funny 2
The 1
and 1
the 1
too 1
book 1
comic 1

---------------------

Sample Input 5:
Do you do do you a something do nothing
do
can

Sample Output 5:
Do you can can you a something can nothing
Do you can do can do you a something can do nothing
Do you you a something nothing
do 3
you 2
a 1
Do 1
nothing 1
something 1

---------------------

Sample Input 6:
to be or not to be
to
do

Sample Output 6:
do be or not do be
do to be or not do to be
be or not be
be 2
to 2
or 1
not 1

---------------------

Sample Input 7:
to be or not to be
be
apple

Sample Output 7:
to apple or not to apple
to apple be or not to apple be
to or not to
be 2
to 2
or 1
not 1

---------------------

Sample Input 8:
banana banana yellow ban banana
banana
banana

Sample Output 8:
banana banana yellow ban banana
banana banana banana banana yellow ban banana banana
yellow ban
banana 3
ban 1
yellow 1

---------------------

Sample Input 9:
apple apple apple apple apple
apple
apple

Sample Output 9:
apple apple apple apple apple
apple apple apple apple apple apple apple apple apple apple

apple 5

---------------------

Sample Input 10:
Vestibulum fermentum nulla ex eget ipsum eu ex ultricies placerat Sed sed ex vel erat eleifend euismoexd exu ext est
ex
exe

Sample Output 10:
Vestibulum fermentum nulla exe eget ipsum eu exe ultricies placerat Sed sed exe vel erat eleifend euismoexd exu ext est
Vestibulum fermentum nulla exe ex eget ipsum eu exe ex ultricies placerat Sed sed exe ex vel erat eleifend euismoexd exu ext est
Vestibulum fermentum nulla eget ipsum eu ultricies placerat Sed sed vel erat eleifend euismoexd exu ext est
ex 3
eu 1
Sed 1
est 1
ext 1
exu 1
sed 1
vel 1
eget 1
erat 1
ipsum 1
nulla 1
eleifend 1
placerat 1
euismoexd 1
fermentum 1
ultricies 1
Vestibulum 1

---------------------

:::
# 23 魔術方塊
:::spoiler

023 魔術方塊

魔術方塊有六面，一開始白色朝自己，藍色朝上，紅色朝右
立體示意圖如連結所示(https://ppt.cc/fbhoyx)，
展開示意圖如連結所示(https://ppt.cc/fL3N7x)

顏色編號，1: 藍色，2: 紅色，3: 黃色，4: 白色，5: 橘色，6:綠色。

接下來 M 次修改操作，每次操作包含一個整數 a，意義為：
10 表示直欄(column)最左邊向前轉一次。
11 表示直欄(column)中間向前轉一次。
12 表示直欄(column)最右邊向前轉一次。
20 表示橫列(row)最上面向左轉一次。
21 表示橫列(row)中間向左轉一次。
22 表示橫列(row)最下面向左轉一次。
註：以上修改操作，皆不會轉動魔術方塊的本體，只會針對欄或列做操作
=================
輸入說明：
先輸入M代表接下來有幾次修改操作
接著輸入M行整數視為修改操作，操作整數意義詳見上表

輸出說明：
經過M次修改操作且皆完成後，輸出朝上9格的顏色編號。
=================
範例輸入說明：
3 接下來會有3次修改操作
10 表示直欄(column)最左邊向前轉一次
20 表示橫列(row)最上面向左轉一次
10 表示直欄(column)最左邊向前轉一次

初始狀態示意圖 https://ppt.cc/fJIkcx
10操作後狀態示意圖 https://ppt.cc/fd5yMx
20操作後狀態示意圖 https://ppt.cc/fuUEFx
10操作後狀態示意圖 https://ppt.cc/fHWg9x

範例輸出說明：
2 4 4
6 1 1
6 1 1
註：row的數字間以一個空格區隔
=================
Sample Input 1：
1
10

Sample Output 1：
4 1 1
4 1 1
4 1 1

=================
Sample Input 2：
1
21

Sample Output 2：
1 1 1
1 1 1
1 1 1

=================
Sample Input 3：
2
10
12

Sample Output 3：
4 1 4
4 1 4
4 1 4

=================
Sample Input 4：
2
10
20

Sample Output 4：
4 4 4
1 1 1
1 1 1

=================
Sample Input 5：
2
20
10

Sample Output 5：
2 1 1
4 1 1
4 1 1

=================
Sample Input 6：
2
21
22

Sample Output 6：
1 1 1
1 1 1
1 1 1

=================
Sample Input 7：
3
12
12
12

Sample Output 7：
1 1 3
1 1 3
1 1 3

=================
Sample Input 8：
3
10
12
20

Sample Output 8：
4 4 4
1 1 1
4 4 4

=================
Sample Input 9：
3
10
20
12

Sample Output 9：
4 4 2
1 1 4
1 1 4

=================
Sample Input 10：
3
20
12
10

Sample Output 10：
2 1 2
4 1 4
4 1 4

=================
Sample Input 11：
3
20
22
10

Sample Output 11：
2 1 1
4 1 1
2 1 1

=================
Sample Input 12：
3
20
12
22

Sample Output 12：
1 1 2
1 1 4
1 1 4

=================
Sample Input 13：
3
10
22
20

Sample Output 13：
4 4 4
1 1 1
1 1 1

=================
Sample Input 14：
3
21
22
20

Sample Output 14：
1 1 1
1 1 1
1 1 1

:::
# 24 成績換算
:::spoiler

題目: 成績換算

********：必須使用enum定義不同評分制資料型別，使用union定義分數資料型別。***********
一個班級有N位同學(ID)，M門課，每一門課可以設定評分方式。
設定M門課評分制，輸入N位同學M門課成績，根據下表換算，計算每一位同學百分制對照平均成績
印出前三名ID與平均成績，四捨五入到整數。

等第 GPA 百分制區間 百分制對照
A+ 4.3 90-100 95
A 4.0 85-89 87
A- 3.7 80-84 82
B+ 3.3 77-79 78
B 3.0 73-76 75
B- 2.7 70-72 70
C+ 2.3 67-69 68
C 2.0 63-66 65
C- 1.7 60-62 60
F 0 0-59 50

先輸入有幾門課 M
接下來M行，依序設定這M門課的評分方式

----------------
輸入說明 :
第一行，有幾門課 M
接下來M行，依序設定這M門課的評分方式
(等第 = G，GPA = GPA，百分制區間 = S)

M行輸入後，輸入學生數量 N
接下來輸入N組學生資訊

每組學生資訊包括:
第1行: 學生學號
接下來M行: 對應課程的成績
----------------
輸出說明 :
輸出共六行
第一行 平均成績最高的學生的學號
第二行 平均成績最高的學生的平均成績
第三行 平均成績次高的學生的學號
第四行 平均成績次高的學生的平均成績
第五行 平均成績第三高的學生的學號
第六行 平均成績第三的學生的平均成績

備註: 題目至少會有3名學生，且不會出現平均分數相同的學生
=================
範例輸入說明：
Input:
2 (M = 2，有2門課)
G (第一門課使用等第)
GPA (第二門課使用GPA)
5 (N = 有5位學生)
10801 (第1位學生的學號)
A+ (第1位學生，第1門課的成績)
4.3 (第1位學生，第2門課的成績)
10802 (第2位學生的學號)
B+ (第2位學生，第1門課的成績)
4.0 (第2位學生，第2門課的成績)
10803 (第3位學生的學號)
B- (第3位學生，第1門課的成績)
3.3 (第3位學生，第2門課的成績)
10804 (第4位學生的學號)
C (第4位學生，第1門課的成績)
2.3 (第4位學生，第2門課的成績)
10805 (第5位學生的學號)
F (第5位學生，第1門課的成績)
0 (第5位學生，第2門課的成績)

範例輸出說明：
10801 (平均成績最高的學生的學號 = 10801)
95 (10801該學生第一門課A+，第二門課GPA4.3， (95 + 95) / 2 = 95)
10802 (平均成績最高的學生的學號 = 10802)
83 (10802該學生第一門課B+，第二門課GPA4.0， (78 + 87) / 2 = 82.5，四捨五入到整數 83)
10803 (平均成績最高的學生的學號 = 10803)
74 (10803該學生第一門課B-，第二門課GPA3.3， (70 + 78) / 2 = 74)

=================

Sample Input 1:
2
G
GPA
5
10801
A+
4.3
10802
B+
4.0
10803
B-
3.3
10804
C
2.3
10805
F
0

Sample Ouput 1:
10801
95
10802
83
10803
74

=================

Sample Input 2:
2
G
S
5
10801
F
0-59
10802
C
63-66
10803
B
73-76
10804
A
85-89
10805
A+
90-100

Sample Ouput 2:
10805
95
10804
87
10803
75

=================

Sample Input 3:
3
G
S
GPA
5
10801
C+
90-100
2.0
10802
B-
70-72
1.7
10803
B
63-66
3.0
10804
A+
85-89
4.0
10805
F
90-100
0

Sample Ouput 3:
10804
90
10801
76
10803
72

=================

Sample Input 4:
3
GPA
GPA
GPA
6
AB1001
4.3
3.7
3.3
AB1002
4.3
4.3
4.3
AB1003
4.3
1.7
2.0
AB1004
3.7
3.3
3.7
AB1005
0
1.7
2.0
AB1006
4.3
4.0
0

Sample Ouput 4:
AB1002
95
AB1001
85
AB1004
81

=================

Sample Input 5:
3
S
S
G
6
AB1001
73-76
67-69
B+
AB1002
80-84
77-79
C
AB1003
0-59
90-100
A+
AB1004
63-66
60-62
A
AB1005
85-89
77-79
A+
AB1006
0-59
60-62
C

Sample Ouput 5:
AB1005
87
AB1003
80
AB1002
75

=================

Sample Input 6:
1
G
5
10810
F
10811
C
10812
B-
10813
B
10814
A

Sample Ouput 6:
10814
87
10813
75
10812
70

=================

Sample Input 7:
3
G
G
G
4
AB1001
A+
A+
B
AB1002
B-
B+
B+
AB1003
C+
C+
C+
AB1004
A+
A
A+

Sample Ouput 7:
AB1004
92
AB1001
88
AB1002
75

=================

Sample Input 8:
3
S
S
S
4
AB1001
90-100
90-100
73-76
AB1002
70-72
77-79
77-79
AB1003
67-69
67-69
67-69
AB1004
90-100
85-89
90-100

Sample Ouput 8:
AB1004
92
AB1001
88
AB1002
75

:::
# 25 k-交錯字串
:::spoiler

025 - k-交錯字串
===================================================
一個字串如果全由大寫英文字母組成，我們稱為大寫字串；
如果全由小寫字母組成則稱為小寫字串。
字串的長度是它所包含字母的個數，在本題中，字串均由大小寫英文字母組成。
假設k是一個自然數，一個字串被稱為「k-交錯字串」，
如果它是由長度為k的大寫字串與長度為k的小寫字串交錯串接組成。
舉例來說，「StRiNg」是一個 1 -交錯字串,因為它是一個大寫一個小寫交替出現；
而「heLLow」是一個 2 -交錯字串，因為它是兩個小寫接兩個大寫再接兩個小寫。
但不管k是多少，「aBBaaa」、「BaBaBB」、「aaaAAbbCCCC」都不是k-交錯字串。

本題的目標是對於給定k值，在一個輸入字串找出最長一段連續子字串滿足k-交錯字串的要求。
例如k=2且輸入「aBBaaa」，最長的k-交錯字串是「BBaa」，長度為4。
又如k=1且輸入「BaBaBB」，最長的k-交錯字串是「BaBaB」，長度為5。
請注意，滿足條件的子字串可能只包含一段小寫或大寫字母而無交替，也可能不存在滿足條件的子字串。

輸入說明
第一行為 k
第二行為一字串
-------------------------------------------------
輸出說明
輸出在輸入字串中最長的一段連續子字串有滿足k-交錯字串之字串長度
----------------------------------------------------------------------------------

=================
範例輸入 1 說明：
1 (欲求 1-交錯字串)
aBBdaaa (從此字串中，求出最長的一段連續子字串滿足1-交錯字串之字串長度)

範例輸出 1 說明：
2 (子字串中，最長的1-交錯字串: aB 或是 Bd，長度為2)


範例輸入 6 說明：
3 (欲求 3-交錯字串)
dfsjhDGHdasnFGHfdmQYIKH (從此字串中，求出最長的一段連續子字串滿足3-交錯字串之字串長度)

範例輸出 6 說明：
12
(子字串中，最長的3-交錯字串: asnFGHfdmQYI，長度為12)


範例輸入 7 說明：
3 (欲求 3-交錯字串)
DDaasAAbbCC (從此字串中，求出最長的一段連續子字串滿足3-交錯字串之字串長度)

範例輸出 7 說明：
3 (子字串中，最長的3-交錯字串: ass，長度為3)


範例輸入 8 說明：
3 (欲求 3-交錯字串)
DDaaAAbbCC (從此字串中，求出最長的一段連續子字串滿足3-交錯字串之字串長度)

範例輸出 8 說明：
0 (子字串中，沒有3-交錯字串)
=================

Sample Input 1:
1
aBBdaaa

Sample Output 1:
2

=================

Sample Input 2:
1
hdsjfsdh

Sample Output 2:
1

=================

Sample Input 3:
2
ABcdZXywQUqtTV

Sample Output 3:
14

=================

Sample Input 4:
2
ABCdEfGJIj


Sample Output 4:
2

=================

Sample Input 5:
2
AbCdE

Sample Output 5:
0

=================

Sample Input 6:
3
dfsjhDGHdasnFGHfdmQYIKH

Sample Output 6:
12

=================

Sample Input 7:
3
DDaasAAbbCC

Sample Output 7:
3

=================

Sample Input 8:
3
DDaaAAbbCC

Sample Output 8:
0

=================

Sample Input 9:
4
aabbbbCCCC

Sample Output 9:
8

=================

Sample Input 10:
4
ABCDEFGHI

Sample Output 10:
4

=================

Sample Input 11:
4
XYZ

Sample Output 11:
0

:::
# 26 計算面積
:::spoiler

026 - 計算面積 (積分)

使用切割面積加總法公式(將函式切成N個梯形)，

計算函式f(x)從f(p)到f(q)之間的面積， x 值從區間起始 p 到區間終點 q

f1(x) =((a-x^2))^(1/2) ; f2(x) = (ax^3 + 7x)/(a+x)^(1/2), a 為常數(可能有小數)。

選定這兩個函數之一，使用梯形法來估計從x=p到x=q的面積

梯形面積公式如下，若一個函數圖形切成n塊，則梯形法的估計為:

A(n) = ((q-p)/2n)[f(p)+2f(p+x)+2f(p+2x)+...+2f(q-x)+f(q)]，其中x = (q-p) / n

初始設定 n=1，每次不符合所期待的精確度err時，n*2( n=n*2 )，並重新估計面積。

err為精確小數位數，例如 err=6，即 "目前"與"上一次"，這兩次切割，

計算出的面積值的差小於 10 的負6次方，亦即小於 0.000001。

當計算出的面積值的差小於 10的負err次方時，輸出目前的估計面積。

請注意，計算過程中面積請記得取絕對值


輸入說明：
此題測試資料為連續輸入一至多筆資料 (有可能一次輸入包含多組測資)。

第一行輸入數字1或2，輸入 1 代表計算 f1(x) 面積，輸入 2 代表計算 f2(x)面積，
接著依序輸入 a, p, q, err，到此為一組輸入。
接下來
若輸入0，則結束輸入並結束程式
若輸入1，則代表計算f1(x)面積，且接下來重新輸入a, p, q, err，進行新一輪計算
若輸入2，則代表計算f2(x)面積，且接下來重新輸入a, p, q, err，進行新一輪計算


輸出說明：
根據每一組輸入，輸出目前的估計面積
答案需輸出到小數點第12位

備註：本題之浮點數請使用double
公式內2f(p+x)+2f(p+2x)+...+2f(q-x)，裡面個別項目的*2，請使用乘法而非加法，
如: 2f(p+x)，請使用2 * f(p+x)，而非f(p+x) + f(p+x)
可參考上課講義page.394
推薦同學使用指向函數的指標練習本題

=================

Sample Input 1:
1
4
-2
1
9
0

Sample Output 1:
5.054815608319

=================

Sample Input 2:
2
1
0
3
9
0

Sample Output 2:
29.752380952687

=================

Sample Input 3:
1
55
-6
4
9
2
0.2
0
5
8
0

Sample Output 3:
67.152011942032
65.331732302359

=================

Sample Input 4:
2
4
-1
5
6
1
12.3
-1
1
4
0

Sample Output 4:
257.089598859209
6.918020609884

=================

Sample Input 5:
1
100
-10
10
6
1
100
-1
8
8
0

Sample Output 5:
157.079632241407
80.348069141438

=================

Sample Input 6:
2
2
-1
1
9
2
3
-2
2
9
0

Sample Output 6:
5.973826122479
33.855886871686

=================

Sample Input 7:
1
1.5
-1
1
4
2
2.14
-1
2
4
2
2.34
3
4
3
0

Sample Output 7:
2.140067322512
15.384214084536
52.274082846130

:::
# 27 專案時程
:::spoiler

27 - 專案時程
*此題須使用struct實作，否則不予計分。
(使用struct進行實作並通過所有測資才予以給分，期末會進行檢查)

開發專案時，
專案會被分割為許多項目，分配給多組程式設計師開發。
但這些項目是有順序關係，只有當順序在前的項目完成，才能開始開發順序在後的項目。
用一個有向無環圖，表示這些開發順序。
每個節點代表一個項目，節點內的數字為節點編號， 上方所列數字代表開發這個項目所需天數；
邊表示開發順序。
以下方敘述為例，只有在節點2完成後，才能開始節點4的開發。
同理，只有在節點3與節點4都完成後，才能開始節點5的開發。
一軟體公司的專案準備開始開發，你是公司專案經理，根據開發流程圖，
老闆想知道專案要多久才能完成。

------------------------------------------------------------------

例子 :
節點1→6天
節點2→5天
節點3→11天
節點4→4天
節點5→8天

節點1→節點2→節點4→節點5
↓
節點3______________↗

備註: 本題可參考上課講義page.463，有較清楚的圖

------------------------------------------------------------------

輸入說明 :
第一行是整數，代表後續測試資料組數。
每組測試資料代表專案有向圖。
每組測試資料的第一行是正整數N，代表專案共有 N 個工作事項(節點)，N<=100。
接下來N 行測試資料，每一行依序代表一個項目節點(從第1個節點開始)，
第一個正整數表示完成這個項目所需天數，
第二個正整數 K 表示這個節點有K 條指向其他節點的邊，
接下來K 個正整數表示所指向的項目節點編號。

輸出說明 :
完成所有工作事項所需要的時間 (參考下方說明)

---------------------------------------------------------------------------

範例輸入1 說明:
2 共有兩組專案測試資料
2 第一組專案有兩個工作項目（節點）
8 1 2 第一個工作項目需8天完成，有一個工作項目(第二個工作項目)需等第一個工作項目完成後才能進行。
2 0 第二個工作項目需要2天才能完成
5 第二組專案有五個工作項目（節點）
6 2 2 3 第一個工作項目需6天才能完成，有兩個工作項目（第二、三個工作項目）需等第一個工作項目完成後才能進行。
5 1 4 第二個工作項目需要5天才能完成，有一個工作項目（第四個工作項目）需等第二個工作項目完成後才能進行。
11 1 5 第三個工作項目需要11天才能完成，有一個工作項目（第五個工作項目）需等第三個工作項目完成後才能進行。
4 1 5 第四個工作項目需要4天才能完成，有一個工作項目（第五個工作項目）需等第四個工作項目完成後才能進行。
8 0 第五個工作項目需要8天才能完成

範例輸出1 說明:
10 第二個工作項目需要等第一個工作項目完成，8+2=10。
25 第五個工作項目需要等第三、第四個工作項目完成，完成第三個工作項目需要6+11天，完成第四個工作項目需要6+5+4天，所以第五個工作項目需要6+11+8=25。

---------------------------------------------------------------------------

範例測資6 說明:
該組測資有20個工作項目，但這20個工作項目均可以同時進行，當這20個工作項目中，所需時間最長的工作項目完成後，即可宣告專案完成，因此輸出為時間最長的39天。

---------------------------------------------------------------------------

Sample Input 1:
2
2
8 1 2
2 0
5
6 2 2 3
5 1 4
11 1 5
4 1 5
8 0

Sample Output 1:
10
25

---------------------------------------------------------------------------

Sample Input 2:
1
11
1 2 2 4
2 1 3
3 2 4 5
4 1 5
5 1 6
6 3 7 8 9
7 2 8 10
8 2 9 10
9 1 11
10 1 11
11 0

Sample Output 2:
57

---------------------------------------------------------------------------

Sample Input 3:
1
9
1 1 2
6 2 3 4
5 2 4 5
11 1 6
4 1 6
8 2 7 9
9 1 8
1 1 9
10 0

Sample Output 3:
51

---------------------------------------------------------------------------

Sample Input 4:
1
100
1 1 2
2 1 3
3 1 4
4 1 5
5 1 6
6 1 7
7 1 8
8 1 9
9 1 10
10 1 11
11 1 12
12 1 13
13 1 14
14 1 15
15 1 16
16 1 17
17 1 18
18 1 19
19 1 20
20 1 21
21 1 22
22 1 23
23 1 24
24 1 25
25 1 26
26 1 27
27 1 28
28 1 29
29 1 30
30 1 31
31 1 32
32 1 33
33 1 34
34 1 35
35 1 36
36 1 37
37 1 38
38 1 39
39 1 40
40 1 41
41 1 42
42 1 43
43 1 44
44 1 45
45 1 46
46 1 47
47 1 48
48 1 49
49 1 50
50 1 51
51 1 52
52 1 53
53 1 54
54 1 55
55 1 56
56 1 57
57 1 58
58 1 59
59 1 60
60 1 61
61 1 62
62 1 63
63 1 64
64 1 65
65 1 66
66 1 67
67 1 68
68 1 69
69 1 70
70 1 71
71 1 72
72 1 73
73 1 74
74 1 75
75 1 76
76 1 77
77 1 78
78 1 79
79 1 80
80 1 81
81 1 82
82 1 83
83 1 84
84 1 85
85 1 86
86 1 87
87 1 88
88 1 89
89 1 90
90 1 91
91 1 92
92 1 93
93 1 94
94 1 95
95 1 96
96 1 97
97 1 98
98 1 99
99 1 100
100 0

Sample Output 4:
5050

---------------------------------------------------------------------------

Sample Input 5:
1
8
3 2 2 8
4 2 3 8
5 2 4 8
6 2 5 8
7 2 6 8
8 2 7 8
9 1 8
20 0

Sample Output 5:
62

---------------------------------------------------------------------------

Sample Input 6:
1
20
1 0
3 0
5 0
7 0
9 0
11 0
13 0
15 0
17 0
19 0
21 0
23 0
25 0
27 0
29 0
31 0
33 0
35 0
37 0
39 0

Sample Output 6:
39

---------------------------------------------------------------------------

Sample Input 7:
1
10
1 3 2 3 4
10 1 5
15 1 5
20 1 5
5 3 6 7 8
16 1 9
14 1 9
27 1 9
7 1 10
12 0

Sample Output 7:
72

---------------------------------------------------------------------------

Sample Input 8:
1
7
2 2 2 3
3 1 4
6 1 5
11 2 6 7
9 1 7
10 0
7 0

Sample Output 8:
26

:::

# 28 棒球遊戲
:::spoiler

28 - 棒球遊戲
*此題須使用struct實作，否則不予計分。
(使用struct進行實作並通過所有測資才予以給分，期末會進行檢查)


假設球員打擊情況：
(1) 安打：以 1, 2, 3 和 H 代表一、二、三和全(四)壘打。
(2) 出局：以英文字母 O 表示 (OUT)。
簡化版的規則如下：
(1) 球場上有四個壘包，稱為本壘、一、二和三壘。本壘握球棒稱「擊球員」，在另外三個壘包稱「跑壘員」。
(2) 當擊球員打擊「安打」時， 擊球員與跑壘員可移動；「出局」時，跑壘員不動，擊球員離場換下一位。
(3) 比賽開始由第 1 位打擊，接著 2, 3, 4, 5 位球員。
(4) 打出 K 壘打時，場上球員(擊球員和跑壘員)會前進 K 個壘包。本壘到一壘，接著二、三壘，最後回到本壘。 回到本壘可得 1 分。
(5) 每達到三個出局數時，壘包清空(跑壘員都得離開)， 重新開始。

------------------------------------------------------------------------

輸入格式
(1) 每組測試資料固定有 10 行。
(2) 第 1 到 9 行，依照球員順序， 每 1 行代表 1 位球員的 打擊資訊 。每 1 行開始有 1 個正整數 a (1<=a<=5)，代 表球員總共打 a 次。接下來有 a 個字元，依序代表每 次打擊結果。資料間均以 1 個空白字元隔開。球員打擊資訊不會有錯誤與缺漏。
(3) 第 10 行有 1 個正整數 b (1<=b<=27)，表示要計算當總出局數累計到 b 時，該球隊的得分 。輸入打擊資訊中 至少包含 b 個出局。

輸出格式
(1) 總計第 b 個出局數發生時的總得分。
(2) 依棒次先後順序，輸出九位球員在總計第 b 個出局數發生時的資訊 (第幾棒、安打數、到達本壘次數)

備註 : 到達本壘次數指的是該名跑壘員到達本壘的次數，而非棒球術語中的打點
Ex : 第1棒在2壘、第2棒在1壘，此時第3棒打全壘打，則1、2、3棒的到達本壘次數都個別+1

------------------------------------------------------------------------

範例輸入1說明 :
3 1 O O (第一棒打者，三次打席分別為1壘安打、出局、出局)
3 1 2 1 (第二棒打者，三次打席分別為1壘安打、2壘安打、1壘安打)
3 O O O (第三棒打者，三次打席分別為出局、出局、出局)
3 O O O (第四棒打者，三次打席分別為出局、出局、出局)
3 1 1 3 (第五棒打者，三次打席分別為1壘安打、1壘安打、3壘安打)
3 O O H (第六棒打者，三次打席分別為出局、出局、全壘打)
3 3 1 2 (第七棒打者，三次打席分別為3壘安打、1壘安打、2壘安打)
3 O O 1 (第八棒打者，三次打席分別為出局、出局、1壘安打)
2 O 1 (第九棒打者，兩次打席分別為出局、1壘安打)
13 (第 b 個出局數)

範例輸出1說明 :
0 (第13個出局數發生時，總得分為0)
1 1 0 (第一棒打者，安打數1，到達本壘次數0)
2 3 0 (第二棒打者，安打數3，到達本壘次數0)
3 0 0 (第三棒打者，安打數0，到達本壘次數0)
4 0 0 (第四棒打者，安打數0，到達本壘次數0)
5 2 0 (第五棒打者，安打數2，到達本壘次數0)
6 0 0 (第六棒打者，安打數0，到達本壘次數0)
7 2 0 (第七棒打者，安打數2，到達本壘次數0)
8 0 0 (第八棒打者，安打數0，到達本壘次數0)
9 1 0 (第九棒打者，安打數1，到達本壘次數0)

------------------------------------------------------------------------


Sample Input 1:
3 1 O O
3 1 2 1
3 O O O
3 O O O
3 1 1 3
3 O O H
3 3 1 2
3 O O 1
2 O 1
13

Sample Output 1:
0
1 1 0
2 3 0
3 0 0
4 0 0
5 2 0
6 0 0
7 2 0
8 0 0
9 1 0

------------------------------------------------------------------------

Sample Input 2:
4 O 2 1 O
3 1 1 O
3 O O 2
3 2 1 3
3 H H 3
3 3 H O
3 O O 2
3 O 1 2
3 O 1 H
10

Sample Output 2:
14
1 2 1
2 2 1
3 1 1
4 3 3
5 3 2
6 2 1
7 1 1
8 2 2
9 2 2

------------------------------------------------------------------------

Sample Input 3:
5 1 O O 3 1
5 O O 1 O O
5 2 O 1 1 O
5 O O O O O
5 O 3 O O O
5 O O O O 1
5 1 O O O 1
5 3 O O 3 1
5 1 H 2 3 O
27

Sample Output 3:
6
1 3 0
2 1 0
3 3 0
4 0 0
5 1 0
6 1 0
7 2 1
8 3 2
9 4 3

------------------------------------------------------------------------

Sample Input 4:
5 3 O O 1 O
5 3 3 1 1 1
5 2 1 1 1 2
5 1 1 1 2 1
5 2 O 1 1 1
5 3 2 1 O O
5 2 O O O O
5 1 O 2 O O
4 3 H H 1
10

Sample Output 4:
19
1 2 2
2 4 4
3 4 4
4 4 1
5 3 1
6 3 1
7 1 1
8 2 2
9 4 3

:::
# 29 工作排程
:::spoiler

29 - 工作排程

有M個工作要在N台機器上加工，每個工作i包含若干個工序Oij，
這些工序須依序加工，也就是前一道工序Oi(j-1)完成後才可開始下一道工序Oij。
每道工序oij可用一個有序對(kij,tij)表示它需在機器kij上面花費tij小時完成。
每台機器一次只能處理一道工序。
所謂一道工序Oij的「最早完成時間的cij*｣是指考慮目前排程中機器kij之可用性
以及前一道工序Oi(j-1)(若該工序存在)之完成時間後可得的最早完成時間。
工廠經理安排所有工廠經理安排所有工序的排程規則如下：

針對每一個工作的第一個尚未排程的工序，計算出此工序的「最早完成時間｣，
然後挑選出最早完成時間最小的工序納入排程，如果有多個完成時間都是最小，
則挑選其中工作編號最小之工序。
一個工序一旦納入排程就不會再更改，重複以上步驟直到所有工序皆納入排程。

------------------------------------------------------------------------
for example :

工作1(以○代表) o11 = (2, 4) o12 = (1, 1)
此工作有兩道工序，第一道需要在機器2執行4小時， 第二道需要在機器1執行1小時。

工作2(以■代表) o21 = (0, 2) o22 = (2, 2) o23 = (0, 1)
有三道工序，第一道需要在機器0執行2小時，餘類推。

工作3(以●代表) o31 = (0, 7) 有一道工序需要在機器0執行7小時。

排程過說明如下:
1. 在開始時，每個工作都是考慮第一道工序，
三個工作第1道工序需要的時間分別是 t11 = 4、t21 = 2、t31 = 7，
這也是它們的最早完成時間， 也就是c11=4、c21=2、c31=7，
因此會先排o21。
====================================
機器0→■■□□□□□□□□□□□□--------------工作一○
機器1→□□□□□□□□□□□□□□--------------工作二■
機器2→□□□□□□□□□□□□□□--------------工作三●
====================================

2. 接下來， 三個工作要考慮的順序分別是第1、2、1個工序，即 o11、o22和o31。
–(1) o11 需要機器2執行4小時，而機器 2可以開始加工的時間點是0；o11沒有前一道工序。
------因此，這工序可以開始的時間 是 max(0, 0) = 0。是故，其最早完成時間 c11= max(0,0)+ 4 = 4。
–(2) o22 需機器2執行2小時，而機器2可開始加工時間點是0；
------o22前一道工序o21完成時間是2。因此，這工序可以開始的時 間是max(0, 2) = 2。
------最早完成時間 c22=max(0,2)+2= 4。
–(3) o31 需機器0執行 7小時，而機器0可開始加工的時間點是 2；
------o31沒有前一道工序。因此，這工序可開始的時間是max(2, 0) = 2。
------其最早完成時間c31* = max(2, 0) + 7 = 9。

因此，由於c11* 和 c22* 都是最小，根據規則，工作編號小的先排，所以會排 o11。
====================================
機器0→■■□□□□□□□□□□□□--------------工作一○
機器1→□□□□□□□□□□□□□□--------------工作二■
機器2→○○○○□□□□□□□□□□--------------工作三●
====================================

3. 三個工作目前要考慮的順序分別第2、2、1個工序。
----依照類似推論，可得到c12 = 5，c22 = 6，c31 = 9，因此排o12。工作1的工序均已排完，所以它的完成時間是5。
4. 剩下工作2與 3。c22 = 6，c31 = 9，因此先排o22。
5. c23=7而c31 = 9，因此排o23，工作2的工序已排完，所以它的完成時間是7。
6. 剩下工作3，因為機器0的下一個可以開始時間是7，o31的完 成時間是7+7=14。

====================================
機器0→■■□□□□■●●●●●●●--------------工作一○
機器1→□□□□○□□□□□□□□□--------------工作二■
機器2→○○○○■■□□□□□□□□--------------工作三●
====================================
三個工作完成時間分別是5、7、14，輸出答案 5+7+14=26。

備註: 可參考上課講義page.456~page.461，有較清楚的圖

------------------------------------------------------------------------

輸入格式
第一行有兩個整數N與 M，代表N台機器與M個工作 ，
接下 來有M個工作資訊 ， 輸入順序即是工作編號順序。
每個工作資訊包含兩行，第一是整數P，代表到工序數量；
第二行是 2*P個整數 ，每兩個一組依序代表一道工序的機器編號與需求時間。
機器的編號由0開始 。參數N、M、P 以及每個工序的需求時間都是不超過100的正整數。

輸出格式
輸出每個"工作"的完成時間的總和 。

------------------------------------------------------------------------

Sample Input 1 :
3 3
2
2 4 1 1
3
0 2 2 2 0 1
1
0 7

Sample Output 1 :
26

------------------------------------------------------------------------

Sample Input 2 :
2 3
1
0 4
1
1 5
1
1 3

Sample Output 2:
15

------------------------------------------------------------------------

Sample Input 3 :
4 4
3
0 4 1 8 3 5
4
0 2 0 3 2 4 3 1
1
0 9
2
2 3 3 3

Sample Output 3:
56

------------------------------------------------------------------------

Sample Input 4 :
5 5
2
0 1 1 2
2
2 3 3 4
2
0 3 4 5
2
0 1 1 1
2
1 1 2 2

Sample Output 4:
29

------------------------------------------------------------------------

Sample Input 5 :
3 2
10
0 2 1 3 2 4 0 5 1 6 2 7 0 8 1 9 2 10 0 11
10
2 3 1 1 0 2 2 4 1 1 0 5 2 6 1 4 0 3 1 10

Sample Output 5:
119

------------------------------------------------------------------------

Sample Input 6 :
1 5
3
0 2 0 4 0 6
10
0 2 0 5 0 7 0 9 0 10 0 9 0 7 0 5 0 12 0 7
1
0 30
2
0 14 0 36
5
0 17 0 23 0 7 0 3 0 5

Sample Output 6:
662

:::
# 30 圖形周長與面積
:::spoiler

30 - 圖形周長與面積
*此題須使用以下struct及function pointer實作，否則不予計分。
(使用規定架構進行實作並通過所有測資才予以給分，期末會進行檢查)

利用結構 struct 定義
Shape（圖形）, Circle（圓）, Rectangle（矩形）, Square（正方形）, Triangle（三角形）。

圓有半徑，矩形有長和寬，正方形有邊長，三角形有三個邊。
計算各個圖形的周長與面積，以及所有圖形的周長加總與面積加總。

------程式碼架構規範之範例---------------------

#define ShapeText(TYPE) char name[10];\
double (*perimeter)(struct TYPE*);\
double (*area)(struct TYPE*)

typedef struct shape_s {
ShapeText(shape_s);
} shape_t;

typedef struct circle_s {
ShapeText(circle_s);
double radius;
} circle_t;

備註: 架構範例可參考上課講義page. 455
--------------------------------------------------------

輸入說明:
第一行輸入N，代表圖形個數
接下來輸入N行，第一個英文字代表圖形種類，然後根據圖形種類輸入其屬性
圖形種類以代號輸入，代號如下所示：
C：圓形，屬性內容具有radius (圓周率請使用3.14)
R：矩形，屬性內容具有length、width
S：正方形，屬性內容具有edge
T：三角形，屬性內容具有3個edge

輸出說明：
前N行，輸出各個圖形的周長與面積
最後一行，輸出圖形的周長總和與面積總和
(四捨五入到小數點後第2位，總和請先加總好再四捨五入)

--------------------------------------------------------

範例輸入1 說明
4 (代表有4個圖形要輸入)
T 2.2 3.3 4.4 (第一個圖形是三角形，輸入其三個邊)
S 1.1 (第二個圖形是正方形，輸入其邊長)
R 1.1 2.2 (第三個圖形是長方形，輸入其長與寬)
C 1.0 (第四個圖形是圓形，輸入其半徑)

範例輸出1 說明
9.90 3.51 (第一個圖形(三角形) 的周長是9.90，面積是3.51)
4.40 1.21 (第二個圖形(正方形) 的周長是4.40，面積是1.21)
6.60 2.42 (第三個圖形(長方形) 的周長是6.60，面積是2.42)
6.28 3.14 (第四個圖形(圓形) 的圓周長是6.28，面積是3.14)
27.18 10.28 (所有圖形的周長加起來是27.18，面積是10.28)

--------------------------------------------------------

Sample Input 1：
4
T 2.2 3.3 4.4
S 1.1
R 1.1 2.2
C 1.0

Sample Output 1：
9.90 3.51
4.40 1.21
6.60 2.42
6.28 3.14
27.18 10.28
``
--------------------------------------------------------

Sample Input 2：
1
C 0.31847

Sample Output 2：
2.00 0.32
2.00 0.32

--------------------------------------------------------

Sample Input 3：
3
C 3.14159
S 3.14159
T 3.59737 1.56248 2.169984

Sample Output 3：
19.73 30.99
12.57 9.87
7.33 0.88
39.63 41.74

--------------------------------------------------------

Sample Input 4：
2
R 3.98 6.77
S 3.14

Sample Output 4：
21.50 26.94
12.56 9.86
34.06 36.80

--------------------------------------------------------

Sample Input 5：
5
C 3.335
C 3.984
S 315.27
R 4.57 3.18
T 100.5 200 300

Sample Output 5：
20.94 34.92
25.02 49.84
1261.08 99395.17
15.50 14.53
600.50 1226.02
1923.04 100720.49

:::
# 31 邏輯電路圖
:::spoiler

31 - 邏輯電路圖
* 本題必須使用題目所附之程式碼架構
(參考規定架構進行實作並通過所有測資才予以給分，期末會進行檢查)

同學可以對範例架構程式碼做修改來撰寫本題，但需符合以下三點
1. #define中須定義函數指標 (函數的參數可自行決定)
2. 有定義struct，且當中有使用到第一點的define
3. 使用struct的函數指標進行本題的實作
若同學對自己的code是否符合本題架構有疑問，可以詢問助教


　　　　　　　 O1
I1 ----->A　　 ↑
　　　 A------------>B---★----D　O2
I2 ----->A　|　　　　　 D ↑
　　　　　--------->C 　 D---★—>F　　O3
　　　　　　　　 C------->D　　　 F　　↑
I3 --------------------->C　|　 　　 F-----★
　　　　　　　　　　 --->E　　　 F
I4-------------------------------->E--------->F

可參考以下連結
https://ppt.cc/fMTCBx@.png

以上邏輯電路圖，
輸入為 I1, I2, I3, I4，以及設定A、B、C、D、E、F六個邏輯閘。
輸出為 O1, O2, O3

A、B、C、D、E、F可被設定成5種邏輯閘，分別是
雙輸入單輸出的AND, OR與XOR
以及
單輸入單輸出的NOT 與 Empty。

如上圖所示，
B邏輯閘為單輸入單輸出邏輯閘，因此可被設定成 NOT 或 Empty。
A, C, D, E, F邏輯閘為雙輸入單輸出邏輯閘，因此可被設定成 AND, OR 與 XOR。

------程式碼架構規範之範例---------------------

#include
#include
#define GATEVALUE(TYPE) int(*GateValue)(void)
typedef struct _Gate{
GATEVALUE();
}Gate;
int GateGetValue(){return 0;}
typedef struct _GateAnd{
GATEVALUE();
}GateAnd;
int GateAndValue(){return 1;}
void CreateGate(Gate *obj){
obj->GateValue = GateGetValue;
}
void CreateGateAND(GateAnd *obj){
obj->GateValue = GateAndValue;
}
int main(int argc, char *argv[]){
Gate gate;
CreateGate(&gate);
GateAnd and;
CreateGateAND(&and);
printf("Gate = %d, GateAND = %d\n", gate.GateValue(), and.GateValue());
return 0;
}

此範例可以參考上課講義page.451
-------------------------------------------------------

輸入說明:
第一行依序輸入I1, I2, I3, I4為 0 或 1，中間以逗號間隔。
第二行依序輸入A, B, C, D, E, F邏輯閘的設定，可輸入的邏輯閘種類代號如下所示：
A：AND Gate
O：OR Gate
X：XOR Gate
N：NOT Gate
E：Empty Gate

輸出說明:
輸出O1, O2, O3為 0 或 1，中間以逗號間隔
輸出順序：O1,O2,O3

-------------------------------------------------------

範例輸入1 說明:
0,0,0,0 (i1, i2, i3, i4皆為0)
X,N,O,X,A,A (A邏輯閘為XOR，B邏輯閘為NOT，C邏輯閘為OR，D邏輯閘為XOR，E、F邏輯閘為AND)

範例輸出1 說明:
1,1,0 (O1為1，O2為1，O3為0)

可參考以下連結
https://ppt.cc/fYjvKx@.png
-------------------------------------------------------

Sample Input 1:
0,0,0,0
X,N,O,X,A,A

Sample Output 1:
1,1,0

-------------------------------------------------------

Sample Input 2:
1,0,1,1
A,E,A,A,X,O

Sample Output 2:
0,0,1

-------------------------------------------------------

Sample Input 3:
0,0,1,0
X,N,A,O,X,X

Sample Output 3:
1,1,1

-------------------------------------------------------

Sample Input 4:
0,0,1,1
O,E,X,O,O,A

Sample Output 4:
0,1,1

-------------------------------------------------------

Sample Input 5:
1,0,0,1
X,N,X,X,A,X

Sample Output 5:
0,1,0

:::
# 32 結構排序
:::spoiler

32 - 結構排序
*此題須使用struct實作，否則不予計分。
(使用struct進行實作並通過所有測資才予以給分，期末會進行檢查)

排序是很重要的

本題給予多組資料，希望你可以將資料做由小到大做排序

排序的規則如下：
先以每組資料中的第一個數字排序，
若相同，再比較第二個數字...以此類推。

--------------------------------------------------------

輸入說明:
第一行輸入兩個數字N、M，表示有N組資料，每組資料有M個數字
接下來N行，每行有M個數字

輸出說明：
輸出以組為單位的資料排序後的結果

--------------------------------------------------------

Sample Input 1：
8 3
1 2 3
4 2 9
8 3 1
7 1 5
4 8 2
1 1 1
1 0 1
2 2 2

Sample Output 1：
1 0 1
1 1 1
1 2 3
2 2 2
4 2 9
4 8 2
7 1 5
8 3 1

--------------------------------------------------------

Sample Input 2：
6 4
1 2 3 4
1 2 3 3
1 1 3 4
0 1 3 3
0 1 2 3
0 0 2 3

Sample Output 2：
0 0 2 3
0 1 2 3
0 1 3 3
1 1 3 4
1 2 3 3
1 2 3 4

--------------------------------------------------------

Sample Input 3：
10 2
9 8
8 7
7 6
6 5
5 4
4 3
3 2
2 1
1 0
0 9

Sample Output 3：
0 9
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8

--------------------------------------------------------

Sample Input 4：
3 10
1 2 3 4 5 6 7 8 9 101
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 1001

Sample Output 4：
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 101
1 2 3 4 5 6 7 8 9 1001

--------------------------------------------------------

Sample Input 5：
10 10
9 8 6 4 6 1 5 8 4 3
3 0 7 9 4 6 6 4 6 2
3 4 8 2 4 7 3 0 1 1
8 6 6 7 4 2 2 3 2 3
9 3 3 6 0 4 2 8 2 6
1 3 7 3 3 5 3 0 9 0
2 0 2 4 9 3 3 7 1 0
3 5 6 8 5 7 2 9 7 3
2 7 9 3 2 3 9 1 0 6
4 9 9 9 5 9 1 0 8 9

Sample Output 5：
1 3 7 3 3 5 3 0 9 0
2 0 2 4 9 3 3 7 1 0
2 7 9 3 2 3 9 1 0 6
3 0 7 9 4 6 6 4 6 2
3 4 8 2 4 7 3 0 1 1
3 5 6 8 5 7 2 9 7 3
4 9 9 9 5 9 1 0 8 9
8 6 6 7 4 2 2 3 2 3
9 3 3 6 0 4 2 8 2 6
9 8 6 4 6 1 5 8 4 3

:::
# 33 交通工具
:::spoiler

33 - 交通工具
*此題須使用以下struct及function pointer實作，否則不予計分。
(使用規定架構進行實作並通過所有測資才予以給分，期末會進行檢查)

同學必須使用規定架構定義四種交通工具 (車、腳踏車、長途客運、摩托車)
但可以定義各個交通工具特有的屬性
如在車的結構中定義油錢、過路費、停車費。

題目敘述
BMI博士想從A點移動到B點，中間距離 x 公里，他想要知道在金錢花費限制在 y 元以下的情況，最快抵達B點需要多久的時間，是使用哪種交通工具?


利用結構 struct 定義
Car（車）, Bike（腳踏車）, Intercity Bus（長途客運）, Scooter（摩托車）。

交通工具會有兩個的method需要實作，分別是計算金錢花費以及計算時間花費。


計算費用的方式
車需要考慮油錢、過路費、停車費。
腳踏車需考慮租賃費用。
客運根據站點計費。
摩托車需考慮油錢。

車:
1.油錢:汽油每公升a元。
汽車每100公里需要10公升汽油。
不足100公里以100公里計算 (如250公里，汽車要30公升汽油)
2.過路費: 每100公里 b元
過路費不足100公里以100公里計算 (如250公里，過路費為3b元)
3.停車費: c元

腳踏車:
1.租賃費用:a元

客運:
1.固定費用:a元
2.長途加收:超過100公里，每50公里多b元。
加收部分，不足50公里以50公里計算 (如170公里為a+2b)

摩托車:
1.油錢:汽油每公升a元。
摩托車每100公里需要4公升汽油。
不足100公里以100公里計算 (如250公里，摩托車要12公升汽油)


計算時間的方式

車每小時可以朝目的地移動100公里(100km/hr)
客運每小時可以朝目的地移動75公里(75km/hr)
摩托車每小時可以朝目的地移動50公里(50km/hr)
腳踏車每小時可以朝目的地移動20公里(20km/hr)

------程式碼架構規範之範例---------------------

#define TransportationText(TYPE) char name[20];\
double speed;\
double distance;\
int (*price)(struct TYPE*);\
double (*time)(struct TYPE*)

typedef struct car_s {
int oilPrice;
int parkPrice;
int tolls;
TransportationText(car_s);
} car_t;

int CarPrice(car_t* obj){
}

double CarTime(car_t* obj){
}

void CarCreate(car_t *obj){
strcpy(obj->name, "Car");
obj->speed = 100;
obj->price = CarPrice;
obj->time = CarTime;
}

--------------------------------------------------------

輸入說明:
第一行輸入二正整數x,y，其中x代表起始點與目的地距離x公里，y代表預算
第二行輸入三正整數為汽車相關費用，分別是油價(元/公升)、停車費以及過路費(元/100km)
第三行輸入一正整數為腳踏車的租賃費用
第四行輸入二正整數為長途客運相關費用，分別是固定費用以及長途加收費用(元/50km)
第五行輸入一正整數為摩托車的油價(元/公升)

輸出說明：
輸出符合預算且花費時間最短的交通類型。

第一行輸出交通工具類型(Car,Bike,Intercity Bus,Scooter)。
第二行輸出實際花費金額。
第三行輸出花費時間(以小時計，取到小數點後兩位)。

如果沒有交通工具符合要求，輸出No Transportation (參考範例測資5)

--------------------------------------------------------

範例輸入1 說明
150 1000 (第一行輸入二正整數x,y，其中x代表起始點與目的地距離x公里，y代表預算)
30 100 50 (第二行為汽車的相關費用，輸入油錢(元/公升)、停車費以及過路費(元/100km))
50 (第三行為腳踏車的相關費用，輸入租賃費用)
50 30 (第四行為長途客運的相關費用，輸入固定費用以及長途加收費用(元/50km))
30 (第四行為摩托車的相關費用，輸入油錢(元/公升))

範例輸出1 說明
Car
800
1.50

汽車的費用= 30*10*⌈150/100⌉ + 100 + 50*⌈150/100⌉= 30*10*2 + 100 + 50*2= 800元
汽車所需時間= 150/100= 1.50hr

腳踏車的費用= 50元
腳踏車所需時間= 150/20= 7.50hr

長途客運的費用= 50 + 30*⌈(150-100)/50⌉= 50 + 30*1= 80元
長途客運所需時間= 150/75= 2.00hr

摩托車的費用= 30*4*⌈150/100⌉= 30*4*2= 240元
摩托車所需時間= 150/50= 3.00hr

因為預算為1000元，
所以在預算內，花費時間最短的交通工具為汽車，花費為800元，需要時間為1.5hr。
--------------------------------------------------------

Sample Input 1：
150 1000
30 100 50
50
50 30
30

Sample Output 1：
Car
800
1.50

--------------------------------------------------------

Sample Input 2：
270 800
35 0 0
50
70 30
30

Sample Output 2：
Intercity Bus
190
3.60

--------------------------------------------------------

Sample Input 3：
70 90
27 100 0
50
100 30
20

Sample Output 3：
Scooter
80
1.40

--------------------------------------------------------

Sample Input 4：
480 20
30 50 70
20
70 100
30

Sample Output 4：
Bike
20
24.00

--------------------------------------------------------

Sample Input 5：
100 50
100 200 300
500
90 60
25

Sample Output 5：
No Transportation

:::
# 34 編修字串
:::spoiler

34 - 編修字串

問題描述
本題目為字串處理問題，程式需讀取一行英文字串，並依據讀入相關之指令，
來編修該字串。程式開始執行時，游標位於該英文字串的第一個字元。

編修字串的指令如下：
0 : 移動游標至目前所在行的第一個字元。
$ : 移動游標至字串的結束位置（即最後一個字元的下一個位置）。
x : 刪除目前游標所在位置的字元（如果在字串的結束位置則不做任何動作）。
s : 與游標所在位置的右邊字元做交換動作（如果游標在結束位置或結束位置的前一個位置，則不做任何動作）。
i : 在游標所在位置插入字元。如指令 ‘ix’ ，則是在游標目前所在位置前插入字元‘x’，游標停留在原始的位置（即所插入‘x’ 的下一位置）。
u : 如果游標所在位置之資料為英文字母，則將該字母改為大寫，並將游標往右移一個位置，如不是英文字母，則直接將游標往右移一個位置。
+ : 將游標向右移一個位置。
- : 將游標向左移一個位置。

--------------------------------------------------------

輸入說明:
第一行為要編修的英文字串。
第二行為編修英文字串的指令。

輸出說明:
請輸出處理完畢之字串。

--------------------------------------------------------

範例輸入1 說明:
i have a bell
$is----x---sxs0u+++xxid

第1個指令為 $，將游標移至字串的結束位置。 ( 執行後游標位置的字元為 ‘\0’ )
第2個指令為 i，從輸入拿一字元 s，並在游標位置前插入。( 執行後游標位置的字元為 ‘\0’ )
第3個指令為 -，將游標向左移一個位置。 ( 執行後游標位置的字元為 s )
第4個指令為 -，將游標向左移一個位置。 ( 執行後游標位置的字元為 l )
第5個指令為 -，將游標向左移一個位置。 ( 執行後游標位置的字元為 l )
第6個指令為 -，將游標向左移一個位置。 ( 執行後游標位置的字元為 e )
第7個指令為 x，刪除目前游標所在位置的字元。 ( 執行後游標位置的字元為 l )
第8個指令為 -，將游標向左移一個位置。 ( 執行後游標位置的字元為 b )
第9個指令為 -，將游標向左移一個位置。 ( 執行後游標位置的字元為 空白 )
第10個指令為 -，將游標向左移一個位置。 ( 執行後游標位置的字元為 a )
第11個指令為 s，與游標所在位置的右邊字元做交換動作。 ( 執行後游標位置的字元為 空白 )
第12個指令為 x，刪除目前游標所在位置的字元。 ( 執行後游標位置的字元為 a )
第13個指令為 s，與游標所在位置的右邊字元做交換動作。 ( 執行後游標位置的字元為 b )
第14個指令為 0，將游標移至字串的開始位置。 ( 執行後游標位置的字元為 i )
第15個指令為 u，將游標所在位置的字元改為大寫。 ( 執行後游標位置的字元為 空白 )
第16個指令為 +，將游標向右移一個位置。 ( 執行後游標位置的字元為 h )
第17個指令為 +，將游標向右移一個位置。 ( 執行後游標位置的字元為 a )
第18個指令為 +，將游標向右移一個位置。 ( 執行後游標位置的字元為 v )
第19個指令為 x，刪除目前游標所在位置的字元。 ( 執行後游標位置的字元為 e )
第20個指令為 x，刪除目前游標所在位置的字元。 ( 執行後游標位置的字元為 空白 )
第21個指令為 i，從輸入拿一字元 d，並在游標位置前插入。( 執行後游標位置的字元為 空白 )

範例輸出1 說明:
I had balls

--------------------------------------------------------

Sample Input 2:
hellol, I am a frog.
$-----xxxxipieirisioin0u++xs

Sample Output 2:
Hello, I am a person.

--------------------------------------------------------

Sample Input 3:
Who lives in a pineapple in the sea
xxxiyioiu0u$----------xxiuinidieir$i.

Sample Output 3:
You lives in a pineapple under the sea.

--------------------------------------------------------

Sample Input 4:
he is baosbrnet yellow and porous
xxxxxxsu+s++s++s++$i iiisi ihie

Sample Output 4:
Absorbent yellow and porous is he

--------------------------------------------------------

Sample Input 5:
You N!a!u!t!i!c!a!l! nonsense be you wish it
+++++x+x+x+x+x+x+x+x$-----------i -ig-in-ii-ih-it-ie-im-io-is

Sample Output 5:
You Nautical nonsense be something you wish it

:::
# 35 長浮點數小數運算
:::spoiler

35 - 長浮點數小數運算

以陣列實做長浮點小數的運算，計算並輸出兩數的相加、相減、相乘
輸出的兩個部分長度最大精確各為 60 位

--------------------------------------------------------

輸入說明:
輸入2行，代表兩個浮點小數

輸出說明：
輸出 3 行
第1行為兩數相加之結果
第2行為兩數相減之結果
第3行為兩數相乘之結果

--------------------------------------------------------

Sample Input 1：
54375594968196412353419.7136567768967814548988
73287424855639561252347.4564956732129084076487

Sample Output 1：
127663019823835973605767.1701524501096898625475
-18911829887443148898927.7428388963161269527499 3985047330212387208846838718241110977261606713.61406369102666397315364414705498798400445156

--------------------------------------------------------

Sample Input 2：
-9234507190321346790456789.1931587893642640223756
-9234507190321346790456789.1931587893642640223756

Sample Output 2：
-18469014380642693580913578.3863175787285280447512
0
85276123048096654594016550136815157974048477583569.58751391797434997190616787629405161746747536

--------------------------------------------------------

Sample Input 3：
-26867969463606565474768123.5645144634542221
136452564856366342453.724563547586473564776

Sample Output 3：
-26867833011041709108425669.839950915867748535224
-26868105916171421841110577.289078011040695664776
-3666203345791645284973102086942259202952614005.2383003686028975820993973094750407496

--------------------------------------------------------

Sample Input 4：
19342748593927235.4859695323773685960483721
-939329384736226582829496.04837462845050055

Sample Output 4：
-939329365393477988902260.5624050960731319539516279
939329404078975176756731.5343441608278691460483721 -18169212135841181949695789552712699214732.353525637433292855735431230415598257654655

:::
# 36 LinkList練習
:::spoiler

36 - LinkList練習
*此題須使用Link List實作，否則不予計分。
*請勿使用全域變數
(須符合上述兩項規定並通過所有測資才予以給分，期末會進行檢查)

給予一個初始Link List，請你進行插入節點、刪除節點的操作
請輸出進行操作後，最後的Link List

--------------------------------------------------------

本題不會出現有重複數值的節點

輸入說明
第一行輸入 n，代表初始Link List有多少個節點
第二行輸入 n 個整數，依序分別為每個節點的值，第一個整數為起始節點，最後一個整數為結束節點

接下來有多行，總共有6種操作:
1 x，代表從尾端插入數值為 x 的新節點。

2 x y，代表搜尋數值為 x 的節點，並在其之後插入數值為 y 的新節點；
若 x 不在Link List中，則不必插入 y 。

3 x，代表刪除數值為 x 的節點；若 x 不在Link List中，則不必刪除任何節點。

4 代表 刪除起始節點，須將起始節點的下一個節點做為新的起始節點。
若 Link List 已無節點，則不必刪除任何節點。

5 代表 刪除結束節點，須將結束節點的前一個節點做為新的結束節點。
若 Link List 已無節點，則不必刪除任何節點。

6 代表 結束程式，並從起始節點到結束節點，依序輸出各個節點的值；
若Link List已無任何節點，則輸出"None any node"。

輸出說明
輸出共一行，從起始節點到結束節點，依序輸出各個節點的值；每個數字中間以空格間隔
若Link List已無任何節點，則輸出"None any node"

--------------------------------------------------------

範例輸入1 說明
5
1 2 3 4 5 初始Link List: 1 2 3 4 5
1 6 從尾端插入數值為 6 的新節點(1 2 3 4 5 6)
2 3 7 搜尋數值為 3 的節點，並在其之後插入數值為 7 的新節點(1 2 3 7 4 5 6)
3 2 刪除數值為 2 的節點 (1 3 7 4 5 6)
4 刪除起始節點 (3 7 4 5 6)
5 刪除結束節點 (3 7 4 5)
6 結束程式

範例輸出1
3 7 4 5
--------------------------------------------------------

Sample Input 1:
5
1 2 3 4 5
1 6
2 3 7
3 2
4
5
6

Sample Output 1:
3 7 4 5

--------------------------------------------------------

Sample Input 2:
6
1 3 5 7 9 11
2 1 15
2 3 17
2 5 19
2 7 21
2 9 23
2 11 25
6

Sample Output 2:
1 15 3 17 5 19 7 21 9 23 11 25

--------------------------------------------------------

Sample Input 3:
5
0 2 4 6 8
1 10
5
4
2 0 1
3 0
3 2
6

Sample Output 3:
4 6 8


--------------------------------------------------------

Sample Input 4:
5
5 4 3 2 1
3 5
3 4
3 3
3 2
3 1
4
5
6

Sample Output 4:
None any node

--------------------------------------------------------

Sample Input 5:
1
1
5
2 1 2
1 3
2 3 4
2 3 5
5
6

Sample Output 5:
3 5

:::
# 37 LinkList多項式
:::spoiler

37 - LinkList多項式
*此題須使用Link List實作，否則不予計分。
*請勿使用全域變數
(須符合上述兩項規定並通過所有測資才予以給分，期末會進行檢查)

輸入兩個多項式，輸出相加、相減、相乘的結果。例如:

2x^4 + 3x^3 + x -1
x^5 - x^3 + 4x^2 - 3x +2
結果：
x^5 + 2x^4 + 2x^3 + 4x^2 - 2x + 1
-x^5 + 2x^4 + 4x^3 - 4x^2 + 4x - 3
2x^9 + 3x^8 - 2x^7 + 6x^6 + 5x^5 - 6x^4 + 11x^3 - 7x^2 + 5x - 2

--------------------------------------------------------

輸入說明
輸入兩筆資料，分別代表兩個多項式。
每一筆輸入 n 個整數，第一個代表 n-1次方的係數，第 n 個代表 0 次方的係數。

輸出說明
輸出共三行
第一行 輸出兩個多項式相加的結果
第二行 輸出兩個多項式相減的結果
第三行 輸出兩個多項式相乘的結果

多項式運算的結果，輸出計算後從最高次方到0次方的結果。
每一項需輸出係數、x、x的次方數
若係數為0，不輸出該項
若係數為1，則不輸出係數，僅需輸出正負號
若係數為正數且次方不為最高次方，需輸出+號
x的次方數 > 1，輸出ax^k (a為係數，k為次方數)
x的次方數 = 1，輸出ax (a為係數)
x的次方數 = 0，輸出a (a為係數)
如果所有係數都為0，則該行輸出0 (參考範例測資7)

--------------------------------------------------------

範例輸入1 說明
2 3 0 1 -1 (2x^4+3x^3+x-1)
1 0 -1 4 -3 2 (x^5-x^3+4x^2-3x+2)

範例輸出1 說明
x^5+2x^4+2x^3+4x^2-2x+1 [ (2x^4+3x^3+x-1) + (x^5-x^3+4x^2-3x+2) ]
-x^5+2x^4+4x^3-4x^2+4x-3 [ (2x^4+3x^3+x-1) - (x^5-x^3+4x^2-3x+2) ]
2x^9+3x^8-2x^7+6x^6+5x^5-6x^4+11x^3-7x^2+5x-2 [ (2x^4+3x^3+x-1) * (x^5-x^3+4x^2-3x+2) ]

--------------------------------------------------------

Sample Input 1:
2 3 0 1 -1
1 0 -1 4 -3 2

Sample Output 1:
x^5+2x^4+2x^3+4x^2-2x+1
-x^5+2x^4+4x^3-4x^2+4x-3
2x^9+3x^8-2x^7+6x^6+5x^5-6x^4+11x^3-7x^2+5x-2

--------------------------------------------------------

Sample Input 2:
3 -7 1 2
7 -1 4

Sample Output 2:
3x^3+6
3x^3-14x^2+2x-2
21x^5-52x^4+26x^3-15x^2+2x+8

--------------------------------------------------------

Sample Input 3:
0 0 0 0 0 0 0
1 2 3 4 5 6 7 8

Sample Output 3:
x^7+2x^6+3x^5+4x^4+5x^3+6x^2+7x+8
-x^7-2x^6-3x^5-4x^4-5x^3-6x^2-7x-8
0

--------------------------------------------------------

Sample Input 4:
100 2 3 90 20 -123
5 9 -1 -2 0 0

Sample Output 4:
105x^5+11x^4+2x^3+88x^2+20x-123
95x^5-7x^4+4x^3+92x^2+20x-123
500x^10+910x^9-67x^8+275x^7+903x^6-531x^5-1307x^4+83x^3+246x^2

--------------------------------------------------------

Sample Input 5:
1 0 0 1
1 0 0 1

Sample Output 5:
2x^3+2
0
x^6+2x^3+1

--------------------------------------------------------

Sample Input 6:
-1 0 0 -1
1 0 0 1

Sample Output 6:
0
-2x^3-2
-x^6-2x^3-1

--------------------------------------------------------

Sample Input 7:
0
0

Sample Output 7:
0
0
0

--------------------------------------------------------

Sample Input 8:
1 1 0 0
1 1

Sample Output 8:
x^3+x^2+x+1
x^3+x^2-x-1
x^4+2x^3+x^2

:::
# 38 LinkList實作Stack
:::spoiler

38 - LinkList實作Stack
*此題須使用Link List實作，否則不予計分。
*請勿使用全域變數
(須符合上述兩項規定並通過所有測資才予以給分，期末會進行檢查)

使用鏈結串列模擬stack後進先出（LIFO, Last In First Out）的原理運作。
兩種基本操作：push 和 pop
push：將資料放入堆疊的頂端（串列形式），堆疊頂端top指標加一。
pop：將頂端資料輸出（回傳），堆疊頂端top指標減一。

每一次push和pop的一筆資料都包含姓名、年齡、生日(年、月、日)

--------------------------------------------------------

輸入說明:
1 代表 push，再依序輸入姓名、年齡、生日(年、月、日)，參數之間以空白相隔
2 代表 pop，再輸入一個數字，進行不同的操作，
操作數字如下:
1: 印出該次pop的資料中的姓名 (不含雙引號)
2: 印出該次pop的資料中的年齡
3: 印出該次pop的資料中的生日 (年、月、日之間以底線連結)
若stack中為空則印出 The Stack is empty
3 代表 pop直到stack為空，且輸出每次pop的資料中姓名、年齡以及生日，中間以空白分隔
若stack中為空則印出 The Stack is empty
4 代表 print，輸出 stack中所有的資料，但不將資料從stack中移除。
輸出的順序同pop，從頂端開始輸出 (參考範例測資1)
每次輸出資料中的姓名、年齡以及生日，中間以空白分隔
若stack中為空則印出 The Stack is empty
5 結束程式，並輸出stack中剩餘的資料數量。

輸出說明
依照輸入，輸出對應的資料

--------------------------------------------------------

範例輸入1 說明
1 Marry 19 1989 7 16 (push Marry 19 1989 7 16 到stack頂端，目前資料數量: 1)
1 Tom 22 1996 10 19 (push Tom 22 1996 10 19 到stack頂端，目前資料數量: 2)
2 1 (pop Tom ，目前資料數量: 1)
1 Billy 15 2005 3 18 (push Billy 15 2005 3 18 到stack頂端，目前資料數量: 2)
2 3 (pop 2005_3_18，目前資料數量: 1)
2 2 (pop 19，目前資料數量: 0)
1 Lucas 24 1993 5 21 (push Lucas 24 1993 5 21 到stack頂端，目前資料數量: 1)
2 3 (pop 1993_5_21，目前資料數量: 0)
2 1 (輸出 The Stack is empty，目前資料數量: 0)
1 Johnson 10 2003 7 10 (push Johnson 10 2003 7 10 到stack頂端，目前資料數量: 1)
1 KillerQueen 49 1973 10 21 (push KillerQueen 49 1973 10 21 到stack頂端，目前資料數量:2)
4 (輸出: KillerQueen 49 1973_10_21\nJohnson 10 2003_7_10)
1 GoldExperience 27 1995 9 26 (push GoldExperience 27 1995 9 26 到stack頂端，目前資料數量: 3)
3 (pop GoldExperience 27 1995_9_26\nKillerQueen 49 1973_10_21\nJohnson 10 2003_7_10，目前資料數量: 0)
5 (結束程式，輸出目前資料數量: 0)

範例輸出1
Tom
2005_3_18
19
1993_5_21
The Stack is empty
KillerQueen 49 1973_10_21
Johnson 10 2003_7_10
GoldExperience 27 1995_9_26
KillerQueen 49 1973_10_21
Johnson 10 2003_7_10
0

--------------------------------------------------------

Sample Input 1:
1 Marry 19 1989 7 16
1 Tom 22 1996 10 19
2 1
1 Billy 15 2005 3 18
2 3
2 2
1 Lucas 24 1993 5 21
2 3
2 1
1 Johnson 10 2003 7 10
1 KillerQueen 49 1973 10 21
4
1 GoldExperience 27 1995 9 26
3
5

Sample Output 1:
Tom
2005_3_18
19
1993_5_21
The Stack is empty
KillerQueen 49 1973_10_21
Johnson 10 2003_7_10
GoldExperience 27 1995_9_26
KillerQueen 49 1973_10_21
Johnson 10 2003_7_10
0

--------------------------------------------------------

Sample Input 2：
1 NTUT 20 1999 8 1
1 NTUT 30 1999 7 31
3
4
2 1
1 Andy 14 2004 4 1
5

Sample Output 2：
NTUT 30 1999_7_31
NTUT 20 1999_8_1
The Stack is empty
The Stack is empty
1

--------------------------------------------------------

Sample Input 3：
1 Marry 19 1989 7 16
1 Tom 22 1996 10 19
1 Billy 15 2005 3 18
1 Lucas 24 1993 5 21
2 1
2 2
2 3
2 1
2 2
2 3
5

Sample Output 3：
Lucas
15
1996_10_19
Marry
The Stack is empty
The Stack is empty
0

--------------------------------------------------------

Sample Input 4：
1 Marry 19 1989 7 16
2 1
1 Marry 20 1987 6 17
2 2
1 Marry 21 1986 5 18
2 3
1 Marry 22 1988 4 19
2 1
1 Marry 23 1984 3 10
1 Marry 24 1983 2 11
4
5

Sample Output 4：
Marry
20
1986_5_18
Marry
Marry 24 1983_2_11
Marry 23 1984_3_10
2

--------------------------------------------------------

Sample Input 5：
1 StarPlatinum 17 1970 4 4
1 CrazyDiamond 16 1983 4 1
1 GoldExperience 15 1985 4 16
1 StoneFree 19 1993 1 8
1 SoftandWet 19 2016 7 7
5

Sample Output 5：
5

:::
# 39 LinkList實作Queue
:::spoiler

39 - LinkList實作Queue
*此題須使用Link List實作，否則不予計分。
*請勿使用全域變數
(須符合上述兩項規定並通過所有測資才予以給分，期末會進行檢查)

使用鏈結串列模擬queue先進先出（FIFO, First In First Out）的原理運作。
兩種基本操作enqueue 和 dequeue
enqueue：將資料存入佇列中 (放入佇列尾端)。
dequeue：將資料從佇列中取出 (從佇列頭端取出)。

每一次enqueue和dequeue的一筆資料都包含姓名、年齡、生日(年、月、日)

--------------------------------------------------------

輸入說明:
1 代表 enqueue，再依序輸入姓名、年齡、生日(年、月、日)，參數之間以空白相隔
2 代表 dequeue，再輸入一個數字，進行不同的操作，
操作數字如下:
1: 印出該次dequeue的資料中的姓名
2: 印出該次dequeue的資料中的年齡
3: 印出該次dequeue的資料中的生日 (年、月、日之間以底線連結)
若queue為空則印出 The Queue is empty
3 代表 dequeue直到queue為空，且輸出每次dequeue的資料中姓名、年齡以及生日，中間以空白分隔
若queue為空則印出 The Queue is empty
4 代表 print，輸出 queue中所有的資料，但不將資料從queue中移除。
輸出的順序同dequeue，從頭端開始輸出 (參考範例測資1)
每次輸出資料中的姓名、年齡以及生日，中間以空白分隔
若queue為空則印出 The Queue is empty
5 結束程式，並輸出queue中剩餘的資料數量。

輸出說明
依照輸入，輸出對應的資料

--------------------------------------------------------

範例輸入1 說明
1 Marry 19 1989 7 16 (enqueue Marry 19 1989 7 16 到queue尾端，目前資料數量: 1)
1 Tom 22 1996 10 19 (enqueue Tom 22 1996 10 19 到queue尾端，目前資料數量: 2)
2 1 (dequeue Marry ，目前資料數量: 1)
1 Billy 15 2005 3 18 (enqueue Billy 15 2005 3 18 到queue尾端，目前資料數量: 2)
2 3 (dequeue 1996_10_19，目前資料數量: 1)
2 2 (dequeue 15，目前資料數量: 0)
1 Lucas 24 1993 5 21 (enqueue Lucas 24 1993 5 21 到queue尾端，目前資料數量: 1)
2 3 (dequeue 1993_5_21，目前資料數量: 0)
2 1 (輸出 The Queue is empty，目前資料數量: 0)
1 Johnson 10 2003 7 10 (enqueue Johnson 10 2003 7 10 到queue尾端，目前資料數量: 1)
1 KillerQueen 49 1973 10 21 (enqueue KillerQueen 49 1973 10 21 到queue尾端，目前資料數量:2)
4 (輸出: Johnson 10 2003_7_10\nKillerQueen 49 1973_10_21)
1 GoldExperience 27 1995 9 26 (enqueue GoldExperience 27 1995 9 26 到queue尾端，目前資料數量: 3)
3 (dequeue Johnson 10 2003_7_10\nKillerQueen 49 1973_10_21\nGoldExperience 27 1995_9_26，目前資料數量: 0)
5 (結束程式，輸出目前資料數量: 0)

範例輸出1
Marry
1996_10_19
15
1993_5_21
The Queue is empty
Johnson 10 2003_7_10
KillerQueen 49 1973_10_21
Johnson 10 2003_7_10
KillerQueen 49 1973_10_21
GoldExperience 27 1995_9_26
0

--------------------------------------------------------

Sample Input 1:
1 Marry 19 1989 7 16
1 Tom 22 1996 10 19
2 1
1 Billy 15 2005 3 18
2 3
2 2
1 Lucas 24 1993 5 21
2 3
2 1
1 Johnson 10 2003 7 10
1 KillerQueen 49 1973 10 21
4
1 GoldExperience 27 1995 9 26
3
5

Sample Output 1:
Marry
1996_10_19
15
1993_5_21
The Queue is empty
Johnson 10 2003_7_10
KillerQueen 49 1973_10_21
Johnson 10 2003_7_10
KillerQueen 49 1973_10_21
GoldExperience 27 1995_9_26
0

--------------------------------------------------------

Sample Input 2：
1 NTUT 20 1999 8 1
1 NTUT 30 1999 7 31
3
4
2 1
1 Andy 14 2004 4 1
5

Sample Output 2：
NTUT 20 1999_8_1
NTUT 30 1999_7_31
The Queue is empty
The Queue is empty
1

--------------------------------------------------------

Sample Input 3：
1 Marry 19 1989 7 16
1 Tom 22 1996 10 19
1 Billy 15 2005 3 18
1 Lucas 24 1993 5 21
2 1
2 2
2 3
2 1
2 2
2 3
5

Sample Output 3：
Marry
22
2005_3_18
Lucas
The Queue is empty
The Queue is empty
0

--------------------------------------------------------

Sample Input 4：
1 Marry 19 1989 7 16
2 1
1 Marry 20 1987 6 17
2 2
1 Marry 21 1986 5 18
2 3
1 Marry 22 1988 4 19
2 1
1 Marry 23 1984 3 10
1 Marry 24 1983 2 11
4
5

Sample Output 4：
Marry
20
1986_5_18
Marry
Marry 23 1984_3_10
Marry 24 1983_2_11
2

--------------------------------------------------------

Sample Input 5：
1 StarPlatinum 17 1970 4 4
1 CrazyDiamond 16 1983 4 1
1 GoldExperience 15 1985 4 16
1 StoneFree 19 1993 1 8
1 SoftandWet 19 2016 7 7
5

Sample Output 5：
5

:::
# 40 建構唯一二元樹

:::spoiler

40 - 建構唯一二元樹
*此題須使用Link List實作，否則不予計分。
*請勿使用全域變數
(須符合上述兩項規定並通過所有測資才予以給分，期末會進行檢查)

題目給定前序或後序以及中序，請建構唯一的Binary Tree。
輸出Tree的內容，輸出順序為由上而下，由左而右印出。

前序代號：P
中序代號：I
後序代號：O

--------------------------------------------------------

輸入說明:
輸入共四行
第一行 輸入前序、中序或後序代號。
第二行 輸入上一行輸入種類尋訪的結果，皆為大寫英文字母。
第三行 輸入前序、中序或後序代號。
第四行 輸入上一行輸入種類尋訪的結果，皆為大寫英文字母。

輸出說明
輸出唯一二元樹的內容，輸出順序為由上而下，由左而右。

--------------------------------------------------------

範例輸入1 說明
P (代表下一行要輸入唯一二元樹的前序走訪)
ABCDEFGHI (唯一二元樹的前序走訪結果)
I (代表下一行要輸入唯一二元樹的中序走訪)
BCAEDGHFI (唯一二元樹的中序走訪結果)

範例輸出1 說明
ABDCEFGIH (唯一二元樹由上而下，由左而右的輸出結果)

範例測資1畫出來的二元樹: https://ppt.cc/fr1eEx


範例輸入3 說明
I (代表下一行要輸入唯一二元樹的中序走訪)
EFDAGHCB (唯一二元樹的中序走訪結果)
O (代表下一行要輸入唯一二元樹的後序走訪)
FEDHGCBA (唯一二元樹的後序走訪結果)

範例輸出3 說明
ADBECFGH (唯一二元樹由上而下，由左而右的輸出結果)

範例測資3畫出來的二元樹: https://ppt.cc/fI3v7x

--------------------------------------------------------

Sample Input 1:
P
ABCDEFGHI
I
BCAEDGHFI


Sample Output 1:
ABDCEFGIH

--------------------------------------------------------

Sample Input 2：
O
CBEHGIFDA
I
BCAEDGHFI

Sample Output 2：
ABDCEFGIH

--------------------------------------------------------

Sample Input 3：
I
EFDAGHCB
O
FEDHGCBA

Sample Output 3：
ADBECFGH

--------------------------------------------------------

Sample Input 4：
O
GIFHBEDCA
I
GFIBHDEAC

Sample Output 4：
ADCBEFHGI

--------------------------------------------------------

Sample Input 5：
P
ABDFIHEGC
I
BAFHEIDGC

Sample Output 5：
ABDFGICHE

--------------------------------------------------------

Sample Input 6：
P
ABCDEFG
I
GFEDCBA

Sample Output 6：
ABCDEFG

--------------------------------------------------------

Sample Input 7：
O
GFEDCBA
I
ABCDEFG

Sample Output 7：
ABCDEFG

--------------------------------------------------------

Sample Input 8：
O
IHGFEDCBA
I
ACEGIHFDB

Sample Output 8：
ABCDEFGHI

--------------------------------------------------------

Sample Input 9：
P
ABCDEFGHIJK
I
FEDCBAGHIJK


Sample Output 9：
ABGCHDIEJFK

--------------------------------------------------------

Sample Input 10：
P
ABDHIEJKCFLMGNO
I
HDIBJEKALFMCNGO

Sample Output 10：
ABCDEFGHIJKLMNO

:::
# 41 城市拜訪
:::spoiler

41 - 城市拜訪

BMI博士想要拜訪N個城市，且博士希望能遵守三個原則:
1. 每一座城市都要拜訪到
2. 可以從任意城市出發，但最終要回到出發的城市
3. 除了最終回到出發城市之外，不能拜訪已經訪問過的城市 (每座城市只能拜訪一次)

可參考講義中的動態程式規劃章節:
https://myweb.ntut.edu.tw/~jykuo/course/08C_%E9%99%A3%E5%88%97array_87.pdf

--------------------------------------------------------

題目給予N個城市和城市之間的距離。
從任意城市出發，拜訪每一座城市，每座城市只能拜訪一次，不能重複拜訪，並在最後回到出發城市。

算出訪問每一座城市一次並回到起始城市的最短距離。

輸入說明:
第一行輸入 一數字N，代表有N座城市
接下來N行，每行輸入N個數字，代表一城市到另一城市的距離

輸出說明:
輸出訪問每一座城市一次並回到起始城市的最短距離

--------------------------------------------------------

範例輸入1 說明
4 (共有4座城市，C0、C1、C2、C3)
0 3 7 8 (C0到C0的距離: 0、C0到C1的距離: 3、C0到C2的距離: 7、C0到C3的距離: 8)
3 0 2 6 (C1到C0的距離: 3、C1到C1的距離: 0、C1到C2的距離: 2、C1到C3的距離: 6)
7 2 0 4 (C2到C0的距離: 7、C2到C1的距離: 2、C2到C2的距離: 0、C2到C3的距離: 4)
8 6 4 0 (C3到C0的距離: 8、C3到C1的距離: 6、C3到C2的距離: 4、C3到C3的距離: 0)

範例輸出1 說明
17 (最短距離: C0->C1->C2->C3->C0 = 3+2+4+8=17)

--------------------------------------------------------

Sample Input 1:
4
0 3 7 8
3 0 2 6
7 2 0 4
8 6 4 0

Sample Output 1:
17

--------------------------------------------------------

Sample Input 2：
3
0 3 7
3 0 2
7 2 0

Sample Output 2：
12

--------------------------------------------------------

Sample Input 3：
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Sample Output 3：
80

--------------------------------------------------------

Sample Input 4：
5
0 1 4 5 3
1 0 2 3 4
2 3 0 3 4
3 2 1 0 3
9 1 2 3 0

Sample Output 4：
10

--------------------------------------------------------

Sample Input 5：
5
0 3 4 2 6
5 0 3 5 1
8 5 0 6 9
5 3 9 0 5
9 8 6 4 0

Sample Output 5：
19

:::