---
# System prepended metadata

title: APCS 2016年10月題解
tags: [APCS]

---

# APCS 2016年10月題解
## 第一題 三角形辨別
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c294
### 解套
N/A
### 題目分析
本題分成兩個部分：決定大小順序和判斷三角形種類

因為只有三個數字，所以在大小方面最小的就對三邊取最小值、最大就對三邊取最大值、而中間的我是用三邊邊長總合減最大與最小來計算

判斷三型種類則是用簡單的if依序判斷就好

時間複雜度$O(1)$
### 解題流程
輸入$→$排序$→$判斷、輸出
### 解題過程
#### 變數宣告
```cpp=3
int a,b,c,d,e,f;
```
d,e,f吃輸入；a,b,c存排序後的邊長
#### 輸入
```cpp=5
cin>>d>>e>>f;
```
#### 排序
```cpp=6
a=min({d,e,f});
c=max({d,e,f});
b=d+e+f-a-c;
```
方法同前述
#### 輸出、判斷
```cpp=9
cout<<a<<" "<<b<<" "<<c<<"\n";
if(a+b<=c)cout<<"No";
else{
    a*=a;b*=b;c*=c;
    if(a+b<c)cout<<"Obtuse";
    else if(a+b==c)cout<<"Right";
    else cout<<"Acute";
}
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f;
int main(){
    cin>>d>>e>>f;
    a=min({d,e,f});
    c=max({d,e,f});
    b=d+e+f-a-c;
    cout<<a<<" "<<b<<" "<<c<<"\n";
    if(a+b<=c)cout<<"No";
    else{
        a*=a;b*=b;c*=c;
        if(a+b<c)cout<<"Obtuse";
        else if(a+b==c)cout<<"Right";
        else cout<<"Acute";
    }
}
```
## 第二題 最大和
### 題目敘述 
https://zerojudge.tw/ShowProblem?problemid=c295
### 解套
N/A
### 題目分析
直接操作即可。
最直觀的作法會是用二維陣列存所有數字，不過我用稍微難一點的方法，就是對每組數字邊吃輸入更新最大值，並把最大值加到總和並存起來，最後一個一個判斷是否整除總和即可

另外因為要求結尾不能有空格，所以答案先全部存起來再輸出

時間複雜度$O(mn)$
### 解題流程
輸入、決定最大值$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,sum=0,inp;
vector<int>picked,last;
```
n,m同題述，sum存總和，inp是輸入用，picked存被選到的數字，last存能整除的
#### 輸入、更新
```cpp=6
cin>>n>>m;
picked.assign(n,0);
for(int i=0;i<n;i++){
    int mx=INT_MIN;
    for(int j=0;j<m;j++){
        cin>>inp;
        mx=max(mx,inp);
    }
    picked[i]=mx;
    sum+=mx;
}
```
依照n決定picked的大小(第7行)
接著對每組數字，先設一個最大值，並邊輸入邊更新最大值，最後把它加進總和並放入picked
#### 輸出
``` cpp=17
cout<<sum<<"\n";
for(int i:picked)if(sum%i==0)last.push_back(i);
if(last.empty())cout<<-1;
else{
    cout<<last[0];
    for(int i=1;i<last.size();i++)cout<<" "<<last[i];
}
```
先輸出總和(第17行)
接著把能整除總和的放進last(第18行)
然後按題述輸出即可(注意沒有符合的要輸出-1，且結尾不能有空白)
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0,inp;
vector<int>picked,last;
int main(){
    cin>>n>>m;
    picked.assign(n,0);
    for(int i=0;i<n;i++){
        int mx=INT_MIN;
        for(int j=0;j<m;j++){
            cin>>inp;
            mx=max(mx,inp);
        }
        picked[i]=mx;
        sum+=mx;
    }
    cout<<sum<<"\n";
    for(int i:picked)if(sum%i==0)last.push_back(i);
    if(last.empty())cout<<-1;
    else{
        cout<<last[0];
        for(int i=1;i<last.size();i++)cout<<" "<<last[i];
    }
}
```
## 第三題 定時K彈
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c296
### 解套
約瑟夫問題
### 題目分析
基本上跟經典的[約瑟夫問題](https://oi-wiki.org/misc/josephus/)非常像，因此只需要對約瑟夫問題的$O(n)$解法做一些些微的調整就好

如果最後只剩一個人解法會長這樣：
```cpp
int josephus(int n,int m) {
     int res=0;
     for(int i=1;i<=n;i++)res=(res+m)%i;
     return res;
}
```
其中n代表有幾個人，m代表一次屬幾個人

但這題只會去除k個人，而且第一個人編號是1，所我們稍微做一下改寫：
```cpp
int josephus(int n,int m) {
     int res=0;
     for(int i=n-k+1;i<=n;i++)res=(res+m)%i;
     return res+1;
}
```
把i=1～n改成i=n-k+1讓我們只去除k個人，要注意的是不能改成i=1～k
(因為對i取模是在處理剩下人數)
最後加一是為了變回1-base

時間複雜度$O(k)$
### 解題流程
輸入$→$套公式$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,k;
```
變數名同題述
#### 輸入
```cpp=5
cin>>n>>m>>k;
```
#### 找答案、輸出
```cpp=6
int tmp=0;
for(int i=n-k+1;i<=n;i++)tmp=(tmp+m)%i;
cout<<tmp+1<<"\n";
```
跟前面一樣，只是不是用函式的形式呈現
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main(){
    cin>>n>>m>>k;
    int tmp=0;
    for(int i=n-k+1;i<=n;i++)tmp=(tmp+m)%i;
    cout<<tmp+1<<"\n";
}
```
## 第四題 棒球遊戲
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c297
### 解套
N/A
### 題目分析
這題到底是想考甚麼...?
早期的APCS都這樣嗎?
唯一比較要注意的是打擊順序是由上而下，由左而右的，所以不能直接吃輸入
我的作法是用9個vector存每個打者的狀況，再合併起來處理
其餘就直接照規則做就好

時間複雜度$O(1)$(最多只有45個數字)
### 解題流程
輸入$→$調整順序$→$按規則計算分數$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int a,b,cnt=0,pts=0,outs=0;
bool one=0,two=0,three=0;
vector<string>v[9],arr;
```
a,b輸入用，cnt紀錄有幾次打擊，pts紀錄分數，outs紀錄出局數，one,two,three紀錄一二三壘有沒有人，v存初始輸入，arr按順序存打擊狀態
#### 輸入
```cpp=7
for(int i=0;i<9;i++){
    cin>>a;
    cnt+=a;
    v[i].assign(a,"");
    for(int j=0;j<a;j++)cin>>v[i][j];
}
cin>>b;
```
#### 轉成按順序存
```cpp=14
for(int i=0;i<5&&cnt;i++){
    for(int j=0;j<9&&cnt;j++){
        arr.push_back(v[j][i]);
        cnt--;
    }
}
```
cnt確保不會多存導致記憶區間錯誤
#### 計算分數
```cpp=20
for(int i=0;i<arr.size()&&b>0;i++){
    if(arr[i]=="1B"){
        if(three){
            pts++;
            three=0;
        }
        if(two){
            three=1;
            two=0;
        }
        if(one){
            two=1;
            one=0;
        }
        one=1;
    }
    else if(arr[i]=="2B"){
        if(three){
            pts++;
            three=0;
        }
        if(two){
            pts++;
            two=0;
        }
        if(one){
            three=1;
            one=0;
        }
        two=1;
    }
    else if(arr[i]=="3B"){
        if(three){
            pts++;
            three=0;
        }
        if(two){
            pts++;
            two=0;
        }
        if(one){
            pts++;
            one=0;
        }
        three=1;
    }
    else if(arr[i]=="HR"){
        if(three){
            pts++;
            three=0;
        }
        if(two){
            pts++;
            two=0;
        }
        if(one){
            pts++;
            one=0;
        }
        pts++;
    }
    else{
        outs++;
        b--;
        if(outs%3==0)one=two=three=0;
    }
}
```
比較直接的做法，只是按照規則寫而已

雖然題目的三種出局分別給不同的代號，但統一處理即可，所以統一放在else裡面
需要特別注意的是如果出局數達到三的倍數就要清空壘包(第84行)
#### 輸出
```cpp=87
cout<<pts;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a,b,cnt=0,pts=0,outs=0;
bool one=0,two=0,three=0;
vector<string>v[9],arr;
int main(){
    for(int i=0;i<9;i++){
        cin>>a;
        cnt+=a;
        v[i].assign(a,"");
        for(int j=0;j<a;j++)cin>>v[i][j];
    }
    cin>>b;
    for(int i=0;i<5&&cnt;i++){
        for(int j=0;j<9&&cnt;j++){
            arr.push_back(v[j][i]);
            cnt--;
        }
    }
    for(int i=0;i<arr.size()&&b>0;i++){
        if(arr[i]=="1B"){
            if(three){
                pts++;
                three=0;
            }
            if(two){
                three=1;
                two=0;
            }
            if(one){
                two=1;
                one=0;
            }
            one=1;
        }
        else if(arr[i]=="2B"){
            if(three){
                pts++;
                three=0;
            }
            if(two){
                pts++;
                two=0;
            }
            if(one){
                three=1;
                one=0;
            }
            two=1;
        }
        else if(arr[i]=="3B"){
            if(three){
                pts++;
                three=0;
            }
            if(two){
                pts++;
                two=0;
            }
            if(one){
                pts++;
                one=0;
            }
            three=1;
        }
        else if(arr[i]=="HR"){
            if(three){
                pts++;
                three=0;
            }
            if(two){
                pts++;
                two=0;
            }
            if(one){
                pts++;
                one=0;
            }
            pts++;
        }
        else{
            outs++;
            b--;
            if(outs%3==0)one=two=three=0;
        }
    }
    cout<<pts;
}
```