---
# System prepended metadata

title: S3 演算法 week 3
tags: [S3 公開資源]

---

# S3 演算法 week 3
###### tags: `S3 公開資源`

:::info
時間：10/30 9:00 ~ 17:00
地點：成大資工系新館 **65304** 教室
主題：複雜度分析與程式技巧
直播連結：
:::

## 課程內容
- 複雜度分析
- 程式技巧
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS


## 注意事項
1. 請先預習講義序章及初章前半第四章之後（含第四張）的內容，並且完成第一次上課的必做題
2. 第二堂課的必做題題解放在第二堂課的指引：https://hackmd.io/@SCIST/H1AuBbJmi
3. 所有上課相關連結都會放在資源彙整裡：https://hackmd.io/@SCIST/rykldedMj
4. 上課期間請全程配戴口罩
5. 建議學員可以帶自己的筆電，以減少重新設定的時間成本
6. 請假表單：https://forms.gle/2ESVuTezcHCK959H6

# 必作題題解

## 初章 - 第六節

[TOC]

### [Kattis Autori](https://open.kattis.com/problems/autori)

撰寫者：Ateto

逐字檢查只要出現 `-` 即輸出他的下一個字元。

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
signed main() {
	string s;
	cin >> s;
	cout << s[0];
	for(int i=0; i<s.size(); ++i) {
		if(s[i] == '-') cout << s[i+1];
	}
	cout << '\n';
	return 0;
}
```
:::

---

### [Kattis Hissing Microphone]()

撰寫者：Ateto

目標是要檢查字串是否包含 `ss` 字串，
方法是只要出現 `s` 就去檢查下一個字元是否為 `s`。

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
signed main() {
	string s;
	bool flag = false;
	cin >> s;
	for(int i=0; i+1<s.size(); ++i) {
		if(s[i]=='s' && s[i+1]=='s') {
			flag = true;
		}
	}
	if(flag) cout << "hiss\n";
	else cout << "no hiss\n";
	return 0;
}
```
:::

---

### [TOJ 5](https://toj.tfcis.org/oj/pro/5/)

撰寫者：Ateto

cin或scanf一次只能讀一個字串(讀取規則如一般cin 遇到空白或是換行(\n)就會判斷成一個字串)
如果要一次讀整行要用getline。(只會讀到換行為止)

getline語法：
||getline(cin, your_variable)||

::: spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    cout << "Hello ," << s << " !\n";
    return 0;
}
```
:::

---

### [TOJ 92](https://toj.tfcis.org/oj/pro/92/)

撰寫者：Ateto

就注意輸出有空白的部分即可。

:::spoiler 參考程式碼
```cpp =
#include<iostream>
using namespace std;
int main() {
    string name1, name2, name3;
    cin >> name1 >> name2 >> name3;
    cout << "Hello, " << name1 << ", " << name2 << ", and " << name3 << "!\n";
    return 0;
}
```
:::

---

### [Kattis Quick Estimates](https://open.kattis.com/problems/quickestimate)

撰寫者：Ateto

當數字大到 $10^100$ 之類的數字 顯然會超出long long範圍的數字，基本上就 "一定要用" string 讀進來處理。
否則直接用整數型別讀進來溢位了更是沒有意義。
||用字串輸入後直接輸出字串長度||

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
signed main() {
	string s;
	int n;
	cin >> n;
	while(n--) {
		cin >> s;
		cout << s.size() << '\n';
	}
	return 0;
}
```
:::

---

### [Kattis Detailed Differences](https://open.kattis.com/problems/detaileddifferences)

撰寫者：Ateto

逐字對兩個字串做比對，並注意每筆case要換行的部分。

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
signed main() {
	string str1, str2;
	int t, first=true;
	cin >> t;
	while(t--) {
		if(first) first = false;
		else cout << '\n';
		cin >> str1 >> str2;
		cout << str1 << '\n' << str2 << '\n';
		for(int i=0; i<str1.size(); ++i) {
			if(str1[i] == str2[i]) cout << '.';
			else cout << '*';
		}
		cout << '\n';
	}
	return 0;
}
```
:::

---

### [TOJ 103](https://toj.tfcis.org/oj/pro/103/)

撰寫者：Koying

用一個變數判斷甜度、冰塊這兩個有幾個是相同的

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
signed main() 
{
    string s[4];
    int cnt = 0;
    for (int i = 0; i < 4; i++)
        cin >> s[i];
    
    cnt += (s[0] == s[2]);
    cnt += (s[1] == s[3]);
    
    if (cnt == 0)
        cout << "OTZ" << '\n';
    else if (cnt == 1) 
        cout << "=~=" << '\n';
    else
        cout << "GOOD" << '\n';
	return 0;
}
```
:::

---

### [Kattis lineup](https://open.kattis.com/problems/lineup)

撰寫者：Jun-an

利用迴圈依序比較每個字串跟前一個字串的大小關係
如果越來越大 -> INCREASING
越來越小 -> DECREASING
沒有規律 -> NEITHER

:::spoiler 參考程式碼
```cpp=
#include <iostream>

using namespace std;

int main() {
    bool increase = false, neither = false;
    
    int t;
    cin >> t;
    
    string prev, curr;
    cin >> prev >> curr; //如果題目 n=1時，這個方法會有問題(因為沒有那麼多數字可以讀進來)，就會TLE。
    
    if (curr > prev) {
        increase = true;
    }
    
    for (int i = 2; i < t; ++i) {
        prev = curr;
        cin >> curr;
        
        if (prev > curr && increase) {
            neither = true;
        }
        else if (prev < curr && !increase) {
            neither = true;
        }
        
        if (neither) {
            break; //這裡break時，測資有可能是沒讀完的在遇到多重輸入時就會有問題~
        }
    }
    
    if (neither) {
        cout << "NEITHER\n";
    }
    else {
        if (increase) {
            cout << "INCREASING\n";
        }
        else {
            cout << "DECREASING\n";
        }
    }
    
    return 0;
}
```
:::

---

### [Kattis simonsays](https://open.kattis.com/problems/simonsays)

撰寫者：fishhh

先設一個字串為 "Simon says" 方便接下來的判斷，再用一個for迴圈從頭判斷是否符合題目要求
最後，輸出即可~

:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
const int MATCH = 1;
const int NOT_MATCH = 0;
int main(){
	string s,key="Simon says";
	int n;
	cin>>n;
	getline(cin,s); //單純將換行符號讀掉
    //原本用cin.ignore() 沒有 geline 安全建議不要使用
	for(int i=0;i<n;i++){
		bool match=MATCH;
		getline(cin,s);
		for(int i=0;i<key.size();i++){
			if(s[i]!=key[i]){
				match=NOT_MATCH;
				break;
			}
		}
		if(match){
			for(int i=key.size();i<s.size();i++){
				cout<<s[i];
			}
			cout<<"\n";
		}
	}
}
```
:::

---

### [TOJ 100](https://toj.tfcis.org/oj/pro/100/)

撰寫者：Eason

利用ASCII 碼的特性
英文字母具有連續性
所以把字母轉ASCII
再減1 就好

然後要特別判斷 'A'

~~你要用26個條件判斷我也是不反對啦~~

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

int main(){
    char c;
    cin >> c;
    if (c == 'A') cout << '@' << '\n';
    else cout << (char)(c - 1) << '\n';
    return 0;
}
```
:::

---
### [TOJ 127](https://toj.tfcis.org/oj/pro/127/)

撰寫者：fishhh

把每個字元的ascii+$k$(偏移量) 即可
然後再把這個字元補回'A'~'Z'

:::spoiler 參考程式
```cpp=
#include <iostream>
using namespace std;
int main(){
    string a;
    int p;
    cin>>p>>a;
    for(int i=0;i<a.length();i++){
        a[i]-=p;
        while(a[i]<'A'){
            a[i]+=26;
        }
        while(a[i]>'Z'){
            a[i]-=26;
        }
        cout<<a[i];
    }
    cout<<"\n";
}
```
:::

---

### [Kattis anewalphabet](https://open.kattis.com/problems/anewalphabet)

撰寫者：小麥

此題的測資要記得使用getline，因為是一整行的。
先建表在一個字一個字判斷。

:::spoiler 參考程式
```cpp=
#include <iostream>

using namespace std;

int main() {

    string table[26] = {"@", "8", "(", "|)", "3", "#", "6", "[-]", "|", "_|", "|<", "1", 
                    "[]\\/[]", "[]\\[]", "0", "|D", "(,)", "|Z", "$", "']['", "|_|", 
                    "\\/", "\\/\\/", "}{", "`/", "2"};

    string str;
    getline(cin, str);

    for (int i = 0; i < str.length(); i++) {
        if (str[i] >= 'A' && str[i] <= 'Z') {
            cout << (table[str[i] - 'A']); 
        }
        else if (str[i] >= 'a' && str[i] <= 'z') {
            cout << table[str[i] - 'a'];
        }
        else {
            cout << str[i];
        }
    }

    return 0;

}
```
:::

---

### [toj113](https://toj.tfcis.org/oj/pro/113/)

撰寫者：Eason

找出P 的位置（假設是pos）
最後一項如果是L 就跟pos - 1 交換
最後一項如果是R 就跟pos + 1 交換

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    string p;
    cin >> p;
    int pos;
    for (int i = 0; i < p.size(); i++){// 尋找P的位置
        if (p[i] == 'P'){
            pos = i;
        }
    }
    char dir;
    cin >> dir;
    if (dir == 'L'){
        char temp = p[pos];
        p[pos] = p[pos - 1];
        p[pos - 1] = temp;
    }
    else{
        char temp = p[pos];
        p[pos] = p[pos + 1];
        p[pos + 1] = temp;
    }
    cout << p << '\n';
    return 0;
}
```
:::


--- 

### [TOJ 18](https://toj.tfcis.org/oj/pro/18/)

撰寫者：Jun-an

如果輸入的字串是強效咒文就要在前面加上 "SETUP! "
強效咒文其實就是迴文 (反過來也長的一模一樣)
你需要先把字串裡面的字母拿出來變成一個新的字串
大小寫視為相同

:::spoiler 參考程式碼
```cpp=
#include <iostream>

using namespace std;

int main() {
    string s;
    
    while (getline(cin, s)) {
        string tmp;
        for (int i = 0; i < s.size(); ++i) {
            if ('A' <= s[i] && s[i] <= 'Z') {
                tmp += s[i] + 32;
            }
            else if ('a' <= s[i] && s[i] <= 'z') {
                tmp += s[i];
            }
        }
        
        bool is_palindrome = true;
        int Len = tmp.size();
        
        for (int i = 0; i <= Len / 2; ++i) {
            if (tmp[i] != tmp[Len - i - 1]) {
                is_palindrome = false;
                break;
            }
        }
        
        if(is_palindrome) {
            cout << "SETUP! " + s << '\n';
        }
        else {
            cout << s << '\n';
        }
    }
}
```
:::

---

### [Kattis smartphone](https://open.kattis.com/problems/smartphone)

撰寫者：fishhh

首先要瞭解題目的意思
然後直接實作即可
:::spoiler 參考程式碼
``` cpp=
#include<iostream>
using namespace std;
int main(){
	bool k;
	int tap[10],n;
	string arr[10];
	cin>>n;
	for(int u=0;u<n;u++){
		for(int j=0;j<5;j++){
			cin>>arr[j];
			tap[j]=0;
		}
		for(int h=1;h<=4;h++){
			k=0;
			if(h!=1)tap[h]++;
			for(int i=0;i<arr[0].length()&&i<arr[h].length();i++){
				if(arr[0][i]!=arr[h][i]){
					k=1;
					tap[h]+=arr[0].size()-i+arr[h].size()-i;
					break;			
				}
			}
			if(!k){
				if(arr[h].length()>=arr[0].length()){
					tap[h]+=arr[h].length()-arr[0].length();
				}
				else{
					tap[h]+=arr[0].length()-arr[h].length();
				}	
			}
		}
		int ans=1000;
		for(int i=1;i<=4;i++){
			if(tap[i]<ans){
				ans=tap[i];
			}
		}
		cout<<ans<<"\n";
	}
}
```
:::

---

### [Kattis pokerhand](https://open.kattis.com/problems/pokerhand)

撰寫者：Eason 

判斷每張牌的第一個字元是否一樣就好

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

int main(){
    string s[5];
    for (int i = 0; i < 5; i++){
        cin >> s[i];
    }
    int max = 0;
    for (int i = 0; i < 5; i++){
        int sum = 1; //這裡要初始化為1，是因為自己要算進去
        for (int j = 0; j < i; j++){
            if(s[i][0] == s[j][0]){ 
                sum++;
            }
        }
        if(sum > max) max = sum;
    }
    cout << max << '\n';
    return 0;
}
```
解釋一下第14行，因為我是用字串陣列，所以第1個中括號是第幾個字串，第2個中括號是該字串的第幾個字元
:::

---

### [Trik](https://open.kattis.com/problems/trik)

撰寫者：小麥

用一個陣列作模擬即可。

:::spoiler 參考程式碼
```cpp
#include <iostream>

using namespace std;

int main() {

    int arr[3] = {1, 0, 0};

    string str;
    cin >> str;

    for (int i = 0; i < str.length(); i++) {
        if (str[i] == 'A') {
            int temp = arr[0];
            arr[0] = arr[1];
            arr[1] = temp;
        }
        else if (str[i] == 'B') {
            int temp = arr[1];
            arr[1] = arr[2];
            arr[2] = temp;
        }
        else {
            int temp = arr[0];
            arr[0] = arr[2];
            arr[2] = temp;
        }
    }

    for (int i = 0; i < 3; i++) {
        if (arr[i]) {
            cout << (i+1);
        }
    }

    return 0;

}
```
:::

---

### [Kattis permutationencryption](https://open.kattis.com/problems/permutationencryption)

撰寫者：fishhh

把字串長度補成 $n$ 的倍數 就可以直接操作ㄌ~

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
int main(){
	int n,key[100];
	string k;
	while(cin>>n){
		if(n==0){
			return 0;
		}
		for(int i=0;i<n;i++){
			cin>>key[i];
			key[i]--;
		}
		getline(cin,k);//讀掉換行
		getline(cin,k);
		cout<<"'";
		while(k.length()%n!=0)k+=" "; // 或是用 resize 也行!
		for(int i=0;i<k.length();i+=n){
			for(int x=0;x<n;x++){
				cout<<k[i+key[x]]; //這裡的話 建議先用一個字串把答案加起來 不然一直做輸出可能TLE~
			}
		}
		cout<<"'\n";
	}
}
```
:::


---

### [UVa 11577](http://domen111.github.io/UVa-Easy-Viewer/?11577)

撰寫者：小麥

開一個陣列把每個字的出現數量記起來，在取最大值。

:::spoiler 參考程式碼
```cpp=
#include <iostream>

using namespace std;

int arr[26+1];

int main() {

    int t;
    string str;
    getline(cin, str);
    t = stoi(str); //字串轉整數
    while (t--) {

        for (int i = 0; i < 26; i++) {
            arr[i] = 0;
        }

        string str;
        getline(cin, str);

        for (int i = 0; i < str.length(); i++) {
            if (str[i] >= 'A' && str[i] <= 'Z') {
                arr[str[i] - 'A']++;
                continue;
            }
            else if(str[i] >= 'a' && str[i] <='z') {
                arr[str[i] - 'a']++;
            }
        }
        
        int maxi = (int) -1e9; //1e9相當於 -1*10^9
        for (int i = 0; i < 26; i++) {
            if (arr[i] > maxi) {
                maxi = arr[i];
            }
        }

        for (int i = 0; i < 26; i++) {
            if (arr[i] >= maxi) {
                cout << char('a' + i);
            }
        }
        cout << "\n";
    }

    return 0;

}
```
:::

---

### [No Judge 最小改變次數](https://hackmd.io/@sa072686/cp/%2FRCDOBMTWQNm_nw2KBk96zw#%E6%9C%80%E5%B0%8F%E6%94%B9%E8%AE%8A%E6%AC%A1%E6%95%B8)

撰寫者：fishhh

窮舉比較開始的起點 就類似下圖
![](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWdrci5jbi1iai51ZmlsZW9zLmNvbS9iNjE0ZWRiZS04NjEyLTRiODAtODg5YS01ZjBlZjljMDg5ZDcuZ2lm)
但與上面的圖不同的是，我們就算檢查到不一樣的也要跑完 不能跳過 這樣才能算他們之間最小的差距

:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
int main(){
	string a,b;
	cin>>a>>b;
	int ans=10000;
	for(int i=0;i<a.size()-b.size();i++){
		int cost=0;
		for(int x=0;x<b.size();x++){
			if(b[x]!=a[x+i]){
				cost++;
			}
		}
		if(cost<ans){
			ans=cost;
		}
	}
	cout<<ans<<" times."; // ans=1||ans=0 應該要輸出單數?XD
}
```
:::

---

### [Kattis keytocrypto](https://open.kattis.com/problems/keytocrypto)

撰寫者：Jun-an

![](https://hackmd.io/_uploads/SyjO-9YQo.png)

將一個 $message$ 的每一個字元分別加上 $key$ 的每一個字元
就會得到一個密文 $ciphertext$
$Ex. S + A = A$
$83 + 65 = 148$
但是 $148$ 已經超出 $A$ ~ $Z$，因此需要再減掉 $65$ 轉成 $A$
而 $key$ 是一個字串加上 $message$

題目會給你 $key$ 前面的字串跟 $ciphertext$，你需要輸出 $message$
上面有提到 $key =$ 字串 $+$ $message$
所以可以先利用 $ciphertext$ 的前面幾個字元先跟 $key$ 的字串做解密
接著再放到題目給的 $key$ 後面
:::spoiler 參考程式碼
```cpp=
#include <iostream>

using namespace std;

int main() {
    string ciphertext, key;
    cin >> ciphertext >> key;

    int textLen = ciphertext.size();
    string message;
    for (int i = 0; i < textLen; ++i) {
        message += (char)((ciphertext[i] + 26 - key[i]) % 26 + 'A');
        key += (char)((ciphertext[i] + 26 - key[i]) % 26 + 'A');
    }

    cout << message << '\n';

    return 0;
}
```
:::

---

## 初章-間章

### [TOJ 114](https://toj.tfcis.org/oj/pro/114/)

撰寫者：Eason

先建一個陣列
輸入完之後用迴圈掃過每一行、每一列

其中每一行可以從索引值2 開始找
然後比較當前那格跟前兩格是否相同

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

int arr[5][6];

int main(){
    for (int i = 0; i < 5; i++){
        for (int j = 0; j < 6; j++){
          cin >> arr[i][j];
        }
    }
    
    bool is_found = false;
    for (int i = 0; i < 5; i++){
        for (int j = 2; j < 6; j++){
            if (arr[i][j] == arr[i][j - 1] && arr[i][j] == arr[i][j - 2]){
                is_found = true;
                break;
            }
        }
        if (is_found) break;
    }
    
    if (!is_found){
        for (int j = 0; j < 6; j++){
            for (int i = 2; i < 5; i++){
                if(arr[i][j] == arr[i - 1][j] && arr[i][j] == arr[i - 2][j]){
                    is_found = true;
                    break;
                }
            }
            if (is_found) break;
        }
    }
    if (is_found) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}
```
**找到之後將is_found 改為true**
若is_found 最後為true 就表示沒找到，則輸出Yes
若is_found 最後為false 就表示沒找到，則輸出No
:::

---

### [Kattis cudoviste](https://open.kattis.com/problems/cudoviste)

撰寫者：fishhh

對於地圖上的每個點當作是2x2的左上角。
去記錄說每個點當作左上角時壓到幾台車。
:warning:
注意會有一些點當作左上角時會壓到房子或是超出邊界，記得要先判斷!

:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
int main(){
	int r,c;
	cin>>r>>c;
	string map[60];
	for(int i=0;i<r;i++){
		cin>>map[i];
	}
	int ans[6]={};
	int cx[]={0,1,1,0},cy[]={1,0,1,0}; //方便未來窮舉
	for(int y=0;y<r;y++){
		for(int x=0;x<c;x++){ // 窮舉每個點當作4x4的左上角
			int crush=0; // 紀錄壓到幾台車
			bool vaild=true; // 是否壓到房子 或者是 是否超出邊界
			for(int change=0;change<4;change++){ // 找出 x,y 當左上角時的所有地方
				int nx=x+cx[change],ny=y+cy[change];
				if(nx<0||ny<0||nx>=c||ny>=r){ // 超出邊界了 直接不算
					vaild=false; // 記得標註說這個不算數
					break;
				}
				if(map[ny][nx]=='#'){ //壓到房子了!
					vaild=false;
					break;
				}
				else if(map[ny][nx]=='X'){
					crush++;
				}
			}
			if(vaild){
				ans[crush]++;
			}
		}
	}

	for(int i=0;i<5;i++){
		cout<<ans[i]<<"\n";
	}
}
```
:::

---

### [Kattis mirror](https://open.kattis.com/problems/mirror)

撰寫者：小麥

倒放即可

:::spoiler 參考程式碼
```cpp=
#include <iostream>

using namespace std;

int main() {

    int t;
    cin >> t;
    int times = 1;
    while (t--) {
        cout << "Test " << (times++) << "\n";
        int n, m;
        cin >> n >> m;
        char arr[30][30];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> arr[i][j];
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                cout << arr[i][j];
            }
            cout << "\n";
        }
    }

    return 0;

}
```
:::

---

### [No Judge 俄羅斯方塊](https://hackmd.io/@sa072686/cp/%2FfaPENjvdTS6YIk1cYc4FkQ#%E4%BF%84%E7%BE%85%E6%96%AF%E6%96%B9%E5%A1%8A)

撰寫者：fishhh

將沒被消去的行數堆疊起來即可。

:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
int main(){
	int n,idx=0;
	cin>>n;
	string ans[40],s,blank="..........",full="##########";
	int cnt=0;
	for(int i=0;i<n;i++){
		cin>>s;
		if(s==full){
			cnt++;
		}
		else{
			ans[idx]=s;
			idx++;
		}
	}

	cout<<"remove "<<idx-1<<" rows.\n";
	for(int i=0;i<n-idx;i++){
		cout<<blank<<"\n";
	}
	for(int i=0;i<idx;i++){
		cout<<ans[i]<<"\n";
	}
}
```
:::

---

### [UVa 10189](http://domen111.github.io/UVa-Easy-Viewer/?10189)

撰寫者：fishhh

就是一題簡單的實作題，其中有一個小技巧就是將已經有地雷的地方設為 -100 這樣我們就不用在做增加的時候去特判它。

:::spoiler 參考程式
```cpp=
#include<iostream>

using namespace std;

int main(){
	int n, m, field_num = 1;
	string s;
	while( cin>>n>>m && !(n == 0 && m == 0) ){
		if( field_num != 1){
			cout<<"\n";
		}

		int field[200][200] = {};
		
		for( int i = 1 ; i <= n ; i++ ){
			cin>>s;
			for( int j = 1 ; j <= m ; j++ ){
				if( s[j-1] == '*' ){
					field[i][j] = -100 ; // 小技巧
					for( int k = -1 ; k <= 1 ; k++ ){
						for( int l = -1 ; l <= 1 ;l++ ){
							field[i+k][j+l]++;
						}
					}
				}
			}
		}

		cout<<"Field #"<<field_num<<":\n";
		field_num++;

		for( int i = 1 ; i <= n ; i++ ){
			for( int j = 1 ; j <= m ; j++ ){
				if( field[i][j] < 0 ){
					cout<<"*";
				}
				else{
					cout<<field[i][j];
				}
			}
			cout<<"\n";
		}
	}
	return 0;
}
```

:::

---
### [Kattis prva](https://open.kattis.com/problems/prva)

撰寫者：小麥

:::spoiler 參考程式
```cpp=
#include <iostream>

using namespace std;

int main() {

    int n, m;
    cin >> n >> m;

    string str[20];

    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }

    string ans = "";
    for (int i = 0; i < n; i++) {
        string temp = "";
        for (int j = 0; j < m; j++) {
            if (str[i][j] != '#') {
                temp = temp + str[i][j];
                continue;
            }
            if (temp.length() >= 2) {
                if (ans == "") {
                    ans = temp;
                    temp = "";
                    continue;
                }
                if (ans > temp) {
                    ans = temp;
                }
            }
            temp = "";
        }
        //要再判一次
        if (temp.length() >= 2) {
            if (ans == "") {
                ans = temp;
                temp = "";
                continue;
            }
            if (ans > temp) {
                ans = temp;
            }
        }
    }

    for (int j = 0; j < m; j++) {
        string temp = "";
        for (int i = 0; i < n; i++) {
            if (str[i][j] != '#') {
                temp = temp + str[i][j];
                continue;
            }
            if (temp.length() >= 2) {
                if (ans == "") {
                    ans = temp;
                    temp = "";
                    continue;
                }
                if (ans > temp) {
                    ans = temp;
                }
            }   
            temp = "";
        }
        //要再判一次
        if (temp.length() >= 2) {
            if (ans == "") {
                ans = temp;
                temp = "";
                continue;
            }
            if (ans > temp) {
                ans = temp;
            }
        }  
    }

    cout << ans << "\n";

    return 0;

}
```
:::

---

### [Kattis Image Processing](https://open.kattis.com/problems/imageprocessing)

撰寫者：fishhh

題目要做乘法運算
注意提敘的這行，他有說要翻轉 kernel 這個矩陣
![](https://hackmd.io/_uploads/rk-X7OoVo.png)

翻轉的部分，可以用一個技巧，就是反著將測資讀進來。
這樣即可完成翻轉的操作。

最後就是將其相乘，可以直接在最外層 for 迴圈的地方限制，就不會有超出邊界狀況。

:::spoiler
```cpp=
#include<iostream>
using namespace std;
int main(){
    int a,b,c,d,tot,arr[100][100],ar2[100][100];
    cin>>a>>b>>c>>d;
    for(int x=0;x<a;x++){
        for(int y=0;y<b;y++){
            cin>>arr[x][y];
        }
    }
    for(int x=c-1;x>=0;x--){ //倒著放入陣列
        for(int y=d-1;y>=0;y--){
            cin>>ar2[x][y];
        }
    }
    for(int x=0;x<a-c+1;x++){ //限制其不要超出邊界
        for(int y=0;y<b-d+1;y++){ 
            tot=0;
            for(int x1=0;x1<c;x1++){
                for(int y1=0;y1<d;y1++){
                    tot+=arr[x+x1][y+y1]*ar2[x1][y1];   
                }
            }   
            cout<<tot;
            if(y<b-d)cout<<" ";
        }
        cout<<"\n";
    }
}
```
:::

---

## 初章 - 第七節

### [Kattis Sibice](https://open.kattis.com/problems/sibice)

撰寫者：Eason

火柴盒都是長方形
所以要判斷能不能把火柴放進火柴盒
就是判斷火柴盒的斜邊是否大於火柴就好:place_of_worship: 
![](https://hackmd.io/_uploads/H1Slc5iVi.png)


:::spoiler 參考程式碼
```cpp=
#include<iostream>
#include<math.h>
using namespace std;

int main(){
    int n, w, h;
    cin >> n >> w >> h;
    double area;
    area = sqrt (w * w + h * h);
    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        if (temp <= area) cout << "DA\n";
        else cout << "NE\n";
    }
    return 0;
}
```
:::

---

### [UVa 10370](http://domen111.github.io/UVa-Easy-Viewer/?10370)

撰寫者：小麥

計數 分數 > (總合 / 總人數) 的數量 在除於總人數

小數點位數控制使用
#include \<iomanip\>
cout << fixed << setprecision(3);

:::spoiler 參考程式碼
```cpp=
#include <iostream>
#include <iomanip>

using namespace std;

int main() {

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        int arr[1100];
        double sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
            sum += arr[i];
        }
        sum /= n;

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > sum) {
                cnt++;
            }
        }
        cout << fixed << setprecision(3) << ((double) cnt / n * 100) << "%" << "\n";
    }    

    return 0;

}
```
:::

---

### [Uva476](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=417)

撰寫者：Eason

假設當前在第 $i$ 個座標
且矩形的左右上下分別為 $x_{a}$, $x_{b}$, $y_{a}$, $y_{b}$
判斷 $x_{i}$ 是否在矩形的 $x_{a}$ ~ $x_{b}$ 的範圍內
再判斷 $y_{i}$ 是否在矩形的 $y_{a}$ ~ $y_{b}$ 的範圍內

**小技巧：為了避免浮點數誤差，可以把每個數字都乘10 再存到整數型態**

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

long long rec[15][5];
 
int main(){
    char t;
    int count = 0;
    while (cin >> t){
        if (t == '*') break;
        for (int i = 0; i < 4; i++){
            double temp;
            cin >> temp;
            temp *= 10;
            rec[count][i] = temp;
        }
        count++;
    }
    double tempx, tempy;
    int round = 1;
    while (cin >> tempx >> tempy){
        long long x = tempx * 10, y = tempy * 10;
        if (x == 99999 && y == 99999){
            break;
        }
        bool is_contain = false;
        for (int i = 0; i < count; i++){
            if (x > rec[i][0] && x < rec[i][2]){
                if (y < rec[i][1] && y > rec[i][3]){
                    cout << "Point " << round << " is contained in figure " << i + 1 << '\n';
                    is_contain = true;
                }
            }
        }
        if (!is_contain){
            cout << "Point " << round << " is not contained in any figure\n";
        }
        round++;
    }
    return 0;
}

```
:::

---
