# 學科能力複試筆記
* ### [題目(嘉義高中)](https://hackmd.io/@cube/HyxueFBi4#%E4%BA%8C%E3%80%81%E5%8F%B0%E4%B8%AD%E5%8D%80)
* ### [各科題目含一些測資(嘉義高中)](https://www.cysh.cy.edu.tw/files/11-1001-629.php)
* ### [測站(台中女中)](http://tcgs.tc.edu.tw:1218/Problems?tab=tab03)
## 中區105年
### 1.計算字串間隔距離
> 給定一個由大小寫英文字母所組成的字串以及一個英文字母，請輸出字母在字串中出現的間隔距離。
> 輸入說明 ：
> 第一行為一個由大小寫字母所組成的長字串，字串長度為n(2≤n≤100)。
> 第二行為一個英文字母，代表要計算間隔距離的字母，且該字母在長字串中必至少不分大小寫地出現兩次(含)以上。
> 輸出說明 ：
> 不分大小寫，列出該字母在此長字串中出現的間隔距離（距離間以一個空白字元分開）。
>
> 範例1輸入：
> ABCDAAEFeDaBDCBCBcBCbCBBd
> A
> 範例1輸出：
> 4 1 5
>
> 範例2輸入：
> ABCDAAEFeDaBDCBCBcBCbCBBd
> d
> 範例2輸出：
> 6 3 12

---

**比賽測資:**

>
> **input:**
> hcjhCJKHKhcHChCHKCHCYUGCJ
> h
> **output:**
> 3 4 2 2 2 2 3
>
> **input:**
> cksSCjslklsLHCHSLclLCHshl
> S
> **output:**
> 1 3 4 5 7
>
> **input:**
> hcjhCJKHKhcHChCHKCHCYUGCJ
> c
> **output:**
> 3 6 2 2 3 2 4
>
> **input:**
> YOCHXcemfxCmNXcshdlkdmXCexg
> c
> **output:**
> 3 5 4 9

#include<bits/stdc++.h>
using namespace std;
int main(){
    string line;
    cin>>line;
    for(auto &s:line) s=toupper(s); //注意參照用法，和char專用的toupper()
    char c;
    cin>>c;
    c=toupper(c);
    int d=-1;
    //cout<<line<<" "<<c<<endl;
    for(int i=0;i<line.length();i++){
        if(d==-1&&line[i]==c) d=i;
        else if(line[i]==c) {
            cout<<i-d<<" ";
            d=i;
        }
    }
}

### 2.同字母字串列最寬排版

> 給定n個由英文大寫字母所構成之字串S1,S2,S3…,Sn，且其中任一字串Sa必可找到與其有至少一字母相同之字串Sb (a!=b )。輸出時，每行印出一個字串，並將上一行與下一行字串之間相同的字母上下對齊，由左向右延伸，並計算出整體排版寬度最寬的字串排列方式來列印。(若最寬之排列方式不只一種，則將多種排列方式進行字串排序值比較，例如 : 最寬之排列為兩種，S2-S5-S4-S3-S1 與 S2-S5-S3-S4-S1，根據字串排序值，前者值為 25431 後者為 25341，而25431 > 25341，所以輸出S2-S5-S4-S3-S1 之排列)。
> 輸入說明 ：
> 第一行為一個正整數 n (n≤10)，代表接下來有 n 行輸入。
> 接下來 共有n行，每一行是一個字串，每一個字串皆由大寫英文字母所組成。
> 輸出說明 ：
> 每行印出一個字串，並將上一行與下一行字串之間相同的字母上下對齊，由左向右延伸，並計算出整體排版寬度最寬的字串排列方式來列印。若最寬之排列方式不只一種，則將多種排列方式進行字串排序值進行比較，選擇字串值排序值最大者輸出。若一個排列方法有多個對齊方法，請讓後項盡量往右邊靠。
>
> 範例輸入 ：
> 5
> CBAKM
> KDMF
> KCDDFMS
> WSRC
> PW
> 範例輸出 ：
> ```
> PW
> WSRC
> CBAKM
> KCDDFMS
> KDMF
> ```
> 範例說明：
> 在以上的範例中，最後兩個字串可以選擇對齊多個字母，但是為了符合輸出要求，選擇對齊字母 M。
---

**比賽測資:**

>
> **input:**
> 5
FDE
ABCD
EPLUW
UCKMPOU
OYREAWD
> **output:**
> ```
> ABCD
> FDE
> EPLUW
> UCKMPOU
> OYREAWD
> ```
>
> **input:**
> 6
FDE
ABCD
EPLUW
QICL
UCKMPOU
OYREAWQ
> **output:**
> ```
> ABCD
> FDE
> EPLUW
> UCKMPOU
> OYREAWQ
> QICL
> ```
> **input:**
> 6
> CPZ
> ZOJKM
> FDE
> EPLUW
> QICL
> WYREARQ
> **output:**
> ```
> FDE
> EPLUW
> WYREARQ
> QICL
> CPZ
> ZOJKM
> ```
>
> **input:**
> 4
> ABCD
> DEFG
> FAKSHNQP
> KHZQP
> **output:**
> ```
> ABCD
> DEFG
> FAKSHNQP
> KHCQP
> ```

**原題意和新版compiler:accept: 接受之作法，如下:**

#include<bits/stdc++.h>
using namespace std;
struct item {
    vector<int> indexs,slen;//slen=spacelen
    int len=0,indexnum=0;
};
int main() {
    int n=0;
    cin>>n;
    vector<string> line(n+1);
    int factorial=1;
    for(int i=1; i<=n; i++)
        factorial*=i;
    //cout<<factorial<<endl;
    item *allP=new item [factorial];
    //vector<vector<int>> indexList;
    vector<int> tmp,pairList;
    for(int i=1; i<=n; i++) {
        cin>>line[i];
        tmp.push_back(i);
    }
    int i=0;
    do {
        allP[i].indexs.assign(tmp.begin(),tmp.end());
        for(int j=0; j<n; j++)
            allP[i].indexnum+=allP[i].indexs[j]*pow(10,5-j);
        allP[i].indexnum=allP[i].indexnum/10;
        i++;
    } while(next_permutation(tmp.begin(),tmp.end()));
    /*for(int i=0;i<factorial;i++){
        for(int j=0;j<n;j++) cout<<allP[i].indexs[j]<<" ";
        cout<<allP[i].indexnum<<endl;
    }*/
    for(int i=0; i<factorial; i++) {
        vector<string> tmpLine;
        for(int j=0; j<n; j++) {
            tmpLine.push_back(line[allP[i].indexs[j]]);
        }
        for(int j=0; j<n-1; j++) {
            int spaces=0;
            vector<int> spacesList;
            for(int k=0; k<tmpLine[j].length(); k++) {
                for(int x=tmpLine[j+1].length()-1; x>-1; x--) {
                    //cout<<tmpLine[j+1][x]<<" ";
                    if(tmpLine[j][k]==tmpLine[j+1][x]) {
                        spaces=k-x;
                        spacesList.push_back(spaces);
                    }
                }
            }
            if(!spacesList.empty()) {
                sort(spacesList.begin(),spacesList.end());
                reverse(spacesList.begin(),spacesList.end());
                spaces=spacesList[0];
            }else{
                spaces=-10000;
            }
            allP[i].slen.push_back(spaces);
            allP[i].len+=spaces;
            //cout<<endl<<tmpLine[j]<<" "<<tmpLine[j+1]<<" "<<spaces<<endl;
        }
        //cout<<endl;
        allP[i].len+=tmpLine[n-1].length();
        //cout<<allP[i].len<<endl<<endl;
    }
    sort(allP,allP+factorial,[](item f,item s) {
        if(f.len==s.len)
            return f.indexnum<s.indexnum;
        else
            return f.len<s.len;
    });
/*     for(int i=0;i<factorial;i++) {
 *         cout<<allP[i].len<<" "<<allP[i].indexnum<<endl;
 *     }
 */
    int spaces=0;
    cout<<line[allP[factorial-1].indexs[0]]<<endl;
    for(int i=1;i<n;i++){
        spaces+=allP[factorial-1].slen[i-1];
        for(int j=0;j<spaces;j++) cout<<" ";
        cout<<line[allP[factorial-1].indexs[i]]<<endl;
    }
}

GreenJudge :100: :

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
struct item {
    vector<int> indexs,slen;//slen=spacelen
    int len,indexnum;
};
bool cmp(item f,item s) {
    if(f.len==s.len)
        return f.indexnum<s.indexnum;
    else
        return f.len<s.len;
}
int main() {
    int n=0;
    cin>>n;
    vector<string> line(n+1);
    int factorial=1;
    for(int i=1; i<=n; i++)
        factorial*=i;
    //cout<<factorial<<endl;
    item *allP=new item [factorial];
    //vector<vector<int>> indexList;
    vector<int> tmp,pairList;
    for(int i=1; i<=n; i++) {
        cin>>line[i];
        tmp.push_back(i);
    }
    int i=0;
    do {
        allP[i].indexs.assign(tmp.begin(),tmp.end());
        allP[i].indexnum=0;
        allP[i].len=0;
        for(int j=0; j<n; j++)
            allP[i].indexnum+=allP[i].indexs[j]*pow(10,5-j);
        allP[i].indexnum=allP[i].indexnum/10;
        i++;
    } while(next_permutation(tmp.begin(),tmp.end()));
    /*for(int i=0;i<factorial;i++){
        for(int j=0;j<n;j++) cout<<allP[i].indexs[j]<<" ";
        cout<<allP[i].indexnum<<endl;
    }*/
    for(int i=0; i<factorial; i++) {
        vector<string> tmpLine;
        for(int j=0; j<n; j++) {
            tmpLine.push_back(line[allP[i].indexs[j]]);
        }
        for(int j=0; j<n-1; j++) {
            int spaces=0;
            vector<int> spacesList;
            for(int k=0; k<tmpLine[j].length(); k++) {
                for(int x=tmpLine[j+1].length()-1; x>-1; x--) {
                    //cout<<tmpLine[j+1][x]<<" ";
                    if(tmpLine[j][k]==tmpLine[j+1][x]) {
                        spaces=k-x;
                        spacesList.push_back(spaces);
                    }
                }
            }
            if(!spacesList.empty()) {
                sort(spacesList.begin(),spacesList.end());
                reverse(spacesList.begin(),spacesList.end());
                spaces=spacesList[0];
            } else {
                spaces=-10000;
            }
            allP[i].slen.push_back(spaces);
            allP[i].len+=spaces;
            //cout<<endl<<tmpLine[j]<<" "<<tmpLine[j+1]<<" "<<spaces<<endl;
        }
        //cout<<endl;
        allP[i].len+=tmpLine[n-1].length();
        //cout<<allP[i].len<<endl<<endl;
    }
    sort(allP,allP+factorial,cmp);
    /*     for(int i=0;i<factorial;i++) {
     *         cout<<allP[i].len<<" "<<allP[i].indexnum<<endl;
     *     }
     */
    int spaces=0;
    cout<<line[allP[factorial-1].indexs[0]]<<endl;
    for(int i=1; i<n; i++) {
        spaces+=allP[factorial-1].slen[i-1];
        for(int j=0; j<spaces; j++)
            cout<<"_";
        cout<<line[allP[factorial-1].indexs[i]]<<endl;
    }
}

### 3.指數2k的四個自然數平方和之所有表示法
> 請寫一程式找出將指數2^k^表示成四個正整數的平方和的所有表示法。例如當k=2時，可以表示為2^2^=1^2^+1^2^+1^2^+1^2^。這些正整數請以由小到大的順序列出，數字與數字中間以一個空格隔開；若無此種表示法，則輸出0。
> 輸入說明 ：
> 第一行為一個正整數n，代表接下來有n行輸入。
> 接下來共有n行，每一行有一個正整數k，表示這一筆測資需計算2^k^的表示法。
> 輸出說明 ：
> 對於每一筆測資，請輸出將指數2^k^表示成四個自然數的平方和的所有表示法，四個正整數請以由小到大的順序列出，數字間以一個空白字元區隔；若有多個可能請依照字典順序全部輸出；若沒有合法組合，則輸出0。
> 字典順序：從第一個字元開始進行比較，值小的先輸出，若第一個字元的值相當，則繼續比較下一個字元。
> 範例輸入 ：
> 2
> 2
> 3
> 範例輸出 ：
> 1 1 1 1
> 0
>

---

**比賽測資:**

>
> **input:**
> 2
6
12
> **output:**
> 4 4 4 4
32 32 32 32
>
>
> **input:**
> 2
5
19
> **output:**
> 0
0
>
> **input:**
> 2
12
14
> **output:**
> 32 32 32 32
64 64 64 64
>
> **input:**
> 5
5
6
12
14
18
> **output:**
> 0
4 4 4 4
32 32 32 32
64 64 64 64
256 256 256 256

---
> 提示如下 :
> 2^k^=2^2^*2^k/2-1^

#include<iostream>  
#include<math.h>  
using namespace std;  
int main() {  
    int n=0;  
    cin>>n;  
    for(int i=0; i<n; i++) {  
        int k=0;  
        cin>>k;  
        if(k%2) {  
            cout<<0<<endl;  
            continue;  
        }  
        for(int j=0; j<4; j++) {  
            cout<<pow(2,(k/2-1))<<" ";  
        }  
        cout<<endl;  
    }  
}  

### 4.排隊

> 有一家新開張速食店，客人到店內消費採先到先服務(First in first out)的順序，每一個顧客都很有耐心，只要開始排隊了就一定會排到吃到餐點為止，而且客人不會插隊。老闆為了瞭解一天之內，來店消費顧客其排隊隊伍最長為多長(正在被服務者不算入等待隊伍長度內)，特別委請你設計一程式來幫他計算。
> 假定客人進來排隊的時間以及每個人被服務的時間都是預先知道的，同時一個時間只能服務一個客人。現在給你一群顧客進來消費的時間資料，請計算此店的服務排隊隊伍最長為多少。
> 輸入說明 ：
> 第一行為一個正整數 n ，代表客人數量。
> 接下來共有 n 行，每一行有兩個整數q及s，分別代表客人的來店排隊的時間點以及需要被服務的時間。
> 其中，0<q≤1000、0<s≤1000且輸入以 q 排序（意即依照來店時間點的先後順序輸入）。
> 輸出說明 ：
> 輸出一個整數，代表隊伍最長的長度(正在被服務者不算入等待隊伍長度內)。如範例1，第一個客人來店時不需排隊，之後兩個客人到達時，因為第一個客人尚未服務完畢，因此該筆測資最長的隊伍長度為 2 。
>
> 範例1輸入 ：
> 3
> 1 10
> 2 5
> 3 1
> 範例1輸出 ：
> 2
>
> 範例2輸入 ：
> 3
> 1 2
> 2 3
> 5 1
> 範例2輸出 ：
> 1
>

---

**比賽測資:**

>
> **input:**
> 10
0 1
0 1
1 4
1 4
2 4
3 4
3 2
4 4
5 5
8 5
> **output:**
> 6
>
> **input:**
> 25
0 1
0 2
0 2
1 2
3 2
5 2
8 3
9 3
9 1
9 3
9 1
10 3
11 2
12 3
13 1
13 2
13 1
13 2
15 3
15 1
17 2
18 1
18 1
19 1
20 1
> **output:**
> 15
>
> **input:**
> 100
7 5
9 3
22 4
47 4
48 5
72 3
92 4
109 1
112 5
137 2
139 2
146 4
162 3
166 4
167 5
220 4
251 4
262 1
275 2
275 2
285 2
290 1
292 3
292 2
317 2
347 2
350 2
365 4
380 5
383 5
409 2
424 2
455 2
458 1
460 5
466 4
478 2
498 1
499 1
504 2
508 2
518 3
519 1
530 4
532 5
536 4
540 2
557 2
558 4
565 4
574 5
588 4
609 3
616 1
620 5
627 3
631 1
635 3
660 3
672 1
676 4
679 5
702 5
713 2
726 2
730 2
733 3
736 3
761 4
781 2
783 4
795 4
797 3
816 2
831 3
835 3
845 3
857 2
862 4
865 2
866 2
867 2
885 4
890 2
898 2
901 4
903 1
906 3
919 2
934 1
942 3
952 2
955 5
965 4
977 3
980 4
982 5
986 4
991 5
992 3
> **output:**
> 2
>
> **input:**
> 100
2 8
20 8
27 8
30 10
31 6
35 2
43 5
53 1
75 5
82 6
82 1
96 1
104 1
132 7
134 4
141 3
149 10
174 5
193 1
198 4
206 8
211 9
214 5
216 2
224 2
250 1
271 8
312 4
322 8
328 3
328 9
338 2
365 6
367 6
369 7
385 3
388 6
390 1
394 7
395 9
399 4
405 7
406 10
415 6
416 3
419 2
432 3
472 8
486 9
498 5
503 8
519 5
522 8
529 10
548 5
552 8
562 5
580 8
583 10
589 7
598 9
600 3
609 1
629 7
634 3
644 6
666 8
696 4
699 6
711 2
715 10
730 6
736 10
736 2
742 6
744 10
754 8
757 5
786 10
787 9
800 8
801 3
810 5
829 4
834 10
847 5
859 2
867 10
871 8
872 6
877 5
886 5
909 5
917 2
926 5
930 7
948 2
953 2
973 2
988 1
> **output:**
> 4
>
GreenJudge :100: :

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n=0,time=0,maxQueueLen=0,queueLen=0,arriveT=0,serviceT=0;
    cin>>n;
    int *finishT=new int[n];
    for(int i=0; i<n; i++) {
        queueLen=i;
        cin>>arriveT>>serviceT;
        for(int j=0; j<i; j++) {
            if(arriveT>finishT[j])
                queueLen-=1;
        }
        if(time<=arriveT)
            time=arriveT+serviceT;
        else
            time+=serviceT;
        finishT[i]=time;
        if(queueLen>maxQueueLen)
            maxQueueLen=queueLen;
    }
    cout<<maxQueueLen<<endl;
}

### 5.解密

>對於英文句子，我們可以發現，若我們保留句中每一個單字頭尾的字母不動但將中間的字母任意打亂，我們還是可以很容易的識別出該英文句子中每個字的原始意義，例如 “tihs snetncee mkaes prfecet sesne”此例句中的每個單字大部分的人應該不難看出是 “this sentence makes perfect sense”；同樣的若我們將句子中的空格都移除把所有單字都串起來，也不難看出該句子的原始意義，例如 “thissentencemakesperfectsense”就是一個好的範例，然而若我們將一個句子依序做了以上兩種處裡(先打亂再移除空格)，那要將原始句子中的單字都正確找出就不是一件容易的事，例如以下的字串就不容易還原成原來正確句子 “tihssnetnceemkaesprfecetsesne”
> 給定一個經過上述處理所得的字串以及一些字串中所用的單字所形成的字典，請寫一程式將字串解密成原來的句子。
>
> 輸入說明：
> 第一行為一個正整數 n (n≤100)，代表接下來有 n 組測資。
> 每一組測資的開頭為一行任意打亂的英文句子（一個連續的小寫英文字母字串，其長度不大於 1000），下一行為一個正整數 k，代表該組測資的字典有 k (k≤100) 個單字。接下來的 k 行，每行會有一個單字（一個連續的小寫英文字母字串，其長度不大於 100）。
>
> 輸出說明：
> 每一組測資請輸出一行結果。
> 若根據字典內容，句子僅有一種解碼方式，則輸出解碼後的句子，單字間以一個空白字元分隔；若句子有多種解碼方式則輸出1；若句子無法解碼則輸出-1。
>
> **範例輸入：**
> 3
> tihssnetnceemkaesprfecetsesne
> 5
> makes
> perfect
> sense
> sentence
> this
> hitehre
> 2
> there
> hello
> hitehre
> 3
> hi
> there
> three
>
> **範例輸出：**
> this sentence makes perfect sense
> -1
> 1
>
---

**比賽測資:**

>
> **input:**
> 2
daedmentlelnotleas
6
tales
no
men
tell
tlel
dead
mseriylveoscpmonay
3
loves
misery
company
> **output:**
> 1
misery loves company
>
>
> **input:**
>2
goodceusonlnveercmoesasims
5
amiss
comes
good
counsel
always
pcctiarewahtyoupcareh
4
you
practice
preach
what
>
> **output:**
> 1
practice what you preach
>
> **input:**
> 1
gtaehryourobduseswilhemay
5
you
while
may
rosebuds
gather
>
> **output:**
> gather you rosebuds while may
>
> **input:**
> 1
erveymanhashisttsae
5
man
has
every
taste
his
>
> **output:**
> every man has his taste
>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        int va=0;//vocabularyAmount
        string ds;//decodingString
        cin>>ds>>va;
        vector<string> oe(va);//OriginElement
        vector<int> elements(va);
        vector<int> finalOrder;
        for(int j=0; j<va; j++) {
            cin>>oe[j];
            elements[j]=j;
        }
        int pairTimes=0;
        do {
//            for(auto item:elements)
//                cout<<item<<" ";
//            cout<<endl;
            int index=0;
            string tmpResultString;
            for(int j=0; j<va; j++) {
                string tmp=oe[elements[j]];
                sort(tmp.begin(),tmp.end());
                do {
                    if(ds.substr(index,tmp.length())==tmp) {
                        index+=tmp.length();
                        if(index-1==ds.length()) break;
                        tmpResultString+=tmp;
                        break;
                    }
                    //cout<<ds.substr(index,tmp.length())<<" "<<tmp<<" ";
                } while(next_permutation(tmp.begin(),tmp.end())); //對STRING做枚舉
            }
            //cout<<tmpResultString<<endl;
            if(tmpResultString==ds) {
                pairTimes+=1;
                finalOrder=elements;
            }
        } while(next_permutation(elements.begin(),elements.end())); //對VECTOR<int>做枚舉
        if(pairTimes==0)
            cout<<-1<<endl;
        else if(pairTimes>1)
            cout<<1<<endl;
        else {
            for(int k=0; k<va; k++)
                cout<<oe[finalOrder[k]]<<" ";
            cout<<endl;
        }
    }
}

// 2D vector initial => vector<vector<int>>v(10,vector<int>(11,100));

### 6.特殊格式字串XYX辨識與出現次數累計
> 寫一個程式來辨識特殊格式的字串XYX(長度3，頭尾兩個字母相同，其中X與Y可以是任意的英文字母)，並輸出其出現的次數。輸入兩個字串，第一個字串是目標字串所以必須是長度3且頭尾相同，第二個字串則是長度介於3到1000之間的樣本字串。注意重疊的目標是可以被允許的而且次數都需要累計。例如，在樣本字串XLBLBLBLY 中，包含了3 次的目標字串LBL 而非2次而已。
>
> 輸入說明：
> 第一行為一個正整數n，代表接下來有n組測資。
> 每一組測資由兩行組成，第一行為目標字串，第二行為樣本字串。
> 其中，樣本字串的長度不大於1000 ，所有字串僅包含大寫英文字母。
> 輸出說明：
> 輸出目標字串的出現次數，當目標字串格式錯誤時，請輸出-1。
>
> 範例輸入：
> 2
> LPL
> BEGINTHELLPPLPLXYXYXYPLPLPLPLPLLPLEND
> LKK
> BEGINLKKLKKKLKEND
>
> 範例輸出：
> 6
> -1
---

**比賽測資:**

>
> **input:**
> 2
AAA
AAAAAAAAAA
ABC
CONFAPONFNONANF
> **output:**
> 8
-1
>
>
> **input:**
> 10
SSS
SSSSSSESSQSSYFSSSSSOSSSSSSSSSSP
NHN
HNNHPNHNINHNHNNHBNHHNXNHNDHNHNNHNKNHNJNHNNHN
VZV
ZVKUFZVVZVQVZSVZVZVZVVZXRUZVVZVZV
CXC
CXCFCXIXCXHXXC
III
IIIIIIIIIIIIIIIIIII
XNX
ZOPA
UUU
UUUUUUULQUUUUIUUUUUUUUUUUUNUUUUULQPUUAIUU
NNN
NNXNNTNNNNNNNN
UUU
UUUUYUUGRUUPJSUUUUU
DDD
DDPODDVDDDDADDDDDDDDDDDDDDDDDUDDQJDDDDDDDDDDD
> **output:**
> 15
9
6
1
17
0
20
6
5
26
>
> **input:**
> 3
PLP
PLPOLPLHJKMKIJHPLPHLP
AKAA
AKJIAKEAKEKFOAKAAKAK
LKL
BEGINLKLLKLKLKELD
> **output:**
> 2
-1
3
>
> **input:**
> 50
PBP
PBUPBPBPBPPBPPPBPMRBPZPBQAPBPBJPBPPBPBPPBBPBGPIPBZPBPBRQBPBPPBBPBELPBPDPBVLWV
WWW
WWWWWWWWWWWWYWWPWWWWWWWWEWWWWWFWWGOYWWXTPMWWWWWZWWVRWWWWWWZWWHTWWWXWWEWWWWWJ
JHJ
JHIHJJHJHZIJHEJHJYJHUJBJHJJHMJHJJJHGJHJHBJHJJHJHJIJHJQBYHJHJ
APA
GAPPAPAAPAAPCAPLPAAPAPAAPAPAAPAPAAPJAPV
VVV
VVVHVVPRFVVVVPVVVEVVLFVVPVVVVVVVVVD
MMM
MMMDUMMMMDMMMPMMVMMMM
OUO
UOXUOOUOUOOUUOOUOOUOOUHCOUUOOUOUOHOUNVOUOOUOOUOOUOYOUSOUOUMOUPOUOOUOUOUGOUOUO
HJH
HJZVHJHHJHJHHJIJHVOHJJHJHJHHJHJHPUHJHHJMHJHHJBHJTJHCHJHHJUUKHJHHJJHN
MAM
MAMAMAMXMAFMAR
NEN
NEQSNEWCENNENENTENNEN
YYY
YYYYYYYYYYYYYHYYBYYYYYYYYYYYYSYYKYYUYYYYEYYUCYYBYYYYY
PXP
PXEXPPXPXPIHPXPXPPXLPXPXPGOXPXPPXPXPPXEXPXPPXWPXPXPXPGDPXPXPXPPXPXHPSPXVPXP
HQH
HQCPKHQHQXEQHHQQHHQHHQUHQHHQYHQHYHQHHQ
LRL
LRYLRQWLRIRLLRKRLHLRLYSLRLLRLLRNKLRLRLLRMLRLLRGLRL
RKR
RKRRKERKRRKKRRKRRKRUKRKRKYRKUKRLRKRRKDRKRTQRKZRKKRRKRKKRRKRRKRKRRKRKRRKRQRKBRKBARRKRVKRRKR
AQA
AQKQAAQAQAQAAQAAQAQUAQAOQAAQEAQFQAAQAQAAQAQADAQAAQMQAAQAAQUEQAAQAAQLAQN
BBB
BBBBBBBBBBBBBTBBBBBMBBBBBBB
KKK
RKKKKKKKKKZKKVCPKKACKKCKKKKKKKKDKKCKKKKKKKRKKRKKKKHKKKKKKKKKJKKKJKKCKKKNLKKVIMBKKSOEX
YWY
YWYWGNWYYWYYWWYVYWEWYYWWSYWYWFFWYCYWYWYWYYWMCLYWYYWYYWYWWYWYWYLWYWQSTAWYYWYYYWY
DED
DEDDEEDEDDEDEWEDXWIDEDEDEDSCDEDDDEAEDEDKDEXEDSDEDELDEDEDDEEDE
KAK
AKKAKKAKAKAKAKJGKAKAKKAZKANEAKAKKAKWBKAK
EKE
EKYEKMKEEKKEWEKOKEFQEKEKEEKUKEUQEKEYLEKBEKEKEEKKEEKEKEEKUEKKEKEEKEKECEKEEKCOKEKEEKHEKUUEKQB
AXA
AXXAAXAXAXAXAMXAXAXAXKXAAXAXAXABAXAYAXU
BBB
BBBBBBBBBBBBXBBBBBBBBBBBBBBBBQBBWBBDLBBBBBBBBBGBBBJBBBBWBBBBBBBBBBBBBB
EAE
JAEEAACEAPEAEEAMVEAEEAEBAEAENAEDANAEEAEGEA
BOB
GBORLCIBORZBOBOBBOB
QHQ
DQHCQHBQHBHQQHAQHG
XYX
RYXWLYXXXYXKXYYXXYSVXYGXYXQYXLXYXXYXYXFYXXYXXYXZXYXXYRVXYXJYXXYXYXXYKQGJYXXYMBXYLXYMXYX
SZS
ZSGUQZSQZSGKESZSZSNSZJSZSGZSWZSDFEHSGESZSZSZSSZSZSZNSZSZSVSZXSZSSZSZSSZR
CYC
CYCCYCFCYHCYCH
ZDZ
ZDZZDZDCZDZZDZZDTZDBZDDZZDZDZZDZZDZBZDZKZDZZDPDZ
VVV
LNVVVVVVVVVVVVVVMZVVVVVAEVVVSVVAVVPJTWVVOVVCVVVJVVVVSVVBDVVVVVVKVVP
CTC
CTOCTCTCZCTCTCCTGCTCCTCCTVCTFCTCCTCVDCTNCTTCBCTCNCTUCTJTCCTCCTCTCCTUCTDCTCCTCPCTCCTCMCTC
MNM
MNNMDNMMNMNMEMNMNMAMNMDNM
RKR
XYRKFRKVRKWRKKRKRKHRKOFGKRSCRKPKRKRRKPTRKRKMRKRRKJRKBHWKRRKKRRRKRKRRKCRKRYKRRKMRKXRKC
FLF
FLFSFLFLFFLFLFFLFLFFLLFFLLFLFLFLFFLIFLELFPTZFLFLFMNFLFFL
ZHZ
ZHBZHZRIZHZIZHZDKZHZHZZHSFHZZHTHZZHZHZMZHZZHZZHGZHZ
XDX
DXXDXXDXDXDXDXXDJBXDFJXDKXDXDOOXDMDIXDRXDXDXXDDAXDXDXDXX
QAQ
QAQAQAQAQQAQOQAQAQQAQAQTAQAQQAQQAQAQQAOQAXQALQACAZQALQA
VQV
QVVQVOYVQNVQUQVAOVQAVQVQVWWVQVVQHVVQVVQIVQVVQVLVQVQVVQXVQUVQVVQIVQRQVVQGVQUQVVQVEVQC
QEQ
EQEQWQEKEQQEQEQZQEQEVTQEQQEJQEEQIQEOEQEQBEQ
DDD
DDJADDDDDTDDDDDDRDDJPDDVDDDDDQDDDDDDDDDDDDPDDBDDDDDDDQRDDWDDAXDDKDDIDDDDQDDDJLDDHSKDD
MEM
EMMEM
LXL
LXQLXDLXLLXLXHLXLLXGQ
TJT
TJRJTTJTNTJTTJDTJDTJSTJJSFTJTJPTJ
JGJ
ZJGZJGJJGJJGJJGIJGJPHGJGFGJGJRJGJCJGOGJGJUNJGLJGPGJYGJYFYGJJGCJGJGJJGPJGJGJJGJGJ
WWW
WWIWWXWWWWWWWWWWWWBWWWWWWWCWWRWWWSVHWWVSWWFWWWWWWWZWWWWWWWWWQ
UUU
AUUUUUUUUUUUUULUUUUUUUUUUUUUUUUUUYUMUUUORUUUUUUUUUUUUUUUTUUUUUUUUKUUUFCUUUUUUU
SYS
YSSYSSYKSYSYSSYSYVZYSSYSESYKRSYJSYSGSYSCWSYYSFVSYDGSYJSYS
EWE
EWYVJEWEWEWERWEHEWQEWDEWEWEEW
> **output:**
> 12
30
10
8
11
6
16
11
3
3
26
18
5
7
16
13
19
29
13
11
10
12
10
46
5
3
0
12
13
3
10
23
17
5
7
13
10
11
13
11
6
28
1
3
3
13
28
53
8
5

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        string ts;
        cin>>ts; //TargetString
        string ss;
        cin>>ss;//SampleString
        if(!(ts.length()==3 && ts[0]==ts[2])){
            cout<<-1<<endl;
            continue;
        }else{
            int index=ss.find(ts);
            //cout<<index<<endl;
            int times=0;
            while(index!=string::npos){
                times+=1;
                //cout<<index<<endl;
                index=ss.find(ts,index+1);
            }
            cout<<times<<endl;
        }
    }
}

## 中區106年
### 1.計算多個整數的平均值、最大值、最小值

>
> 請寫一程式計算多個整數的平均值，並找出最大值與最小值。
> 輸入說明：
> 第一行為一個正整數 n (n≤100)，代表整數的個數。
> 第二行為整數數列，整數之間用空格隔開。
> 輸出說明：
> 分三行輸出，依序列出平均值(浮點數四捨五入到小數點以下第2位)、最大值(整數)、最小值(整數)。
>
> 範例輸入：
> 7
> 795 -2089 21 9163 851 -3576 68
>
> 範例輸出：
> 747.57
> 9163
> -3576
>

---

#### 比賽測資:
>
>**測資第一組輸入：**
> 11
> -2514 16 8495 2144 -666 201 107 1 0 -999 47
>
> **測資第一組輸出：**
> 621.09
> 8495
> -2514
>
> **測資第二組輸入：**
> 88
> 5050 7654 6272 -4681 510 1412 -1889 851 -2412 4611 3003 2449 -6725 3179 4898 -5020 2700 -7350 2486 1756 8038 4460 394 3337 -4406 1655 -3902 6400 -5279 -6930 6339 -6000 9451 245 2192 6619 1012 9553 -169 5779 -9232 -1379 1439 3279 -6376 -2537 -9541 84 38 6383 -2852 -6105 4283 -9472 8327 -2125 4864 -3121 3009 -5223 -2762 -6771 -8014 5781 -1872 4793 1182 -2033 5398 270 4059 -2458 -5915 2497 8228 5607 -8045 6920 4016 1717 -403 5220 3091 -30 4941 9198 -7733 1411
>
> **測資第二組輸出：**
> 677.02
> 9553
> -9541

#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int main()
{
    int n=0;
    double sum=0;
    cin>>n;
    int *arr= new int[n];
    for(int i=0; i<n; i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    sort(arr,arr+n);
    cout<<fixed<<setprecision(2)<<sum/n<<endl;
    cout<<arr[n-1]<<endl;
    cout<<arr[0]<<endl;
}

### 2.算帳
> 穩賺福利中心本周部分商品推出特價優惠，只要是商品號碼以X開頭者均買一送一(單買一件不優惠)，商品號碼以Y開頭者當次購買第二件相同商品打五折優惠，商品號碼以其他字母開頭者則不優惠，請寫一程式幫忙顧客結帳。
> 輸入說明：
> 輸入資料中每一列代表一種商品的購買明細，第一項為一個大寫英文字母帶頭後面接著九個阿拉伯數字共10碼的商品編號，第二項為一個正整數代表商品單價，第三項為一個正整數代表該商品購買的數量，當商品編號出現0000000000表示整體測試資料的結束。
> 輸出說明：
> 請輸出本次購買商品的總價為何?
>
> 範例輸入：
> A000001002 268 1
> X000000010 963 3
> Y000001101 889 2
> X000000010 963 1
> Y000001102 284 1
> 0000000000
>
> 範例輸出：
> 3811.5

---

#### 比賽測資:
> 測資第一組輸入：
> Y000001102 802 1
> A000001101 705 4
> X000001002 319 4
> X000001102 394 2
> A000001101 705 2
> A000001101 705 3
> A000001101 705 2
> X000001002 319 5
> A000000010 783 4
> X000001102 394 4
> A000001002 869 4
> A000001102 477 4
> Y000001002 841 2
> Y000001102 802 4
> A000000010 783 2
> 0000000000
>
> 測資第一組輸出：
> 25083.5
>
> 測資第二組輸入：
> X000001101 416 3
> X000000010 608 4
> X000001101 416 3
> X000001101 416 1
> Y000001101 399 1
> Y000000010 747 1
> Y000001101 399 1
> X000001102 980 1
> A000000010 622 2
> X000001002 545 4
> A000001002 534 4
> Y000000010 747 5
> Y000001002 747 2
> A000000010 622 3
> X000001002 545 4
> A000000010 622 2
> A000000010 622 1
> A000001002 534 5
> Y000001102 802 1
> A000001101 705 4
> A000001101 705 2
> A000001101 705 3
> A000001101 705 2
> A000001102 477 4
> Y000001102 802 4
> 0000000000
>
> 測資第二組輸出：
> 33773.5

#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct item
{
    string snum;//SerialNumber
    int pprice;//ProductPrice
    int amount;
};
int main()
{
    vector<item> product;
    item tmp;
    double total=0;
    while(cin>>tmp.snum)
    {
        if(tmp.snum=="0000000000")
            break;
        cin>>tmp.pprice>>tmp.amount;
        bool found=false;
        for(int i=0; i<product.size(); i++)
        {
            if(product[i].snum==tmp.snum)
            {
                product[i].amount+=tmp.amount;
                found=true;
                break;
            }
        }
        if(not found)
        {
            product.push_back(tmp);
        }
    }
    for(int i=0; i<product.size(); i++)
    {
        if(product[i].snum[0]=='X')//買一松一 3件=2件的錢
        {
            total+=product[i].amount/2*product[i].pprice+(product[i].amount%2)*product[i].pprice;
        }
        else if(product[i].snum[0]=='Y')
        {
            total+=(product[i].amount/2)*product[i].pprice+(product[i].amount/2)*product[i].pprice*0.5+(product[i].amount%2)*product[i].pprice;
        }
        else
        {
            total+=product[i].amount*product[i].pprice;
        }
    }
    cout<<total<<endl;
}

### 3.費氏數列
> 給定一數列，檢查是否為費氏數列(1,1,2,3,5,8,13,21,34,…)的子集。
> 若是，請列出該數列之第一個數字是第幾個的費氏數列數字。否則，請列出數列中第一個不為費氏數列中之數字。
>
> 輸入說明：
> 一個整數數列，整數之間用空格隔開。
>
> 輸出說明：
> 若輸入數列為費氏數列的一個子集，輸出該數列第一個數字屬於費氏數列的項數，否則，輸出該數列第一個不屬於費氏數列的數字。
>
> 範例1輸入：　
> 8 13 21 34 55 89
> 範例1輸出：
> 6
> 範例2輸入：
> 8 13 21 35
> 範例2輸出：
> 35
> 範例3輸入：
> 2 2 4 6 10
> 範例3輸出：
> 2
---

#### 比賽測資:
> 測資第一組輸入：
> 433494436 701408733 1134903169 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173
>
> 測資第一組輸出：
> 433494436
>
> 測資第二組輸入：
> 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 14472334024676221
>
> 測資第二組輸出：
> 64
#### getline() 版 :100: :

#include<iostream>
#include<string>
#include<vector>
#include<sstream>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    string inputNumList;
    string num;
    unsigned long long int fnum[95];
    vector<unsigned long long int> cnum; //checkNum
    fnum[0]=1,fnum[1]=1;
    for(int i=2; i<95; i++) {
        fnum[i]=fnum[i-1]+fnum[i-2];
    }
    getline(cin,inputNumList);
    istringstream numlist(inputNumList); //In order to use the Function below!
    int i=0;
    unsigned long long int tmpNum;//Fibonacci numbers wiil bigger than the range of unsigned long long int at about 95t
    while(getline(numlist,num,' ')) { //string split & str to int
        istringstream conventer(num);
        conventer>>tmpNum;
        cnum.push_back(tmpNum);
        i++;
    }
    i=0;
    bool allfnum=true;//outputed=false;
    for(i=0; i<95; i++) {
        if (!allfnum)
            break;
        if(fnum[i]==cnum[0]) {
            for(int j=1; j<cnum.size(); j++) {
                if(fnum[i+j]!=cnum[j]) {
                    cout<<cnum[j]<<endl;
                    allfnum=false;
                    break;
                }
            }
            if(allfnum)
                cout<<i+1<<endl;
        }
    }
    unsigned long long int *index=find(fnum,fnum+95,cnum[0]);
    //cout<<index<<endl;
    if(allfnum && index==fnum+95)
        cout<<cnum[0]<<endl;
}

#### cin.eof() 版 :100: :

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    string inputNumList;
    string num;
    unsigned long long int fnum[95];
    vector<unsigned long long int> cnum; //checkNum
    fnum[0]=1,fnum[1]=1;
    for(int i=2; i<95; i++) {
        fnum[i]=fnum[i-1]+fnum[i-2];
    }
    //Fibonacci numbers wiil bigger than the range of unsigned long long int at about 95t
    unsigned long long int tmpNum;
    while(!cin.eof()) {
        cin>>tmpNum;
        cnum.push_back(tmpNum);
    }
    //cnum.pop_back();
    //cnum.pop_back();
    cnum.erase(cnum.begin()+(cnum.size()-1),cnum.end());
    //for(auto x:cnum) cout<<x<<" ";
    //cout<<endl;
    int i=0;
    bool allfnum=true;//outputed=false;
    for(i=0; i<95; i++) {
        if (!allfnum)
            break;
        if(fnum[i]==cnum[0]) {
            for(int j=1; j<cnum.size(); j++) {
                if(fnum[i+j]!=cnum[j]) {
                    cout<<cnum[j]<<endl;
                    allfnum=false;
                    break;
                }
            }
            if(allfnum)
                cout<<i+1<<endl;
        }
    }
    unsigned long long int *index=find(fnum,fnum+95,cnum[0]);
    //cout<<index<<endl;
    if(allfnum && index==fnum+95)
        cout<<cnum[0]<<endl;
}

### 4.數字序號轉換為雜湊表中對應的數字位置

> 請利用邊界摺疊法(folding at the boundaries)和除法取餘數(modulo)來寫出一個雜湊函數(hash function)，將授權碼的數字序號轉換為雜湊表中對應的數字位置。
>
> (1) 邊界摺疊法是將數字序號分為多個固定長度的分段，本題固定3個數字為一個分段(但最後一個分段的長度會可能不足3個數字)，例如12389020311256725的數字序號可以分為6個分段，x1=123, x2=890, x3=203, x4=112, x5=567, x6=25。將每一個奇數分段的值和偶數分段的反轉值相加即為對應值，例如奇數分段的值為x1=123, x3=203, x5=567，偶數分段的反轉值為x2’=098, x4’=211, x6’=52，所以相加後的對應值為123 + 203 + 567 + 98 + 211 + 52 = 1254。
>
> (2) 除法取餘數是將邊界摺疊法相加後的對應值再除以一個固定質數後，所得餘數作為雜湊表中對應的數字位置，本題是除以固定質數997，因此1254 % 997 = 257，亦即12389020311256725的數字序號在雜湊表中對應的儲存位置為257。
>
> 本題請輸入一個數字序號(由0~9組成)，此序號的長度不超過30個數字，再將此數字序號依據邊界摺疊法和除法取餘數的雜湊函數，轉換為在雜湊表中對應的數字位置進行輸出。
> 輸入說明：
> 由0~9組成的一串數字序號，此序號的長度不超過30個數字。
> 輸出說明：
> 一個介於0~996之間的整數。
>
> 範例1輸入：
> 123456789012345678901234567890
> 範例1輸出：
> 10
> 範例2輸入：
> 1234567890123456789012345678
> 範例2輸出：
> 917
>
---

#### 比賽測資:
> 測資第一組輸入：
> 98080735458523390620
>
> 測資第一組輸出：
> 498
>
> 測資第二組輸入：
> 3345044656749182566570100791
>
> 測資第二組輸出：
> 9
>
> 測資第三組輸入：
> 219806280786753444700485098
>
> 測資第三組輸出：
> 385

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    string num;
    vector<int> numlist;
    int tmpnum=0;unsigned long long int sum=0;
    cin>>num;
    for(int i=0; i<num.length()/3*3; i+=3) {
        if(i%2==0) {//不須反轉
            for(int j=0; j<3; j++) {
                tmpnum=(int(num[i+j])-'0')+tmpnum*10;
                //cout<<int(num[i+j])-'0'<<endl;
            }
        } else {
            for(int j=3; j>0; j--) {
                tmpnum=(int(num[i+j-1])-'0')+tmpnum*10;
            }
        }
        //cout<<tmpnum<<endl;
        numlist.push_back(tmpnum);
        tmpnum=0;
    }
    int i=num.length()/3*3;
    if(i%2==0) {//不須反轉
    for(int j=0; j<num.length()%3; j++) {
            tmpnum=(int(num[i+j])-'0')+tmpnum*10;
        }
    } else {
        for(int j=num.length()%3; j>0; j--) {
            tmpnum=(int(num[i+j-1])-'0')+tmpnum*10;
        }
    }
    //cout<<tmpnum<<endl;
    numlist.push_back(tmpnum);
    for (int i=0;i<numlist.size();i++){
        sum+=numlist[i];
    }
    cout<<sum%997<<endl;
}
/*數字反轉範例可餐考
#include <iostream>
using namespace std;
int main()
{
  int n, reverse=0, rem;
  cout<<"Enter a number: ";
  cin>>n;
  while(n!=0)
  {
     rem=n%10;
     reverse=reverse*10+rem;
     n/=10;
  }
  cout<<"Reversed Number: "<<reverse<<endl;
  return 0;
}
*/

### 5. 以價格的移動平均值判斷買賣時機
> 以價格的移動平均值判斷買賣時機 (佔分15分)
> 某股市專家在以下4個條件同時成立時才會買股票:
> A. 股價的5日平均值(當天股價加上前面4天的股價再除以5)比前一日的5日平均值高(M5(n)>M5(n-1))。
> B. 股價的10日平均值(當天股價加上前面9天的股價再除以10)比前一日的10日平均值高(M10(n)>M10(n-1))。
> C. 當日股價P(n)與兩個移動平均值的關係為: P(n)>M5(n) > M10(n)。
> D. P(n)<1.2M10(n)，也就是說股價並未高於10日平均值達20%或以上。
>
> 反之，他在以下3個條件任何一個成立時都會賣股票:
>
> E. P(n)>1.2M10(n)，股價已高於10日平均值達20%以上。
> F. 當日股價P(n)與兩個移動平均值的關係為: P(n)<M5(n) < M10(n)。
> G. 股價的10日平均值比前一日的10日平均值低(M10(n)<M10(n-1))。
> 其餘的情況，都是不做任何買賣動作。請幫此專家寫一個程式，將他的買賣紀律自動化。
> 輸入說明：
> 15個整數(最近15日之股價)，以空格分開。
> 輸出說明：
> 最近5日的股價與買賣建議，以B代表買進，S代表賣出，N代表不動作。
>
> 範例1輸入：
> 10 10 11 10 9 10 10 10 10 10 11 12 13 14 15
> 範例1輸出 ：
> 11B 12B 13S 14S 15S
> (最後3日開始賣股票是因為條件E)
>
> 範例2輸入：
> 20 20 19 21 20 20 20 20 20 19 20 21 19 17 15
> 範例2輸出：
> 20N 21N 19S 17S 15S
>
---

#### 比賽測資:
> 測資第一組輸入：
> 15 10 12 13 13 11 12 11 15 14 10 15 11 14 12
>
> 測資第一組輸出：
> 10S 15B 11S 14N 12S
>
> 測資第二組輸入：
> 24 29 31 21 17 21 28 35 42 38 38 40 32 28 24
>
> 測資第二組輸出：
> 38S 40S 32N 28N 24S
>
> 測資第三組輸入:
> 131 145 143 140 142 142 145 153 154 160 152 142 132 122 135
>
> 測資第三組輸出：
> 152N 142S 132S 122S 135S

//多個條件時應使用&&和||運算子
#include<iostream>
using namespace std;
double avm(int first,int last,int p[]) { //要記得使用Double型別，不然再GreenJudge過不了，還會被唸!
    int sum=0;
    for(int i=first; i<=last; i++) {
        sum+=p[i];
    }
    return double(sum)/(last-first+1);
}
void print(char c,int p) {
    cout<<p<<c<<" ";
}
int main() {
    ios_base::sync_with_stdio(false);
    int p[15];
    //MOfToday,MOfYesterday
    double m5t,m5y,m10t,m10y;
    for(int i=0; i<15; i++) {
        cin>>p[i];
    }
    for(int n=10; n<15; n++) {
        m5t=avm(n-4,n,p);
        m5y=avm(n-5,n-1,p);
        m10t=avm(n-9,n,p);
        m10y=avm(n-10,n-1,p);
        if (m5t>m5y && m10t>m10y && (m5t>m10t && p[n]>m5t) && 1.2*m10t>p[n]) {
            print('B',p[n]);
        } else if(1.2*m10t<p[n] || (m10t>m5t && m5t>p[n]) || m10t<m10y ) {
            print('S',p[n]);
        } else
            print('N',p[n]);
    }
}

### 6. 馬步問題

> http://c.biancheng.net/cpp/html/3376.html (可參考)
象棋中○馬走動的方法是直橫並行，即先橫向或直向走一格，然後再直向或橫向走兩格。如下圖範例，位於棋盤中間的馬，走一步時可以到達的位置(8種)
> > 象棋中走動的方法是直橫並行，即先橫向或直向走一格，然後再直向或橫向走兩格。如下圖範例，位於棋盤中間的馬，走一步時可以到達的位置(8種)
>
> | | | 馬 | | 馬 | | | | |
> | --- | --- | --- | --- | --- | --- | --- | --- | --- |
> | | 馬 | | | | 馬 | | | |
> | | | | <span style="color:red">馬</span> | | | | | |
> | | 馬 | | | | 馬 | | | |
> | | | 馬 | | 馬 | | | | |
>
> 給定棋盤的大小 3 * n，寬為3列、長為n行，假設從棋盤的左上角出發，是否可走到棋盤上的任意一格? n=3時3*3 方格中走訪順序如下表，棋盤內的數字代表棋子走的順序，中間方格無法到達，故無解。
>
>
> | 1 | 6 | 3 |
> | --- | --- | --- |
> | 4 | | 8 |
> | 7 | 2 | 5 |
>
> n=4 時3*4 方格中走訪順序如下表，可以走完。
>
> | 1 | 4 | 7 | 10 |
> | --- | --- | --- | --- |
> | 8 | 11 | 2 | 5 |
> | 3 | 6 | 9 | 12 |
>
> 其走法可能不只一種，另一個走法如下表
>
> | 1 | 4 | 7 | 10 |
> | --- | --- | --- | --- |
> | 12 | 9 | 2 | 5 |
> | 3 | 6 | 11 | 8 |
>
> 當有多個答案時，請先將這3*n的格子所代表的解排成一維陣列後，由左至右依字典排序(lexicographical order)比較，再挑選字典排序最小的一個方法輸出。所謂字典排序法，對於兩個一維陣列 1 2 4 5 3和1 2 5 4 3，先由左邊第一位開始比較，左邊第一位都是1，不能分辨大小；則再比左邊第二位，都是2；再比左邊第三位，後者是5較大，所以後者排列較大，其後的幾位也不用再比較，亦即1 2 4 5 3小於1 2 5 4 3。
>
> 於n=4 馬步走法的輸出兩種方法中，左邊第五位資料比較時第一個方法為8比第二個方法的12小，故輸出第一個。
>
> | 1 | 4 | 7 | 10 | **8** | 11 | 2 | 5 | 3 | 6 | 9 | 12 |
> | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
>
> 與
>
> | 1 | 4 | 7 | 10 | 12 | 9 | 2 | 5 | 3 | 6 | 11 | 8 |
> | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
>
> n=7 時3*7 方格走訪順序有以下
>
> | 1 | 4 | 7 | 20 | 17 | 14 | 11 |
> | --- | --- | --- | --- | --- | --- | --- |
> | 6 | 21 | 2 | 9 | 12 | 19 | 16 |
> | 3 | 8 | 5 | 18 | 15 | 10 | 13 |
>
> 或
>
> | 1 | 4 | 7 | 18 | 15 | 10 | 13 |
> | --- | --- | --- | --- | --- | --- | --- |
> | 6 | 19 | 2 | 9 | 12 | 21 | 16 |
> | 3 | 8 | 5 | 20 | 17 | 14 | 11 |
>
> 等16種走法。 (念誠猜測題目有誤應該是-----等6種走法。)
>
> **輸入說明：**
>
> 一個大於或等於3且小於或等於10的正整數 (3 >= n <= 10)
>
> **輸出說明：**
>
> 若無法走訪3*n棋盤上的任一格則輸出0，若可以走訪3*n棋盤的任一格，則輸出找到所有可能的走法中字典排序 (lexicographical order) 最小的一個方法。將每一格被走訪的順序，共有3*n個數字輸出於同一列，數字間以一個空格分開。
>
> **範例1輸入：**
>
> 3
>
> **範例1輸出：**
>
> 0
>
> **範例2輸入：**
>
> 4
>
> **範例2輸出：**
>
> 1 4 7 10 8 11 2 5 3 6 9 12
>
> **範例3輸入：**
>
> 7
>
> **範例3輸出：**
>
> 1 4 7 18 15 10 13 6 19 2 9 12 21 16 3 8 5 20 17 14 11
>
---

#### 比賽測資:
> 測資第一組輸入：
> 8
>
> 測資第一組輸出：
> 1 4 7 10 13 16 19 22 8 11 2 5 20 23 14 17 3 6 9 12 15 18 21 24
>
> 測資第二組輸入：
> 10
>
> 測資第二組輸出：
> 1 4 7 12 25 10 27 16 19 22 6 13 2 9 28 15 24 21 30 17 3 8 5 14 11 26 29 18 23 20
>
謝謝偉良老師幫忙一起做這題，想到使用DFS爆搜的做法。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int Nrow = 3;             //棋盤3列
int Ncol = 0 ;
int **martic=new int *[Nrow]; //記錄棋盤每格是第幾步走過
int countStep = 0;           //目前走第幾步
int solution = 0;        //第N種方法
int step[8][2] = {{2,-1},{1,-2},{-1,-2},{-2,-1}, {-2,1},{-1,2},{1,2},{2,1}};   //8方向
vector< vector<int> > walkPath;    //走過的順序

int cmp(vector<int> v1,vector<int> v2) {
    for(int i=0; i<v1.size(); i++) {
        if(v1[i]!=v2[i]) {
            return v1[i]<v2[i];
        }
    }
}
int isok(int x,int y) {   //判斷這一步是否可以走
    return (x>=0 && x<Nrow && y>=0 && y<Ncol && martic[x][y]==0);
}

void display() { //當整個棋盤都已走過就輸出整個棋盤
    cout << "the "<< ++solution <<" solution:"<<endl;
    for(int i=0 ; i<Nrow ; i++) {
        for(int j=0 ; j<Ncol ; j++) {
            cout << martic[i][j] << " " ;
        }
        cout << endl ;
    }
    cout << endl;
}

void DFS(int x,int y) {
    int nextx,nexty;
    for (int i = 0; i < 8; ++i) {
        nextx = x + step[i][0];
        nexty = y + step[i][1];

        if (isok(nextx,nexty)) {
            if(countStep!=Nrow*Ncol-1) {
                countStep++;
                martic[nextx][nexty] = countStep;
                DFS(nextx,nexty);          //遞迴
                martic[nextx][nexty] = 0;  //BackTracking
                countStep--;                   //BackTracking
            } else {
                countStep++;
                martic[nextx][nexty] = countStep;
                ++solution;
                //display();
                //已全部走過，列印輸出
                vector<int> tmp;  //使用一個一維vector 生成二維 vector
                for(int r=0; r<Nrow; r++) {
                    for(int c=0; c<Ncol; c++) {
                        tmp.push_back(martic[r][c]);
                    }
                }
                walkPath.push_back(tmp);
                martic[nextx][nexty] = 0;  //BackTracking
                countStep--;                   //BackTracking
            }
        }
    }
}
int main() {
    cin>>Ncol;
    for(int i=0; i<Nrow; i++) {
        martic[i]=new int [Ncol];
        for(int j=0; j<Ncol; j++)
            martic[i][j]=0;
    }
    countStep = 1;
    martic[0][0]=1;
    DFS(0,0);
    if(solution!=0) {
        sort(walkPath.begin(),walkPath.end(),cmp);
        for(int i=0; i<Nrow*Ncol; i++) {
            cout<<walkPath[0][i]<<" ";
        }
        cout<<"\n";
    } else {
        cout<<0<<"\n";
    }
    return 0;
}

### 7. 雙層骨牌 (佔分20分)
> 有一種特殊的骨牌，骨牌的正面分成兩個區域，每個區域可以有0到6個黑點不等，下圖一就是一組包含有四張骨牌的範例，在這範例中，上半區域的點數總和為6+1+1+1=9，下半區域的點數總和為1+4+3+3=11，將上下兩區域的點數總和的差值加上絕對值稱為這一組骨牌的縫隙值，假定每一張骨牌可以被旋轉180度(也就是上下區域對調) ，請設計一程式來計算要旋轉幾張骨牌可以讓一組骨牌的縫隙值最小。以圖一為例，不需旋轉任何骨牌，其縫隙值已是最小，所以答案為0個。
 圖一 四張骨牌
> **輸入說明 ：**
> 輸入資料的第一列有1個數字 q (0 < q < 1000)代表這一組骨牌總共有幾張，接下來的q列，每一列都有兩個以空白隔開的數字 u及d (0 ≦ u , d ≦6) ，分別代表這q張骨牌的上半及下半區域的點數。
> **輸出說明 ：**
> 第一列輸出要旋轉幾張骨牌可以讓這一組骨牌的縫隙值最小
> 第二列輸出旋轉後所得之最小縫隙值為何?
> **範例輸入 ：**
> 3
> 2 5
> 4 1
> 6 0
> **範例輸出 ：**
> 1
> 0
---

#### 比賽測資:
> 測資第一組輸入：
> 10
> 6 0
> 5 0
> 4 0
> 3 0
> 2 0
> 1 0
> 6 1
> 5 1
> 4 1
> 3 1
>
> 測資第一組輸出：
> 4
> 1
>
> 測資第二組輸入：
> 23
> 0 0
> 2 6
> 6 6
> 2 1
> 1 1
> 6 2
> 0 6
> 0 5
> 2 4
> 4 3
> 4 5
> 1 0
> 1 3
> 6 2
> 0 2
> 4 3
> 0 6
> 1 5
> 0 1
> 0 4
> 6 0
> 0 0
> 2 5
>
> 測資第二組輸出：
> 3
> 0
>
> 測資第三組輸入：
> 25
> 4 2
> 6 0
> 2 6
> 5 4
> 2 1
> 1 1
> 3 3
> 4 0
> 0 0
> 2 4
> 1 0
> 6 1
> 5 5
> 1 3
> 5 3
> 3 3
> 3 2
> 2 4
> 0 4
> 2 2
> 3 1
> 4 1
> 5 6
> 6 0
> 0 5
>
> 測資第三組輸出：
> 2
> 0
>
> 測資第四組輸入：
> 32
> 3 1
> 5 5
> 0 6
> 6 5
> 2 2
> 4 0
> 0 4
> 4 1
> 2 2
> 6 2
> 4 3
> 0 4
> 6 3
> 3 6
> 2 3
> 6 2
> 5 4
> 3 3
> 6 6
> 0 3
> 6 5
> 5 4
> 6 2
> 2 6
> 6 2
> 6 2
> 6 4
> 3 0
> 6 4
> 4 4
> 0 0
> 4 0
>
> 測資第四組輸出：
> 3
> 1
>
出不來 :-1: :-1: :-1:

#include<iostream>
#include<vector>
#include<algorithm>
#define endl '\n'
#define IOS ios_base::sync_with_stdio(0) cin.tie(NULL)
#pragma GCC optimize("O3")
using namespace std;

int q=0;
bool s[1000];

struct subSet {
    int value;
    int rtime; //RotateTime
} tmpSubSet;

vector<struct subSet> solution;
vector< vector<int> > boneCard;

bool cmp(struct subSet a,struct subSet b) {
    if(a.value!=b.value)
        return a.value<b.value;
    else
        return a.rtime<b.rtime;
}

void backtrack(int n) { //位向量法生成所有子集
    if(n==q) {
        tmpSubSet.value=0;
        tmpSubSet.rtime=0;
        for(int i=0; i<q; i++) {
            if(s[i]) {
                tmpSubSet.value+=boneCard[i][1];
                tmpSubSet.rtime++;
            } else
                tmpSubSet.value+=boneCard[i][0];
        }
        for(int i=0; i<q; i++) {
            if(s[i])
                tmpSubSet.value-=boneCard[i][0];
            else
                tmpSubSet.value-=boneCard[i][1];
        }
        tmpSubSet.value=abs(tmpSubSet.value);
        solution.push_back(tmpSubSet);
        return;
    }
    s[n]=true;  // 選取第n+1個，然後繼續枚舉之後的狀況。
    backtrack(n+1);
    s[n]=false;   // 不選取第n+1個，然後繼續枚舉之後的狀況。
    backtrack(n+1);
}

int main() {
    cin>>q;
    for(int i=0; i<q; i++) {
        vector<int> cardTmp(2);
        cin>>cardTmp[0];
        cin>>cardTmp[1];
        boneCard.push_back(cardTmp);
    }
    backtrack(0);
//    for(auto item : solution) {
//        cout<<item.value<<endl;
//    }
    sort(solution.begin(),solution.end(),cmp);
    cout<<solution[0].rtime<<endl<<solution[0].value<<endl;
}

> 01背包問題-dp的作法 偶還在想...

#include<iostream>
#include<cstring>
using namespace std;
int min(int x,int y)//比较函数
{
    if(x>y)
        return y;
    else
        return x;
} 
int dp[1010][12010];
int main()
{
    int n,top[1001],under[1001];
    int sum[1001],result;
    int i,j;
    
    cin>>n;//输入牌数
    for(i=1;i<=n;i++)	
    {
        cin>>top[i]>>under[i];//输入上方、下方点数
    	sum[i]=top[i]-under[i];//每一组牌的上下差值
    }
    memset(dp,1,sizeof(dp));//将dp数组全部赋1值
    dp[0][5000]=0;
    for(i=1;i<=n;i++)//从第一组牌开始比较
        for(j=-5000;j<=5000;j++)//最小情况为上方1000张全为1，下方1000全为6；最大情况为上方1000张全为6，下方1000全为1
            dp[i][j+5000]=min(dp[i-1][j+5000-sum[i]] , dp[i-1][j+5000+sum[i]]+1);//比较每一次是翻转还是不翻转得到的值最小
 
    for(i=0;i<=5000;i++)
    {
        result=min(dp[n][i+5000],dp[n][-i+5000]);//比较每次是翻转或不翻转小
        if(result<=1000)//因为最多有1000张牌，因此最多移动1000次
        {
            cout<<result<<endl;
            break;
        }
    }
    return 0;
}

## 中區107年
### 1.七張迷你麻將遊戲 (佔分15分)
> 從集合 S = {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G}中選出7個字元形成
> 一個長度為7的字串，每個字元最多可被選到4次。先決定這個字串是否為聽牌
> 狀態(ready)，若是，列出每個它所聽的牌(依S集合內的元素排列順序)。若尚未
> 聽牌或是格式錯誤(字串長度不是7、出現非集合S內的元素、同一張牌出現4次
> 以上等情況)，一律輸出-1。聽牌狀態的定義是，只要再加入一張牌就能形成8張
> 的完整牌型(completed pattern)，也就是胡牌。 8張的完整牌型指的是:一對(2個
> 相同字元)再加上兩組「3件組合」(triplets)。 對英文字母而言，「3件組合」就
> 是3個相同的字母例如: AAA、 BBB、FFF。對阿拉伯數字而言，「3件組合」除
> 了3個相同的數字(例如 111、222、888)以外，也可以是3個連號的數字，像是
> 123、345、789等等。請注意9與1並不相連，換句話說，912跟891都不算合法
> 的「3件組合」。
> **輸入說明：**
> 第一列為一個正整數 n (n≤100)，代表字串的個數，接下來為n列測試字串。
> **輸出說明：**
> 若該輸入字串格式正確(長度7，由S的元素組成，相同字元不超過4個)且已經
> 聽牌，輸出”Ready for“與該輸入字串聽的所有目標牌(依S集合內的元素排列
> 順序，以空格分開)。否則，輸出-1。
> **範例輸入：**
> 14
> 12345AABD
> CD33
> 123AA78
> 8AAABBB
> 1234GGG
> 2333BBB
> 4445666
> 68CCCDD
> 2223456
> 35AABBB
> 0800449
> 1222223
> 2333345
> 123BBDD
>
>
> **範例輸出：**
> -1
> -1
> Ready for 6 9
> Ready for 8
> Ready for 1 4
> Ready for 1 2 4
> Ready for 3 4 5 6 7
> Ready for 7
> Ready for 1 3 4 6 7
> Ready for 4
> -1
> -1
> Ready for 1 2 4 5
> Ready for B D

#include <bits/stdc++.h>
using namespace std;
string SetMahjong = "123456789ABCDEFG";
string groupSet[] = {"AA","BB","CC","DD","EE","FF","GG","11","22","33","44","55","66","77",
                     "88","99","AAA","BBB","CCC","DDD","EEE","FFF","GGG","111","222",
                     "333","444","555","666","777","888","999","123","234","345","456","567","678","789"
                    };
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string mahjong;
    for (int i = 0; i < n; i++) {
        bool format = true;
        cin >> mahjong;
        if (mahjong.length() == 7) {
            //決定是否聽牌 1.長度為七 2.皆為1~9,A~G 3.每個字元最多被選到4次
            sort(mahjong.begin(), mahjong.end());
            //cout<<mahjong<<endl;  檢查排序後的字串
            for (int j = 0; j < 7 && format; j++) {
                if (SetMahjong.find(mahjong[j]) != string::npos) {
                    //cout<<mahjong[j]<<"checked ";看看是不是每一個char都是集合內的文字。
                    if(j==6) {
                        for(int k=0; k<3; k++) {
                            if(mahjong[k]==mahjong[k+4]) {
                                format = false;
                            }
                        }
                    }
                } else
                    format = false;
            }
        } else
            format = false;
        vector<char> readyFor;
        if (!format) {
            cout <<  - 1 << endl;
        } else {
            //cout << "The format is correct." <<endl;
            //開始暴力填入1~G,並依序從倆個的先開始檢查。
            //times找到的次數。
            for(int j=0; j<14; j++) {
                bool sn=false; //SerialNumber
                string copyM=mahjong;
                copyM=copyM+SetMahjong[j];
                sort(copyM.begin(),copyM.end());
                //cout<<copyM<<endl;
                for(int k=32; k<39; k++) {
                    int times=0;
                    for(int ss=0; ss<3; ss++) {//ss=subSet
                        if(copyM.find(groupSet[k][ss])!=string::npos) {
                            times+=1;
                            if(times==3) {
                                sn=true;
                            }
                        }
                    }
                }
                for(int ci=0; ci<16; ci++) { //ci = chickIndex
                    int pos=copyM.find(groupSet[ci]);
                    if(pos!=string::npos && copyM.find(groupSet[ci+16])==string::npos) {
                        copyM.erase(pos,2);
                        //cout<<pos<<endl;
                        //cout<<copyM<<endl;
                        break;
                    }
                }
                for(int ci=16; ci<39; ci++) { //ci = chickIndex
                    int pos=copyM.find(groupSet[ci]);
                    if(pos!=string::npos) {
                        copyM.erase(pos,3);
                        //cout<<pos<<endl;
                        //if(copyM.empty()) cout<<"empty"<<endl;
                        //else cout<<copyM<<endl;
                        if(copyM.empty()) {
                            vector<char>::iterator it = find(readyFor.begin(), readyFor.end(), SetMahjong[j]);
                            char ready=SetMahjong[j];
                            if(it==readyFor.end()) {
                                readyFor.push_back(ready);
                                //cout<<"find "<<ready<<endl;
                            }
                            break;
                        }
                    }
                }
                if(sn) {
                    for(int k=32; k<39; k++) {
                        string copyM2=mahjong+SetMahjong[j];
                        sort(copyM2.begin(),copyM2.end());
                        //cout<<copyM2<<endl; //M2 using for SerialNumber part.
                        int times=0;
                        for(int ss=0; ss<3; ss++) {//ss=subSet
                            if(copyM2.find(groupSet[k][ss])!=string::npos) {
                                times+=1;
                                if(times==3) {
                                    for(int ss2=0; ss2<3; ss2++) {
                                        int pos=copyM2.find(groupSet[k][ss2]);
                                        copyM2.erase(pos,1);
                                    }
                                    for(int ci=32; ci<39; ci++) { //ci = chickIndex
                                        int pos=copyM2.find(groupSet[ci]);
                                        if(pos!=string::npos) {
                                            copyM2.erase(pos,3);
                                            break;
                                        }
                                    }
                                    for(int ci=16; ci<32; ci++) { //ci = chickIndex
                                        int pos=copyM2.find(groupSet[ci]);
                                        if(pos!=string::npos) {
                                            copyM2.erase(pos,3);
                                            break;
                                        }
                                    }
                                    for(int ci=0; ci<16; ci++) { //ci = chickIndex
                                        int pos=copyM2.find(groupSet[ci]);
                                        if(pos!=string::npos) {
                                            copyM2.erase(pos,2);
                                            break;
                                        }
                                    }
                                    if(copyM2.empty()) {
                                        vector<char>::iterator it = find(readyFor.begin(), readyFor.end(), SetMahjong[j]);
                                        char ready=SetMahjong[j];
                                        if(it==readyFor.end()) {
                                            readyFor.push_back(ready);
                                        }
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(!readyFor.empty()) {
            cout<<"Ready for";
            for(int ri=0; ri<readyFor.size(); ri++) {
                cout<<" "<<readyFor[ri];
            }
            cout<<endl;
        } else if(format)
            cout<<-1<<endl;
    }
}

### 2. 雙連線遊戲 (佔分10分)
> 寫出與兩個玩家對戰之棋盤遊戲，輸入棋盤大小為N×N（N為奇數）。依由
> 左而右、由下而上的順序，將每個格子的編號為1, 2, 3,… N×N。遊戲規則如下：
> 1. 玩家1與玩家2輪流輸入任一尚未選取的格子號碼。
> 2. 位於同一直線、橫線、對角線之N個號碼被玩家1或玩家2選取，則完成一
> 條連線。
> 3. 先達成2條連線者則為贏家。
>
>輸入說明：
> 測試資料的內容如下:
> 第一列為一個整數，代表測試資料有幾組。
> 接下來每一組測試資料的第一列為一個介於3到9的奇數(代表棋盤邊長N)，下
> 一列為玩家1與玩家2分別選取的格子編號，以空格區分。玩家1先選，然後
> 玩家2再選，重複這個過程。
> 之後每一組測試資料安排方式依此類推。
> 輸出說明：
> 對於每一組測試資料，請輸出P1（玩家1獲勝）或P2（玩家2獲勝）或是
> tie（平手）。
>
> 範例輸入：
> 2
> 3
> 1 2 4 5 7 3 8 6 9
> 3
> 5 3 9 1 2 8 6 4 7
> 範例輸出：
> P1
> tie

#include<bits/stdc++.h>
using namespace std;
int main() {
    int times;
    cin>>times;
    for(int i=0; i<times; i++) {
        int n,index;
        cin>>n;
        int *table=new int[n*n+1];
        int pi=1;
        int p[3]= {0,0,0};
        for(int j=0;j<int(n*n);j++) {
            table[j]=0;
        }
        for(int j=0; j<int(n*n); j++) {
            cin>>index;
            if(j%2==0) {
                table[index]=1;
                pi=1;
            } else {
                table[index]=2;
                pi=2;
            }
            if(j>=n*2-2) {
                p[1]=0;
                p[2]=0;
                bool lined=false;
                for(int k=0; k<n; k++) { //檢查橫的有沒有
                    for(int w=1; w<n+1; w++) {
                        if(table[k*n+w]==pi)
                            lined=true;//1,2,3
                        else {
                            lined=false;
                            break;
                        }
                    }
                    if(lined)
                        p[pi]++;
                }
                for(int w=1; w<n+1; w++) { //檢查直的有沒有
                    for(int k=0; k<n; k++) {
                        if(table[k*n+w]==pi)
                            lined=true;
                        else {
                            lined=false;
                            break;
                        }
                    }
                    if(lined)
                        p[pi]++;
                }
                //檢查對角的有沒有
                int ci=1;
                for(int k=0; k<n; k++) {
                    if(table[ci]==pi )
                        lined=true;
                    else {
                        lined=false;
                        break;
                    }
                    ci+=n+1;
                }
                if(lined)
                    p[pi]++;
                ci=n;//+(n-1)
                for(int k=0; k<n; k++) {
                    if(table[ci]==pi)
                        lined=true;
                    else {
                        lined=false;
                        break;
                    }
                    ci+=n-1;
                }
                if(lined)
                    p[pi]++;
                //cout<<p[1]<<" "<<p[2]<<endl;
                if(p[1]>=2 && p[2]<p[1]) {
                    cout<<"P1"<<endl;
                    delete [] table;
                    for(int lastj=j; lastj<n*n-1; lastj++)
                        cin>>pi;
                    break;
                } else if(p[2]>=2 && p[1]<p[2]) {
                    cout<<"P2"<<endl;
                    delete [] table;
                    for(int lastj=j; lastj<n*n-1; lastj++)
                        cin>>pi;
                    break;
                }
                if(p[1]<2 && p[2]<2 && j==n*n-1) {
                    cout<<"tie"<<endl;
                    delete [] table;
                }
            }
        }
    }
}

### 4. 人員調動 (佔分10分)
> 某學校人事部門為了整體學校運作效能並預防人員在同一個單位待太久可
> 能衍伸弊端的狀況發生，會於年度結束之前調查校內各單位人員是否有異動意願，並據以作下個年度人員調動依據，為了維持各單位人力平衡，規定每一個人限填寫一項異動要求，而異動要被允許只有在你想去的單位也剛好有人想到
> 你的單位，如此兩人互調，異動方可完成，請幫該校人事室寫一程式，根據今年本校人員異動申請資料，計算出有多少對的人員可以異動？
> 輸入說明：
> 測試資料的內容如下:
> 第一列為一個整數N(0&lt;N≦100)，代表測試資料有幾組。
> 接下來的每一組測試資料的第1列有一個整數M(0&lt;M≦1000)，代表提出申請的員工數量，接下的M列，每一列有二個以空白隔開的整數 a, b (0 &lt; a, b ≤
> 1000)，分別代表申請者原單位代碼及想去的單位代碼，之後每一組測試資料安排方式依此類推。
> 輸出說明：
> 對於每一組測試資料，請輸出有多少對的人員可以異動，若沒有任何符合異
> 動條件的組別則輸出0。
> 範例輸入：
> 2
> 7
> 1 2
> 35 66
> 100 500
> 2 1
> 2 3
> 500 100
> 3 2
> 3
> 100 200
> 200 400
> 400 1
> 範例輸出：
> 3
> 0

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        int m;
        cin>>m;
        int **unitCode=new int*[m];
        int change=0;
        for(int j=0; j<m; j++) {
            unitCode[j]=new int[2];
            cin>>unitCode[j][0];
            cin>>unitCode[j][1];
            //cout<<unitCode[m][0]<<" "<<unitCode[m][1]<<endl;
            if(unitCode[j][0]>unitCode[j][1])
                swap(unitCode[j][0],unitCode[j][1]);
            for(int k=0; k<j; k++) {
                //cout<<unitCode[k][0]<<" "<<unitCode[k][1]<<endl;
                if(unitCode[k][0]==unitCode[j][0] && unitCode[k][1]==unitCode[j][1]) {
                    change++;
                    break;
                }
            }
        }
        cout<<change<<endl;
        for(int j = 0; j <m; j++) {
            delete [] unitCode[j];
            delete [] unitCode;
        }
    }
}
/*vector<vector<int>> unitCode;
unitCode.resize(m,vector<int>(2,0));//¤Gºûvector initialize*/

### 6. 找出每個字串中的最長迴文長度和最長迴文個數 (佔分10分)
> 迴文是指在一串字元中，由前面讀到後面的字元出現順序與從後面讀到前面
> 的字元出現順序一樣。例如，a3BBcBB3a是一串迴文，而aa3baab3acc不是
> 一串迴文，不過，aa3baab3acc字串中仍然可以找出最長的迴文子字串為
> a3baab3a，其最長迴文子字串的長度為8。迴文長度可以為偶數或奇數，例如
>
> 7
> AbbA為偶數長度的迴文，aBa則為奇數長度的迴文。迴文長度最少為1，例如a
> 也可以視為長度1的迴文。一個字串中可能會包含多個長度相同的最長迴文子字
> 串，例如7BCBCdTNTkoWWWaTNT字串中包含五個長度為3的最長迴文子字串
> ，包括BCB、CBC、第一個TNT、WWW、和第二個TNT。則此字串的最長迴文
> 長度為3，最長迴文個數為5。本題要找出每個字串中的最長迴文長度和最長迴
> 文個數，字串由大小寫的英文字母和數字所組成，且大寫與小寫的英文字母視
> 為不同，例如aBbA不是迴文。
> 輸入說明：
> 第一列為一個正整數n，代表字串的個數，接下來為n列字串，請針對每列字
> 串分別找出其最長迴文長度和最長迴文個數。
> 輸出說明：
> 針對所有字串依序輸出，每列字串需輸出兩個整數值，包括每個字串個別的
> 最長迴文長度(整數)和最長迴文個數(整數)，以空格隔開。
> 範例輸入：
> 5
> aa3baab3acc
> a8Sd8fGg9hH9jkL
> 91P1k1999r9cPcKcLcLppP
> aamenwwwnemkmenwwwppwwwnemcceddeccmenqqw
> aabcbddddefffgggggfffedddefffggggfffedddddefffgggfffedddefff
> 範例輸出 ：
> 8 1
> 1 15
> 3 8
> 14 2
> 19 3

#include<bits/stdc++.h>
#include<string>
using namespace std;
int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        string line("");
        cin>>line;
        const int len=line.length();
        for (int j=1; j<len; j++)
            line.insert(2*j-1,"#");
        //cout<<line<<endl;
        int tAmount=0,maxlen=0; //tMount=totalamount
        for(int j=0; j<line.length(); j++) {
            int ci=0,lenc=0; //ci=chickIndex
            while(j-ci>=0 && j+ci<=line.length()-1 && line[j-ci]==line[j+ci]) {

                if(line[j-ci]!='#' && ci!=0)
                    lenc=lenc+2;
                if(line[j-ci]!='#' && ci==0)
                    lenc++;
                ci++;
            }
            if(lenc>maxlen) {
                maxlen=lenc;
                tAmount=1;
            } else if(lenc==maxlen) {
                tAmount+=1;
            }
        }
        cout<<maxlen<<" "<<tAmount<<endl;
    }
}

## 中區108年

### pB

#include <bits/stdc++.h>
using namespace std;
int maxa = INT_MIN;
int t, a, b;
void f(int k, int b) {
    if (k != 0) {
        for (int i = 0, d = 1, nb; i < to_string(b).size(); i++, d *= 10) {
            nb = (b / d) * d * 10 + b % d;
            auto sum = [](int num) {
                int sum = 0;
                while (num) {
                    sum += num % 10;
                    num /= 10;
                }
                return sum;
            };
            maxa = max(maxa, sum(abs(a - nb)));
            f(k - 1, nb);
        }
    }
}
int main() {
    cin >> t;
    while (t--) {
        cin >> a >> b;
        f(to_string(a).size() - to_string(b).size(), b);
        cout << maxa << '\n';
    }
}

### pC

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    while (getline(cin, s)) {
        vector<string> mp;
        mp.push_back(s);
        while (getline(cin, s), s != "***")
            mp.push_back(s);
        tuple<int, int, int> t;
        for (int i = 0; i < mp.size(); i++)
            for (int j = 0; j < mp[0].size(); j++)
                if (mp[i][j] == 's')
                    t = {i, j, 0};
        int d[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}, v[85][85] = {0}, f = 0;
        queue<tuple<int, int, int> > q;
        q.push(t);
        while (!q.empty()) {
            t = q.front();
            q.pop();
            int ni = get<0>(t), nj = get<1>(t), val = get<2>(t);
            v[ni][nj] = 1;
            if (mp[ni][nj] == 'e')
                break;
            for (int i = 0; i < 4; i++)
                if (mp[ni + d[i][0]][nj + d[i][1]] != 'w' && !v[ni + d[i][0]][nj + d[i][1]])
                    q.push({ni + d[i][0], nj + d[i][1], val + 1});
        }
        cout << (mp[get<0>(t)][get<1>(t)] == 'e' ? get<2>(t) : 0) << '\n';
    }
}

T

wwwwwwwwwwwwwwwww
w     wsw       e
ww             ww
wwwwwwwwwwwwwwwww
***
wwwwwwwwwwwwwwwwwwwwwwwwwww
w     wsw         wwwwwwwwe
w                   wwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwww
***

### pD

#include <bits/stdc++.h>
using namespace std;
int main() {
    double s;
    while (cin >> s) {
        double sw[6] = {0, 11.3, 17.1, 32.6, 50.9, INT_MAX};
        cout << (round(pow(s / 0.836, 1 / 1.5)) > 17 ? 17 : round(pow(s / 0.836, 1 / 1.5))) << ',';
        for (int i = 0; i < 5; i++)
            if (s > sw[i] && s <= sw[i + 1]) {
                cout << i + 1 << '\n';
                break;
            }
    }
}

### pE

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s[5] = {"            ",
                   " qwertyuiop ",
                   " asdfghjkl  ",
                   " zxcvbnm    ",
                   "            "};
    map<char, pair<int, int> > mp = {{'u', {-1, 0}},
                                     {'d', {1, 0}},
                                     {'l', {0, -1}},
                                     {'r', {0, 1}}};
    string t;
    while (getline(cin, t)) {
        if (t.substr(t.size() - 3, t.size() - 1) == "eee")
            t = t.substr(0, t.size() - 2);
        else {
            cout << -1 << '\n';
            return 0;
        }

        pair<int, int> p = {1, 1};
        for (int i = 0; i < t.size(); i++) {
            if (t[i] == 'e')
                cout << char(toupper(s[p.first][p.second]));
            else {
                auto n = mp[t[i]];
                if (s[n.first + p.first][n.second + p.second] != ' ')
                    p = {n.first + p.first, n.second + p.second};
            }
        }
        cout << '\n';
    }
}

### pF

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ll f[100] = {0};
    f[1] = 1;
    for (int i = 2; i < 100; i++)
        f[i] = f[i - 1] + f[i - 2];
    int t, m, n;
    cin >> t;
    while (t--) {
        cin >> m >> n;
        ll ans = n;
        for (int j = 0; j < m; j++)
            ans = f[ans];
        cout << ans << '\n';
    }
}

### pH

#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > dq(10000);
vector<int> rd(10000);
int maxa = INT_MIN;
void dfs(int n, int d, int b) {
    maxa = max(d, maxa);
    rd[n] = d;
    for (int i = 0; i < dq[n].size(); i++)
        if (dq[n][i] != b) dfs(dq[n][i], d + 1, n);
}
int main() {
    int n, p, q, a;
    fill(rd.begin(), rd.end(), -1);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> p >> q;
        dq[p].push_back(q);
        dq[q].push_back(p);
    }
    cin >> a;
    dfs(a, 0, a);
    cout << maxa << ' ';
    for (int i = 0; i < n; i++)
        if (maxa == rd[i])
            cout << i << ' ';
}

## 其他地區的題目
### 1.物品探測 `b899`
> 2016高雄市資訊學科能力複賽
> 題目和範例測資如下:
> https://zerojudge.tw/ShowProblem?problemid=b899

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct position {
    int x;
    int y;
}p[3];
int dis(int a,int b){
    return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y);
}
void position(int a,int b,int c){ //a,b 對角線的兩點 c 另一點
                                  //直角座標系的中點公式，偶也不懂還在問數學老師。
    cout<<p[a].x+p[b].x-p[c].x <<" "<<p[a].y+p[b].y-p[c].y<<endl;
}
int main(){
    for(int i=1;i<4;i++){
      cin>>p[i].x>>p[i].y;
    }
    if(dis(1,2)>dis(2,3) && dis(1,2)>dis(1,3)) position(1,2,3);
    else if(dis(1,3)>dis(2,3) && dis(1,3)>dis(1,2)) position(1,3,2);
    else position(2,3,1);
}

### 2.蠕動小蟲 `b900`
> 2016高雄市資訊學科能力複賽
> 題目和範例測資如下:
> https://zerojudge.tw/ShowProblem?problemid=b900
>
>
> 念誠ㄉ好朋友--乃方做ㄉ :100:

//b900_2016高雄複賽_03蠕動小蟲
#include <iostream>
#include <string>
using namespace std;

int main(){
	int w, h;
	cin >> w >> h;
	//pe 1~w
	int pe[w];
	for (int i=0;i<w;i++){
		pe[i] = i+1;
	}
	//這裡出來是他們自己的位子 
	for (int i=0; i<h; i++){
		char temp[2*w-1];
		cin >> temp;
		for (int j=0; j<=(2*w-1); j++){
			if (temp[j] == 45){
				int change = pe[j/2];
				pe[j/2] = pe[j/2+1];
				pe[j/2+1] =  change;
				
			}
		}
	}
	//題目要的是 i 最後到的位子 
	int ans[w];
	for(int i=0; i<w; i++){
		ans[pe[i]-1] = i+1;
	}

	for(int i=0; i<w; i++){
		cout <<ans[i]<< " " ; 
	}
	return 0;
} 

> 偶ㄉ
>

#include <bits/stdc++.h>
using namespace std;
int main() {
    string situation;
    int w,h; //width , height
    cin>>w>>h;
    vector<int> wormsCrawlingPath(w);
    for(int i=0; i<w; i++)
        wormsCrawlingPath[i]=i+1; //初始化寵寵路徑
    for(int i=0; i<h; i++) {
        cin>>situation;
        situation.insert(0,".");
        situation.insert(2*w,".");
        for(int &j : wormsCrawlingPath) {
            if(situation[j*2]=='-') {
                j++;
            }else if(situation[j*2-2]=='-'){
                j--;
            }
        }
    }
    for(int i : wormsCrawlingPath) cout<<i<<" ";
    cout<<endl;
}

### 3.南南見島 `c517`
> 2017高雄市資訊學科能力複賽
> 題目和範例測資如下:
> https://zerojudge.tw/ShowProblem?problemid=c517
>

#include<bits/stdc++.h>
using namespace std;
struct position{;
    long long int x,y;
};
int main(){
    struct position bird,start,endp,movep;
    cin>>bird.x>>bird.y;
    cin>>start.x>>start.y>>endp.x>>endp.y;
    if(start.x<=bird.x && bird.x<=endp.x){ //在X的區段
        movep.x=0;
        movep.y=min(abs(start.y-bird.y),abs(endp.y-bird.y));
    }else if (start.y<=bird.y && bird.y<=endp.y) { //在Y的區段
        movep.y=0;
        movep.x=min(abs(start.x-bird.x),abs(endp.x-bird.x));
    }else{ //都不是
        movep.x=min(abs(start.x-bird.x),abs(endp.x-bird.x));
        movep.y=min(abs(start.y-bird.y),abs(endp.y-bird.y));
    }
    cout<<movep.x+movep.y<<endl;
}

### 4.字串加密 `c518`
> 2017高雄市資訊學科能力複賽
> 題目和範例測資如下:
> https://zerojudge.tw/ShowProblem?problemid=c518
>

//行不通50分，偶之後再想。
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string code;
    string tmpBefore;
    string tmpafter;
    cin>>code>>code>>code>>tmpBefore>>tmpafter;
    for(int j=0; j<tmpafter.length(); j++) {
        for(int i=0; i<code.length(); i++) {
            if(tmpBefore[j]==code[i]) {
                code[i]=tmpafter[j];
            }
        }
    }
    cout<<code<<endl;
}

> 念誠ㄉ好捧油乃方ㄉ老師:楷宗做ㄉ，超級厲害ㄉ :100:

//字串加密
#include<iostream>
#include<string>
using namespace std;

main(){
	int n,m;
	char map[128];
	for (int i=0;i<128;i++){
		map[i]=(char)i;
	}
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	string msg;
	cin >> msg;
	string before,after;
	cin >> before >> after;
	
	
	for (int i=m-1;i>=0;i--){
		map[before[i]]=map[after[i]];	
	}
	for (int i=0;i<n;i++){
		msg[i]=map[msg[i]];	
	}
	cout << msg << endl;
	return 0;
}