# APCS 2016/10 題解
## ==三角形辨別==
### 題目
[三角形辨別](https://zerojudge.tw/ShowProblem?problemid=c294)
### 核心
條件判斷
### 思路

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int A[3];
    scanf("%d%d%d",A,A+1,A+2);
    sort(A,A+3);
    for(int i=0;i<3;i++) printf("%d ",A[i]);
    printf("\n");
    if(A[0]+A[1]<=A[2]) printf("No");
    else if(A[0]*A[0]+A[1]*A[1]==A[2]*A[2]) printf("Right");
    else if(A[0]*A[0]+A[1]*A[1]<A[2]*A[2]) printf("Obtuse");
    else printf("Acute");
}

## ==最大和==
### 題目
[最大和](https://zerojudge.tw/ShowProblem?problemid=c295)
### 核心
條件判斷
### 思路

#include<bits/stdc++.h>
using namespace std;
int num[20][20];
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    int S=0,maxNum[20];
    for(i=0;i<n;i++)
    {
        maxNum[i]=-1;
        for(j=0;j<m;j++)
        {
            scanf("%d",&num[i][j]);
            maxNum[i]=max(maxNum[i],num[i][j]);
        }
        S+=maxNum[i];
    }
    printf("%d\n",S);
    bool can=false;
    for(i=0;i<n;i++)
    {
        if(!(S%maxNum[i]))
        {
            printf("%d",maxNum[i]);
            can=true;
            break;
        }
    }
    for(i=i+1;i<n;i++)
    {
        if(!(S%maxNum[i])) printf(" %d",maxNum[i]),can=true;
    }
    if(!can) printf("-1");
}

## ==定時k彈==
### 題目
[定時k彈](https://zerojudge.tw/ShowProblem?problemid=c296)
### 核心
[約瑟夫問題](https://oi-wiki.org/misc/josephus/)
### 思路1
人數記n，幸運者記Lucky，上一個幸運者記lastLucky，下一個幸運者記:nextLucky，傳遞k次會爆炸。
若移除一人，則Lucky=(lastLucky+k)%n，因為(lastLucky+k-1)%n的人會被移除，再移除一人的話，則nextLucky=(Lucky+k)%(n-1)。
此時會發現一個問題，移除第二人開始，答案會變成當前順序值，記得處理。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main()
{
    cin>>n>>m>>k;
    vector<int> V;
    for(int i=1;i<=n;i++) V.push_back(i);
    int LuckyValue=1,LuckyIndex=0;
    for(int i=0;i<k;i++)
    {
        LuckyIndex=(LuckyIndex+m-1)%n;
        V.erase(V.begin()+LuckyIndex);
        if(LuckyIndex==n-1) LuckyIndex=0;
        LuckyValue=V[LuckyIndex];
        n--;
    }
    printf("%d\n",LuckyValue);
}

### 思路2(約瑟夫)
類似把思路1倒過來想，當人數有i時，tmp為(人數為i-1時的tmp+m)%i，也就是Lucky~i~=(Lucky~i-1~+m)%i，很奇妙的解法。

#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)
### 核心
模擬
### 思路
怪題。

#include<bits/stdc++.h>
using namespace std;
vector<string> info[9],turns;
int cnt=0,outs;
bool one=false,two=false,three=false;
int main()
{
    for(int i=0;i<9;i++)
    {
        int n;
        cin>>n;
        cnt+=n;
        info[i].assign(n,"");
        for(int j=0;j<n;j++) cin>>info[i][j];
    }
    cin>>outs;
    for(int i=0;i<5&&cnt;i++)
    {
        for(int j=0;j<9&&cnt;j++) turns.push_back(info[j][i]),cnt--;
    }
    cnt=0;
    int scores=0;
    for(int i=0;i<turns.size();i++)
    {
        string turn=turns[i];
        if(turn[0]=='S'||turn[0]=='G'||turn[0]=='F')
        {
            cnt++;
            if(!(cnt%3)) one=two=three=false;
            if(cnt==outs) break;
        }
        else if(turn[0]=='H')
        {
            if(one) scores+=1;
            if(two) scores+=1;
            if(three) scores+=1;
            scores+=1;
            one=two=three=false;
        }
        else
        {
            int num=turn[0]-'0';
            if(num==1)
            {
                if(three) scores+=1,three=false;
                if(two) three=true,two=false;
                if(one) two=true,one=false;
                one=true;
            }
            else if(num==2)
            {
                if(three) scores+=1,three=false;
                if(two) scores+=1,two=false;
                if(one) three=true,one=false;
                two=true;
            }
            else
            {
                if(three) scores+=1,three=false;
                if(two) scores+=1,two=false;
                if(one) scores+=1,one=false;
                three=true;
            }
        }
    }
    cout<<scores<<endl;
}