# 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
窮舉比較開始的起點 就類似下圖
但與上面的圖不同的是，我們就算檢查到不一樣的也要跑完 不能跳過 這樣才能算他們之間最小的差距
:::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
將一個 $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 這個矩陣
翻轉的部分，可以用一個技巧，就是反著將測資讀進來。
這樣即可完成翻轉的操作。
最後就是將其相乘，可以直接在最外層 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:
:::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;
}
```
:::
---
Sign in with Wallet
Connect another wallet