# 112CP_Group9-3 出題報告
## 出題動機 ##
在題庫看到寶可夢，想到也是卡牌遊戲的遊戲王，然後依順序抽牌符合linked list操作，於是出此題目。
# Q1
## 說明 ##
有天武藤遊戲的爺爺給了遊戲一副牌，說是當今最流行的卡牌遊戲--遊戲王卡!遊戲開心極了，等不及明天到學校和朋友決鬥。但是在當今主流牌組滿天飛的時代，爺爺的卡有些已經過時了，也因此要重組牌組才行，而他最一開始要做的就是將所有的牌進行分類。
請你幫遊戲設計:
1. 一個結構包含子成員：
- `char name[100]`: 卡牌名稱
- `int type`: 卡牌種類，0: monster(怪獸卡)，1: spell(魔法卡)，2: trap(陷阱卡)
2. <u>**typedef 該結構成**</u>`card`
3. 將卡牌依照輸入順序，type分類至`monster`, `spell`, `trap`三個card陣列的function `classify()`，並記錄各type分類的數量至`size[type]`中。
本題已幫你準備好 main.c如下：
```c
#include <stdio.h>
#include <string.h>
#include "card.h"
int card_type(char *str){ //reads str and returns type
int cmp = strcmp(str, "spell");
if(cmp < 0)return 0;
else if(cmp == 0)return 1;
else return 2;
}
int main(int argc, char *argv[]) {
int n;
scanf("%d", &n);
card deck[n]; //records input cards
card classified[3][n], arr[3]; //three decks of monster, spell, trap
int size[3] = {0, 0, 0}; //records sizes of three decks
char input[8];
for(int i = 0; i < n; i++){
scanf("%s", deck[i].name);
scanf("%s", input);
deck[i].type = card_type(input);
}
classify(deck, n, classified[0], classified[1], classified[2], size);
int target; //0, 1, 2
scanf("%s", input); //which deck to output
target = card_type(input);
for(int i = 0; i < size[target]; i++){
printf("%s\n", classified[target][i].name);
}
}
```
請完成card.c和card.h並上傳<br>
card.h
```c
typedef struct Card// or other name you prefer
{
//...
} card;
void classify(card *deck, int total, card *monster, card *spell, card *trap, int *size);
```
card.c
```c
#include "card.h"
#include <string.h>
void classify(card *deck, int total, card *monster, card *spell, card *trap, int *size){
//...
}
```
## Input Format ##
第一行為$`N`$，代表會接下來會有$`N`$張卡片的輸入，每張卡會有兩行輸入，第一行會是卡牌名稱的字串name，第二行則是卡牌種類type。最後一行會是target字串，是三種type字串其中之一，代表要依照輸入順序輸出所有種類是target的卡的名稱。
- $1 \leq N \leq 10^3$
- $\forall$ $1 \leq i \leq N$, $1 \leq strlen(\text{name}_i) \leq 100$
- $\forall$ $1 \leq i \leq N$, $\text{name}_i$ only contains characters in $\text{[a-zA-Z]}$
- $1 \leq \displaystyle \sum_{i=1} ^ N strlen(\text{name}_i) \leq 1000$
- $\forall$ $1 \leq i \leq N$, $`\text{type}_i \in \text{\{"monster", "spell", "trap"\}}`$
- $`\text{target} \in \text{\{"monster", "spell", "trap"\}}`$
## Output Format ##
輸出所有種類是target的卡的名稱，每行輸出一張後換行，如果沒有則不輸出。
## Sample Input ##
```
4
BlueEyesWhiteDragon
monster
MonsterReborn
spell
BlackMagicianGirl
monster
SkillDrain
trap
monster
```
## Sample Output ##
```
BlueEyesWhiteDragon
BlackMagicianGirl
```
## 解題思路 ##
- 依題序建`struct`並`typedef`
- `function classify`裡放一個`for-loop`整個牌組並依照`type`分配到對應的`array`位置並更新該`array`的`size`
## 解法 ##
### card.c
```c=
#include "card.h"
#include <string.h>
void classify(card *deck, int total, card *monster, card *spell, card *trap, int *size){
for(int i = 0; i < total; i++){
if(!deck[i].type){
strcpy(monster[size[0]].name, deck[i].name);
size[0]++;
}
else if(deck[i].type == 1){
strcpy(spell[size[1]].name, deck[i].name);
size[1]++;
}
else{
strcpy(trap[size[2]].name, deck[i].name);
size[2]++;
}
}
}
```
### card.h
```c=
typedef struct Card{
char name[100];
int type; //0: monster, 1: spell, 2: trap
} card;
void classify(card *deck, int total, card *monster, card *spell, card *trap, int *size);
```
## 測資說明
測資1 \~ 3: 測試所有牌type都一樣的情況
<br>
測資4 \~ 7: $100\leq N\leq 300$
<br>
測資8, 9: $300\leq N\leq 1000$
# Q2
## 說明 ##
在組好牌組和千年積木後，遊戲遇到了封印在積木裡的無名靈魂並交上了朋友，我們就叫這個無名靈魂裏遊戲好了。隔天遊戲就去學校和人決鬥了，根據裏遊戲的教導，一名出色的決鬥者在一回合裡要盡可能地做完能做的事，而一回合裡能做的事有:<br>
- 能通常召喚怪獸卡就通常召喚並抽一張卡<br>
- 能發動魔法卡就發動並抽一張卡<br>
- 能蓋陷阱卡就蓋並抽一張卡<br>
- 若手牌數$`\lt 6`$且牌組還有牌則抽一張卡
當此回合不能做任何動作後，回合結束。
關於能不能通常召喚怪獸是根據以下規則:
一個人有$`5`$格怪獸格，一回合只有一次通常召喚機會，只要還有空的格子且機會還沒用掉就可以通常召喚並用掉一格可用格和機會。如果$`5`$格有怪獸則不能再執行通常召喚
關於能不能發動魔法卡/蓋陷阱卡則是根據以下規則:
一個人有$`5`$格魔法/陷阱格，只要還有空的格子就可以執行發動卡牌或蓋卡，發動完魔法卡該格可以繼續使用，蓋放陷阱卡則會佔用掉一格可用格，如果$`5`$格都蓋滿陷阱卡則不能再執行發動和蓋卡
### 懶人包 ###
初始手牌數為$`0`$，\*只要手牌數$`\lt 6`$且牌組還有牌就可以抽一張牌，若是怪獸卡且還沒有用掉通常召喚機會則可以通常召喚他(手牌數$`-1`$)，魔法卡/陷阱卡則是看是否有剩餘的魔法/陷阱格，有就發動/蓋卡(手牌數$`-1`$)，判斷完則跳回是否可以抽卡的判斷\*
請你幫遊戲設計:
1. 結構1包含子成員 - 卡牌:
- `char name[100]`: 卡牌名稱
- `int type`: 卡牌種類，0: monster(怪獸卡)，1: spell(魔法卡)，2: trap(陷阱卡)
- `struct [結構1名稱] *next`: 指向下一張牌的address
2. <u>**typedef 結構1成**</u>`card`
3. 結構2包含子成員 - 牌組:
- `int size`: 牌組卡牌張數
- `struct [結構1名稱] *head`: 指向牌組第一張牌的address
- `struct [結構1名稱] *end`: 指向牌組最後一張牌的address
4. <u>**typedef 結構2成**</u>`deck`
5. 將$`N`$張卡牌輸入牌組的function `load()`
6. 執行上面抽卡規則一回合，最後分別印出所有手牌的名稱+種類、怪獸召喚數、蓋卡數
本題已幫你準備好 main.c如下：<br>
\*rands[1 \~ 200]則會提供在下面的hint，足夠debug testcase 0 \~ 3<br>
(通常代表4~9也能過了)
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "deck.h"
#include "rands.h" //can be replaced by int rands provided in hints part below
int card_type(char *str){ //reads str and returns type
int cmp = strcmp(str, "spell");
if(cmp < 0)return 0;
else if(cmp == 0)return 1;
else return 2;
}
void shuffle(card ** pos, int size, deck * cards){
//we shuffle for you
for(int i = 0; i < size; i++){
int first = rands[i * 2] % size, second = rands[i * 2 + 1] % size;
if(second == first)second = (second + 1) % size;
card *tmp = pos[first];
pos[first] = pos[second];
pos[second] = tmp;
}
for(int i = 0; i < size - 1; i++)
pos[i] -> next = pos[i + 1];
cards -> head = pos[0];
cards -> end = pos[size - 1];
}
int main(int argc, char *argv[]) {
int n;
scanf("%d", &n);
deck cards;
cards.size = n;
load(&cards, n, card_type);
//shuffle part, can ignore
card *position[n], *cur = cards.head;
for(int i = 0; i < n; i++){
position[i] = cur;
cur = cur -> next;
}
shuffle(position, n, &cards);
draw(&cards, n);
}
```
請完成deck.c和deck.h並上傳<br>
deck.h
```c
typedef struct Card // or other name you prefer
{
//...
} card;
typedef struct Deck // or other name you prefer
{
//...
} deck;
void load(deck *cards, int size, int card_type(char *str));
void draw(deck *cards, int size);
```
deck.c
```c
#include "deck.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void load(deck *cards, int size, int card_type(char *str)){
//don't be scared of card_type, just use it as function card_type()
//...
}
void draw(deck *cards, int size){
//...
}
```
## Input Format ##
第一行為$`N`$，代表會接下來會有$`N`$張卡片的輸入，每張卡會有兩行輸入，第一行會是卡牌名稱的字串name，第二行則是卡牌種類type。
- $1 \leq N \leq 10^3$
- $\forall$ $1 \leq i \leq N$, $1 \leq strlen(\text{name}_i) \leq 100$
- $\forall$ $1 \leq i \leq N$, $\text{name}_i$ only contains characters in $\text{[a-zA-Z]}$
- $1 \leq \displaystyle \sum_{i=1} ^ N strlen(\text{name}_i) \leq 1000$
- $\forall$ $1 \leq i \leq N$, $`\text{type}_i \in \text{\{"monster", "spell", "trap"\}}`$
## Output Format ##
第$`1`$行輸出"hands:"並換行。<br>
假設此時手牌有$`n`$張，則$`\forall`$ $`1 \leq i \leq n`$，第$`2i`$行輸出name_i，第$`2i+1`$行輸出type_i。<br>
第$`2n+2`$行則輸出"summoned: "和summoned(此回合怪獸召喚數)並換行。<br>
第$`2n+3`$行則輸出"sets: "和sets(此回合蓋卡數)並換行。<br>
**第$`1`$行hands:後無空格，第$`2n+2, 2n+3`$行冒號後有空格。**<br>
- $0 \leq n \leq 6$
- $1 \leq strlen(\text{name}_i) \leq 100$
- $\forall$ $1 \leq i \leq N$, $`\text{type}_i \in \text{\{ "monster", "spell", "trap" \}}`$
- $`\text{summoned} \in \text{\{ 0, 1 \}}`$
- $0 \leq \text{sets} \leq 5$
## Sample Input ##
```
4
BlueEyesWhiteDragon
monster
MonsterReborn
spell
BlackMagicianGirl
monster
SkillDrain
trap
```
## Sample Output ##
```
hands:
BlackMagicianGirl
monster
summoned: 1
sets: 1
```
## Hints ##
1. yeah it's just linked list, but it's suggested to code double linked list instead single linked list although not necessary<br>
(may help in Q3?)
2. rands:
```c
int rands[200] = {1804289383, 846930886, 1681692777, 1714636915, 1957747793, 424238335, 719885386, 1649760492, 596516649, 1189641421, 1025202362, 1350490027, 783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426, 304089172, 1303455736, 35005211, 521595368, 294702567, 1726956429, 336465782, 861021530, 278722862, 233665123, 2145174067, 468703135, 1101513929, 1801979802, 1315634022, 635723058, 1369133069, 1125898167, 1059961393, 2089018456, 628175011, 1656478042, 1131176229, 1653377373, 859484421, 1914544919, 608413784, 756898537, 1734575198, 1973594324, 149798315, 2038664370, 1129566413, 184803526, 412776091, 1424268980, 1911759956, 749241873, 137806862, 42999170, 982906996, 135497281, 511702305, 2084420925, 1937477084, 1827336327, 572660336, 1159126505, 805750846, 1632621729, 1100661313, 1433925857, 1141616124, 84353895, 939819582, 2001100545, 1998898814, 1548233367, 610515434, 1585990364, 1374344043, 760313750, 1477171087, 356426808, 945117276, 1889947178, 1780695788, 709393584, 491705403, 1918502651, 752392754, 1474612399, 2053999932, 1264095060, 1411549676, 1843993368, 943947739, 1984210012, 855636226, 1749698586, 1469348094, 1956297539, 1036140795, 463480570, 2040651434, 1975960378, 317097467, 1892066601, 1376710097, 927612902, 1330573317, 603570492, 1687926652, 660260756, 959997301, 485560280, 402724286, 593209441, 1194953865, 894429689, 364228444, 1947346619, 221558440, 270744729, 1063958031, 1633108117, 2114738097, 2007905771, 1469834481, 822890675, 1610120709, 791698927, 631704567, 498777856, 1255179497, 524872353, 327254586, 1572276965, 269455306, 1703964683, 352406219, 1600028624, 160051528, 2040332871, 112805732, 1120048829, 378409503, 515530019, 1713258270, 1573363368, 1409959708, 2077486715, 1373226340, 1631518149, 200747796, 289700723, 1117142618, 168002245, 150122846, 439493451, 990892921, 1760243555, 1231192379, 1622597488, 111537764, 338888228, 2147469841, 438792350, 1911165193, 269441500, 2142757034, 116087764, 1869470124, 155324914, 8936987, 1982275856, 1275373743, 387346491, 350322227, 841148365, 1960709859, 1760281936, 771151432, 1186452551, 1244316437, 971899228, 1476153275, 213975407, 1139901474, 1626276121, 653468858, 2130794395, 1239036029, 1884661237, 1605908235, 1350573793, 76065818, 1605894428, 1789366143, 1987231011, 1875335928, 1784639529 }
```
## 解題思路 ##
- 依題目指示建`struct`包含指定成員並`typedef`
- `function load`裡是`for-loop i`到`size`，每次推入新的`card`就`new`分配新位址並將`end`的`next`指向該位址(`i = 0`時則直接將`head`和`end`指向該位址)
- `function draw`裡
1. 宣告`cnt`、`summoned`、`sets`紀錄並`output "hands:\n"`，因為接下來我們是檢查每張抽進來的牌並輸出，所以推薦先印出指定`message`。
2. 建立`for-loop i to size && cnt < 6`
- 抽到的卡是`monster`且`summoned = 0`則不輸出並`summoned++`，`summoned > 0`則輸出並`cnt++`
- 是`spell`且`sets < 5`則不輸出，`sets = 5`則輸出並`cnt++`
- 是`trap`且`sets < 5`則不輸出且`sets++`，`sets = 5`則輸出並`cnt++`
3. 輸出`summoned: [summoned]\n`和`sets: [sets]\n`
## 解法 ##
### deck.c
```c=
#include "deck.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void load(deck *cards, int size, int card_type(char *str)){
char input[8];
for(int i = 0; i < size; i++){
card *cur = (card *)malloc(sizeof(card));
cur -> next = NULL;
scanf("%s", cur -> name);
scanf("%s", input);
cur -> type = card_type(input);
if(!i)
cards -> head = cur;
else
cards -> end -> next = cur;
cards -> end = cur;
}
}
void draw(deck *cards, int size){
int cnt = 0, summoned = 0, sets = 0;
card *cur = cards -> head;
printf("hands:\n");
for(int i = 0; i < size && cnt < 6; i++){
if(!cur -> type){
if(!summoned)summoned = 1;
else{
cnt ++;
printf("%s\n%s\n", cur -> name, "monster");
}
}
else if(cur -> type > 1){
if(sets < 5)sets ++;
else{
cnt ++;
printf("%s\n%s\n", cur -> name, "trap");
}
}
else{
if(sets >= 5){
cnt ++;
printf("%s\n%s\n", cur -> name, "spell");
}
}
cur = cur -> next;
}
printf("summoned: %d\n", summoned);
printf("sets: %d\n", sets);
}
```
### deck.h
```c=
typedef struct Card{
char name[100];
int type; //0: monster, 1: spell, 2: trap
struct Card *next;
} card;
typedef struct Deck{
int size;
card *head, *end;
} deck;
void load(deck *cards, int size, int card_type(char *str));
void draw(deck *cards, int size);
```
## 測資說明
測資1: $2\leq N\leq 20$。
<br>
測資2, 3: $20 \leq N \leq 100$，所有牌的type都一樣
<br>
測資4 \~ 7: $100\leq N\leq 300$
<br>
測資8, 9: $300\leq N\leq 1000$
# Q3
## 說明 ##
聽完裏遊戲的教導後，遊戲理解了牌組的運作，並自信了起來。沒想到隔天早上，萬惡的K*nami社居然發布了新的大師規則，遊戲也就又不會決鬥了。已知一名出色的決鬥者在一回合裡要盡可能地做完能做的事，而現在根據K社一個人一回合裡能做的事有:<br>
\*粗體字為新規則或有更改
- 能通常召喚怪獸卡就通常召喚並抽一張卡<br>
- **能特殊召喚怪獸卡就特殊召喚並抽一張卡** __new!__<br>
- 能發動魔法卡就發動並**處理效果** __updated!__<br>
- 能蓋陷阱卡就蓋並抽一張卡<br>
- 若手牌數$`\lt 6`$且牌組還有牌則抽一張卡
當此回合不能做任何動作後，回合結束。
關於能不能通常召喚/特殊召喚怪獸是根據以下規則:
一個人有$`5`$格怪獸格，一回合只有一次通常召喚機會，只要還有空的格子且機會還沒用掉就可以通常召喚並用掉一格可用格和機會，**特殊召喚則是只要還有空格就可以，且不消耗機會。可以通常召喚的怪獸(`效果編號0`)不能特殊召喚，可以特殊召喚的怪獸(`效果編號1`)不能通常召喚。** __new!__<br>
如果$`5`$格有怪獸則不能再執行通常召喚/特殊召喚
關於能不能發動魔法卡/蓋陷阱卡則是根據以下規則:
一個人有$`5`$格魔法/陷阱格，只要還有空的格子就可以蓋放陷阱卡並佔用掉一格可用格，發動完魔法卡則不會佔用格子，但會**根據卡牌效果有不同的發動條件和處理**:
__new!__
- `交換牌swap`: `效果編號0`, 要場上有空的格子且除了swap牌的手牌張數$`\geq 1`$才能發動，丟棄手牌中最早抽到的牌後從牌組抽一張牌
- `顛倒牌reverse`: `效果編號1`, 要場上有空的格子且牌組張數$`\geq 1`$才能發動，整副牌組顛倒過來後從牌組再抽一張
- 顛倒: $\forall$ $1 \leq i \leq N / 2$, $`\text{swap}`$($`\text{card}_i`$, $`\text{card}_{N - i + 1}`$)
如果$`5`$格都蓋滿陷阱卡則不能再執行發動和蓋卡
### 懶人包 ###
初始手牌數為$`0`$，\*只要手牌數$`\lt 6`$且牌組還有牌就可以抽一張牌(手牌數$`+1`$)，若是
- `效果編號0的怪獸卡`: 看是否有剩餘的怪獸格且還沒有通常召喚機會，都有則可以通常召喚他(手牌數$`-1`$)
- `效果編號1的怪獸卡`: 看是否有剩餘的怪獸格，有就可以特殊召喚他(手牌數$`-1`$)
- `效果編號0的魔法卡`: 看是否有剩餘的魔法/陷阱格且扣除自己的手牌數$`\geq 1`$，都滿足就可以發動它(手牌數$`-1`$)並丟棄手牌中最早抽到的牌(手牌數$`-1`$)
- `效果編號1的魔法卡`: 看是否有剩餘的魔法/陷阱格且牌組剩餘張數$`\geq 1`$，都滿足就可以發動它(手牌數$`-1`$)顛倒牌組
- 陷阱卡則是看是否有剩餘的魔法/陷阱格，有就發動/蓋卡(手牌數$`-1`$)
判斷完則跳回是否可以抽卡的判斷\*
請你幫遊戲設計:
1. 結構1包含子成員 - 卡牌:
- `char name[100]`: 卡牌名稱
- `int type`: 卡牌種類，0: monster(怪獸卡)，1: spell(魔法卡)，2: trap(陷阱卡)
- **`effect`: 效果編號 0/1** __new!__
- **`struct [結構1名稱] *pre`: 指向上一張牌的address** __new!__
- `struct [結構1名稱] *next`: 指向下一張牌的address
2. <u>**typedef 結構1成**</u>`card`
3. 結構2包含子成員 - 牌組:
- `int size`: 牌組卡牌張數
- `struct [結構1名稱] *head`: 指向牌組第一張牌的address
- `struct [結構1名稱] *end`: 指向牌組最後一張牌的address
4. <u>**typedef 結構2成**</u>`deck`
5. 將$`N`$張卡牌輸入牌組的function `load()`
6. 執行上面抽卡規則一回合，最後分別印出所有手牌的名稱+種類、**場上怪獸數**、蓋卡數 __updated!__
本題已幫你準備好 main.c如下：<br>
\*rands[1 \~ 200]則會提供在下面的hint，足夠debug testcase 0 \~ 4<br>
(通常代表5 \~ 7也能過了)
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hands.h"
#include "new_rand.h"
int card_type(char *str){
int cmp = strcmp(str, "spell");
if(cmp < 0)return 0;
else if(cmp == 0)return 1;
else return 2;
}
void shuffle(card ** pos, int size, deck * cards){
for(int i = 0; i < size; i++){
int first = rands[i * 2] % size, second = rands[i * 2 + 1] % size;
if(second == first)second = (second + 1) % size;
card *tmp = pos[first];
pos[first] = pos[second];
pos[second] = tmp;
}
for(int i = 0; i < size - 1; i++)
pos[i] -> next = pos[i + 1];
for(int i = 1; i < size; i++)
pos[i] -> pre = pos[i - 1];
cards -> head = pos[0];
cards -> end = pos[size - 1];
}
int main(int argc, char *argv[]) {
int n;
scanf("%d", &n);
deck cards;
cards.size = n;
load(&cards, n, card_type);
card *position[n], *cur = cards.head;
for(int i = 0; i < n; i++){
position[i] = cur;
cur = cur -> next;
}
shuffle(position, n, &cards);
draw(&cards, n);
}
```
請完成hands.c和hands.h並上傳<br>
hands.h
```c
typedef struct Card // or other name you prefer
{
//...
} card;
typedef struct Deck // or other name you prefer
{
//...
} deck;
void load(deck *cards, int size, int card_type(char *str));
void draw(deck *cards, int size);
```
hands.c
```c
#include "deck.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void load(deck *cards, int size, int card_type(char *str)){
//don't be scared of card_type, just use it as function card_type()
//...
}
void draw(deck *cards, int size){
//...
}
```
## Input Format ##
第一行為$`N`$，代表會接下來會有$`N`$張卡片的輸入，每張卡會有2或3行輸入，第一行會是卡牌名稱的字串`name`，第二行則是卡牌種類`type`，**如果是怪獸/魔法卡則還會有第三行輸入`effect`** __new!__
- $1 \leq N \leq 10^3$
- $\forall$ $1 \leq i \leq N$, $1 \leq strlen(\text{name}_i) \leq 100$
- $\forall$ $1 \leq i \leq N$, $\text{name}_i$ only contains characters in $\text{[a-zA-Z]}$
- $1 \leq \displaystyle \sum_{i=1} ^ N strlen(\text{name}_i) \leq 1000$
- $\forall$ $1 \leq i \leq N$, $`\text{type}_i \in \text{\{"monster", "spell", "trap"\}}`$
- $\forall$ $1 \leq i \leq N$ and $`\text{type}_i \in \text{\{"monster", "spell"\}}`$, $`\text{effect}_i \in \{ 0, 1\}`$ __new!__
## Output Format ##
第$`1`$行輸出"hands:"並換行。<br>
假設此時手牌有$`n`$張，則$`\forall`$ $`1 \leq i \leq n`$，第$`2i`$行輸出name_i，第$`2i+1`$行輸出type_i。<br>
第$`2n+2`$行則輸出"monsters: "和monsters(場上怪獸數)並換行。<br>
第$`2n+3`$行則輸出"sets: "和sets(此回合蓋卡數)並換行。<br>
**第$`1`$行hands:後無空格，第$`2n+2, 2n+3`$行冒號後有空格。**<br>
- $0 \leq n \leq 6$
- $1 \leq strlen(\text{name}_i) \leq 100$
- $\forall$ $1 \leq i \leq N$, $`\text{type}_i \in \text{\{ "monster", "spell", "trap" \}}`$
- $0 \leq \text{monsters} \leq 5$
- $0 \leq \text{sets} \leq 5$
## Sample Input ##
```
5
BlueEyesWhiteDragon
monster
0
MonsterReborn
spell
1
BlackMagicianGirl
monster
1
Fireball
spell
0
SkillDrain
trap
```
## Sample Output ##
```
hands:
Fireball
spell
monsters: 2
sets: 1
```
## Hints ##
1. yeah it's just double linked list
2. we love those who has patience to write hw
3. rands:
```c
int rands[200] = {1804289383, 846930886, 1681692777, 1714636915, 1957747793, 424238335, 719885386, 1649760492, 596516649, 1189641421, 1025202362, 1350490027, 783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426, 304089172, 1303455736, 35005211, 521595368, 294702567, 1726956429, 336465782, 861021530, 278722862, 233665123, 2145174067, 468703135, 1101513929, 1801979802, 1315634022, 635723058, 1369133069, 1125898167, 1059961393, 2089018456, 628175011, 1656478042, 1131176229, 1653377373, 859484421, 1914544919, 608413784, 756898537, 1734575198, 1973594324, 149798315, 2038664370, 1129566413, 184803526, 412776091, 1424268980, 1911759956, 749241873, 137806862, 42999170, 982906996, 135497281, 511702305, 2084420925, 1937477084, 1827336327, 572660336, 1159126505, 805750846, 1632621729, 1100661313, 1433925857, 1141616124, 84353895, 939819582, 2001100545, 1998898814, 1548233367, 610515434, 1585990364, 1374344043, 760313750, 1477171087, 356426808, 945117276, 1889947178, 1780695788, 709393584, 491705403, 1918502651, 752392754, 1474612399, 2053999932, 1264095060, 1411549676, 1843993368, 943947739, 1984210012, 855636226, 1749698586, 1469348094, 1956297539, 1036140795, 463480570, 2040651434, 1975960378, 317097467, 1892066601, 1376710097, 927612902, 1330573317, 603570492, 1687926652, 660260756, 959997301, 485560280, 402724286, 593209441, 1194953865, 894429689, 364228444, 1947346619, 221558440, 270744729, 1063958031, 1633108117, 2114738097, 2007905771, 1469834481, 822890675, 1610120709, 791698927, 631704567, 498777856, 1255179497, 524872353, 327254586, 1572276965, 269455306, 1703964683, 352406219, 1600028624, 160051528, 2040332871, 112805732, 1120048829, 378409503, 515530019, 1713258270, 1573363368, 1409959708, 2077486715, 1373226340, 1631518149, 200747796, 289700723, 1117142618, 168002245, 150122846, 439493451, 990892921, 1760243555, 1231192379, 1622597488, 111537764, 338888228, 2147469841, 438792350, 1911165193, 269441500, 2142757034, 116087764, 1869470124, 155324914, 8936987, 1982275856, 1275373743, 387346491, 350322227, 841148365, 1960709859, 1760281936, 771151432, 1186452551, 1244316437, 971899228, 1476153275, 213975407, 1139901474, 1626276121, 653468858, 2130794395, 1239036029, 1884661237, 1605908235, 1350573793, 76065818, 1605894428, 1789366143, 1987231011, 1875335928, 1784639529 }
```
## 解題思路 ##
- 依題目指示建`struct`包含指定成員並`typedef`
- `function load`裡是`for-loop i`到`size`，每次推入新的`card`就`new`分配新位址並將`end`的`next`指向該位址(`i = 0`時則直接將`head`和`end`指向該位址)
- `function push`裡是`new`分配新位址並將`end`的`next`指向該位址(`i = 0`時則直接將`head`和`end`指向該位址)並`cards -> size ++`
- `function draw`裡
1. 宣告`monsters`、`summoned`、`sets`、`reversed`紀錄以及記錄手牌的`linked list: hand`
2. 建立`for-loop i = 0 to size - 1 && hand.size < 6`，每當抽到的卡是
- `monster`、`effect = 0`且`summoned = 0`、`monsters < 5`則不輸出並`summoned++`, `monsters ++`
- `monster`、`effect = 1`且 `monsters < 5`則不輸出並`monsters ++`
- `spell`、`effect = 1`且 `size - i > 1`、`sets < 5`則不輸出並`reversed = 1`, `swap(cards.head, cards.end)`
- `spell`、`effect = 0`且 `hand.size > 0`、`sets < 5`則不輸出並`hand.head = hand.hand -> next`, `hand.size --`
- `trap`且`sets < 5`則不輸出且`sets++`
- 以上都未能達到則`push`進`hand`裡
3. 輸出`hands:\n`後`for-loop i = 0 to hand.size - 1`輸出手牌內容
4. 輸出`monsters: [monsters]\n`和`sets: [sets]\n`
## 解法 ##
### hands.c
```c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hands.h"
void load(deck *cards, int size, int card_type(char *str)){
char input[8];
for(int i = 0; i < size; i++){
card *cur = (card *)malloc(sizeof(card));
cur -> next = NULL;
scanf("%s", cur -> name);
scanf("%s", input);
cur -> type = card_type(input);
if(cur -> type < 2)
scanf("%d", &(cur -> effect));
if(!i){
cards -> head = cur;
cards -> end = cur;
}
else{
cards -> end -> next = cur;
cur -> pre = cards -> end;
cards -> end = cur;
}
}
}
void push(deck *cards, char *name, int type){
//printf("push into hands\n%s\n%d\n", name, type);
card *cur = (card *)malloc(sizeof(card));
cur -> next = NULL;
cur -> pre = NULL;
strcpy(cur -> name, name);
cur -> type = type;
if(!cards -> size)
cards -> head = cur;
else{
cards -> end -> next = cur;
cur -> pre = cards -> end;
}
cards -> end = cur;
cards -> size ++;
}
void draw(deck *cards, int size){
int summoned = 0, monsters = 0, sets = 0, reversed = 0;
card *cur = cards -> head;
deck hand;
hand.size = 0;
cards -> head = cur -> next;
for(int i = 0; i < size && hand.size < 6; i++){
//printf("now:\n%s\n%d\n", cur->name, cur->type);
if(!cur -> type){
if(monsters < 5 && cur -> effect)
monsters ++;
else if(monsters < 5 && !summoned){
summoned = 1;
monsters ++;
}
else
push(&hand, cur -> name, cur -> type);
}
else if(cur -> type > 1){
if(sets < 5)sets ++;
else
push(&hand, cur -> name, cur -> type);
}
else{
if(sets >= 5)
push(&hand, cur -> name, cur -> type);
else if(cur -> effect){
if(size - i > 1){
card *tmp = cards -> head;
cards -> head = cards -> end;
cards -> end = tmp;
/*for(int j = 1; j < size - i && tmp != NULL; j++){
card *tmp2 = tmp -> next;
if(j == 1)tmp -> next = NULL;
else tmp -> next = tmp -> pre;
if(j == size - i - 1)tmp -> pre = NULL;
else tmp -> pre = tmp2;
tmp = tmp2;
}*/
reversed = !reversed;
}
else
push(&hand, cur -> name, cur -> type);
}
else{
if(hand.size){
hand.head = hand.head -> next;
hand.size --;
}
else
push(&hand, cur -> name, cur -> type);
}
}
cur = cards -> head;
if(reversed)
cards -> head = cur -> pre;
else
//if(cur != NULL)
cards -> head = cur -> next;
}
printf("hands:\n");
card *tmp = hand.head;
for(int i = 0 ; i < hand.size; i++){
printf("%s\n", tmp -> name);
if(!tmp -> type)
printf("%s\n", "monster");
else if(tmp -> type == 1)
printf("%s\n", "spell");
else
printf("%s\n", "trap");
tmp = tmp -> next;
}
printf("monsters: %d\n", monsters);
printf("sets: %d\n", sets);
}
```
### hands.h
```c=
typedef struct Card{
char name[100];
int type; //0: monster, 1: spell, 2: trap
int effect;
//if monster: 1/0 = can/can't be special summoned
//if spell : 1/0 = reverse/swap
struct Card *next, *pre;
} card;
typedef struct Deck{
int size;
card *head, *end;
} deck;
void load(deck *cards, int size, int card_type(char *str));
void draw(deck *cards, int size);
```
## 測資說明
測資1, 2: $2\leq N\leq 20$，no spell
<br>
測資3: $2 \leq N \leq 20$
<br>
測資4 \~ 7: $20\leq N\leq 1000$
<br>
測資8, 9: $1000\leq N\leq 10000$
## 小組回饋
<table border="1">
<tr>
<th>你們的小組編號</th>
<th>題目敘述是否明確、清楚？如有不足怎麼寫會更清楚？</th>
<th>選題是否切合當週主題？如果沒有是哪裡不符合？</th>
<th>出題組找的解題技巧是否對你們這組做作業時有幫助？補充說明(選填)</th>
<th>出題組的解法好不好？是否有更好的解法或語法？</th>
<th>測資是否完善？如有不足如何可以改善得更好？</th>
<th>給出題組的額外建議</th>
</tr>
<tr>
<td>Group10-1</td>
<td>有些說明的地方沒有用好，還是
顯示\lt 6 之類的</td>
<td>選題切合主題，以stucture包裹住
題目內容，符合概念</td>
<td>double linked list 不知道是不是這
堂課應該學的東西...
</td>
<td>double linked list 不知道是不是這
堂課應該學的東西...但以這題而
言似乎非用linked list不可</td>
<td>測資完善，大小⾧短皆有，範例
測資也足夠⾧讓人debug</td>
<td>可以加上英文敘述以及真的要把
mrakdown數學式子的部分處理
好。
</td>
</tr>
<tr>
<td>Group1-2</td>
<td>是</td>
<td>是</td>
<td>是</td>
<td>好</td>
<td>是</td>
<td>辛苦了</td>
</tr>
<tr>
<td>Group2-1</td>
<td>第二題的題敘很多＄不知道是不
是打錯？</td>
<td>是</td>
<td></td>
<td>好</td>
<td>還蠻完善的</td>
<td>無</td>
</tr>
<tr>
<td>Group2-2 </td>
<td>題目有趣且切合主題</td>
<td>符合</td>
<td>有幫助</td>
<td>好 </td>
<td>完善</td>
<td>無
</td>
</tr>
<tr>
<td>Group2-3
</td>
<td>main function架構可讀性不佳，
題敘數學表示式格式未正確顯
示。
</td>
<td>符合，但建議若main function已
經使用到structure的member的話
，就把structure也附上就好了，
讓同學們另外再寫㇐遍意義不
大。 </td>
<td></td>
<td>解法正確，但可讀性可再加強</td>
<td>完善</td>
<td>不需要寫太多註解，把程式架構
寫清楚、變數名稱取好、函式介
面設計乾淨㇐點就好了，更不用
寫像是don't be scared of
card_type這種和題目無關的話。
例如:
(1)card_type()中使用strcmp()來
區別三種type，雖然結果是對的
，但這樣寫的可讀性和可擴充性
都不好。
(2)第㇐題main 宣告了unused
variable arr[3]
(3)第㇐題classify()的argument可
以傳classified㇐個pointer to
pointer就好了，不需要傳三個
pointer
整體來說格式(數學表示式未正確
顯示)要花不少時間讀懂出題者的
spaghetti code這點都有影響到作
答的順暢度。
但看的出來是有用心設計的題目
，加油。
</td>
</tr>
<tr>
<td>Group3-2
</td>
<td>題目敘述很清楚，變數範圍寫的
很明確2</td>
<td>第㇐題若不是main.c的限制，不
然也可以不用struct就寫出來，第
二題很棒</td>
<td></td>
<td>很棒</td>
<td>測資有很好~謝謝第二題還用心給
了rands</td>
<td>沒有</td>
</tr>
<tr>
<td>Group3-3</td>
<td>可以更加詳細解說第二題裡要實
作的兩個函式的功能</td>
<td>相當符合</td>
<td></td>
<td>範例解法相當好</td>
<td>相當完善</td>
<td>可使題目看上去更加直觀</td>
</tr>
<tr>
<td>Group4-1</td>
<td>有些地方是latex的形式，使得閱
讀困難、第二題可以更仔細的說
明各個函式的功能</td>
<td>切合，有用struct儲存資料，還有
用到linked list</td>
<td></td>
<td>解法標準，就是照題序㇐步㇐步
做 </td>
<td>每個case都有測到</td>
<td>建議把題目的latex指令改成符號(\lt -> 小於符號)</td>
</tr>
<tr>
<td>Group4-3 </td>
<td>非常明確，而且超級有趣！！！</td>
<td>很符合主題～</td>
<td>我覺得解題技巧給我很大的幫助</td>
<td>很好～</td>
<td>很完善</td>
<td>很希歡你們的題目，成功勾起了
我小時候的回憶！</td>
</tr>
<tr>
<td>Group5-1</td>
<td>題目敘述清楚。</td>
<td>切合。</td>
<td></td>
<td>好。 </td>
<td>測資完善。</td>
<td>無</td>
</tr>
<tr>
<td>Group5-3</td>
<td>明確，有給懶人包，貼心！</td>
<td>是 </td>
<td></td>
<td>看起來還可以</td>
<td>Q2也許可以加㇐筆N==1</td>
<td>排版跑掉了</td>
</tr>
<tr>
<td>Group6-1</td>
<td>明確</td>
<td>切合</td>
<td></td>
<td>好</td>
<td>完善</td>
<td>遊戲王題目滿讚的，有想起童年
回憶</td>
</tr>
<tr>
<td>Group6-2</td>
<td>沒問題</td>
<td>卡牌遊戲的出題想法，以及相關
的自訂操作，我覺得很適合這週
的主題 </td>
<td></td>
<td>我認為恰到好處</td>
<td>這部分沒問題</td>
<td>無</td>
</tr>
<tr>
<td>Group6-3
</td>
<td>可以強調"手牌不足6張時抽㇐張
牌，所以手牌的最大數量為6"，
以及"魔法卡與陷阱卡共用同5個
格子"。 </td>
<td>是</td>
<td></td>
<td>可</td>
<td>完善</td>
<td>題目有點難理解，WA數次才正確
理解題意</td>
</tr>
<tr>
<td>Group7-2 </td>
<td>蠻明確的</td>
<td>是，符合</td>
<td></td>
<td>蠻好的</td>
<td>是</td>
<td>我覺得蠻好的</td>
</tr>
<tr>
<td>Group7-3 </td>
<td>清楚，還有懶人包</td>
<td>切合，排組很適合用結構儲存</td>
<td></td>
<td>好，能幫助我正確完成</td>
<td>完善</td>
<td>遊戲王讚</td>
</tr>
<tr>
<td>Group8-1 </td>
<td>明確而且滿有趣的</td>
<td>非常切合</td>
<td></td>
<td>沒看到特別的問題點</td>
<td>完善
</td>
<td>沒有，滿有趣的題目，也可以練
習到struct的應用</td>
</tr>
<tr>
<td>Group8-2</td>
<td>題目邏輯清晰有創意，十分明確</td>
<td>符合，會用到結構</td>
<td>有。看完就知道如何解題</td>
<td>非常好。
沒有</td>
<td>是，看起來各種狀況都有兼顧到
，非常完善。</td>
<td>圖解很棒</td>
</tr>
<tr>
<td>Group8-3</td>
<td>Q2
1. 懶人包的 "若是怪獸卡且還沒
有用掉通常召喚機會則可以通常
召喚他" 應該還要加㇐個條件 "還
有空的怪獸格" ，這是根據上上段
寫的規則。
2. 希望可以說明每回合能做的四
件事有沒有限定判斷的順序。對
於不了解遊戲王的人，看完規則
介紹後可能會對㇐些 case 有疑問
，例如：有多張能用的牌，要依
照什麼順序使用，或是手牌數 < 6
且有牌能用，可不可以不使用牌
就先抽牌......。要看到這題的初始
手牌數為 0 ，且只有㇐回合，才
能刪掉大部分有疑問的 case 。假
設小考題會出現類似上方的 case
，建議把 "每回合能做的事的順
序" 說得更明確。
3. output format 的行序改用類似
Q1 input format 的相對行序（像
是 "每張卡佔兩行，第㇐行是...，
第二行是..." ）可能會比較容易理
解。 </td>
<td>是</td>
<td></td>
<td>好</td>
<td>是</td>
<td>1. 括號沒有成功顯示。
2. Q2 hints 宣告 rands 的時候忘
記寫分號了。
</td>
</tr>
<tr>
<td>Group9-1</td>
<td>有㇐點點不明確，但是還可以理
解</td>
<td>頗切合的</td>
<td></td>
<td>我覺得是很厲害的解法</td>
<td>蠻完善的</td>
<td>無</td>
</tr>
<tr>
<td>Group9-2</td>
<td>明確 </td>
<td>非常切合</td>
<td>非常有幫助</td>
<td>非常好</td>
<td>非常完善</td>
<td>無</td>
</table>
## 分工
- 題目 + 解法 + 測資: 陳冠辰
- 驗題: 林柏佑
- 上台報告 + ppt: 郭秉翔 & 吳松頤
- 出題報告: 王舜盈
## Reference
- markdown
syntax<br>https://hackmd.io/c/codimd-documentation/%2F%40codimd%2Fmarkdown-syntax
- hackmd
tutorial<br>https://hackmd.io/c/tutorials-tw/%2Fs%2Fhow-to-use-code-blocks-tw
Sign in with Wallet
Connect another wallet