# 112年度學科能力競賽竹北高中校內初選題解
###### by ocean
------------------------------------
[題目](https://drive.google.com/file/d/1P4hZYuNl4UgONtiu3R-hFMxe1ZXCuGgP/view?usp=sharing)
## 第一題
排序後，隔一個分組
:::spoiler code

#include<bits/stdc++.h>
#define int long long
using namespace std;

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int num[10];
    int a = 0, b = 0;
    for(int i=0;i<10;i++) cin>>num[i];
    sort(num, num+10);
    for(int i=0;i<10;i++){
        if(i % 2) b += num[i];
        else a += num[i];
    }
    cout<<b<<" "<<a<<"\n";

    return 0;
}

:::
## 第二題
因為本次比賽並無時間限制，所以硬爆是可行的:)
~~對 我硬爆我驕傲~~
但我可以提供一些想法
可以發現是外圈往內數的，並且每次皆為左上開始，可以依據這個規律寫出答案
:::spoiler 硬爆code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n, i, j;cin>>n>>i>>j;
    int num[n+1][n+1] = {};
    int op = 1;
    int x=1, y=1, k = 2;
    num[1][1] = 1;
    // cout<<(n/2 + (n % 2))<<" "<<(n / 2 + 1)<<"\n";
    while(y != (n/2 + (n % 2)) or x != (n / 2 + 1)){
        if(op == 1){
            if(y+1 <= n and num[x][y+1] == 0){
                y++;
                num[x][y] = k++;
            }else op++;
        }else if(op == 2){
            if(x+1 <= n and num[x+1][y] == 0){
                x++;
                num[x][y] = k++;
            }else op++;
        }else if(op == 3){
            if(y-1 > 0 and num[x][y-1] == 0){
                y--;
                num[x][y] = k++;
            }else op++;
        }else if(op == 4){
            if(x-1 > 0 and num[x-1][y] == 0){
                x--;
                num[x][y] = k++;
            }else op=1;
        }
                // cout<<x<<" "<<y<<"\n";
    }
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<num[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    cout<<num[i][j]<<"\n";

    return 0;
}

:::
## 第三題
利用while(cin>>)迴圈或者getline(cin, )簡單模擬
:::info
分數加法公式
a/b + c/d = (a\*d + b\*c)/b\*d
:::
:::spoiler code

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;

pair<int, int> a;
string s;
char op;

int32_t main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);

    cin>>s;
    int i=0;
    for( ;i<s.size() and isdigit(s[i]);i++){
        a.f *= 10;
        a.f += s[i] - '0';
    }
    i += 1;
    for( ;i<s.size() and isdigit(s[i]);i++){
        a.s *= 10;
        a.s += s[i] - '0';
    }
    // cout<<a.f<<" "<<a.s<<"\n";
    while(cin>>op){
        cin>>s;
        pair<int,int> b;
        int i=0;
        for( ;i<s.size() and isdigit(s[i]);i++){
            b.f *= 10;
            b.f += s[i] - '0';
        }
        i += 1;
        for( ;i<s.size() and isdigit(s[i]);i++){
            b.s *= 10;
            b.s += s[i] - '0';
        }
        // cout<<a.f<<" "<<a.s<<" "<<b.f<<" "<<b.s<<"\n";
        if(op == '+'){
            a.f = a.f*b.s + a.s*b.f;
            a.s = a.s * b.s;
        }else if(op == '-'){
            a.f = a.f*b.s - a.s*b.f;
            a.s = a.s * b.s;
        }
        int p = __gcd(a.f, a.s);
        a.f /= p;
        a.s /= p;
        if(a.s < 0){
            a.s *= -1;
            a.f *= -1;
        }

    }
    cout<<a.f<<"/"<<a.s<<"\n";

    return 0;
}

:::
## 第四題
dp經典題，也可以說是費氏數列加強版
dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
:::spoiler code

#include<bits/stdc++.h>
#define int long long
using namespace std;

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;cin>>n;
    int dp[n+1] = {};
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for(int i=3;i<=n;i++) dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    cout<<dp[n]<<"\n";

    return 0;
}

:::
## 第五題
題目中說道
很明顯就算有限時間硬爆也是一個可行解
利用next_permutation排出所有運算符號的運算順序
最好的方法是利用struct實作
~~但因為我懶，所以使用set實作~~
:::spoiler code

#include<bits/stdc++.h>
#define int long long
using namespace std;

string s;
int ans = -1e9;
char op[50];
int ord[50];
vector<int> num(51);

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    for(int i=0;i<50;i++) ord[i] = i;
    cin>>s;
    int i=0;
    for( ;i<s.size() and isdigit(s[i]);i++){
        num[0] *= 10;
        num[0] += s[i] - '0';
    }
    int a = 1, b = 0;
    for( ;i<s.size();i++){
        if(isdigit(s[i])){
            for( ;i<s.size() and isdigit(s[i]);i++){
                num[a] *= 10;
                num[a] += s[i] - '0';
            }
                        a++;
            i--;
        }else op[b++] = s[i];
    }
        // cout<<a<<" "<<b<<"\n";
        // for(int i=0;i<a;i++) cout<<num[i]<<" ";
        // cout<<"\n";
        // for(int i=0;i<b;i++) cout<<op[i]<<" ";
        // cout<<"\n";
    do{
        // for(int i=0;i<50;i++) cout<<ord[i];
        // cout<<"\n";
        set<int> st;
        vector<int> tmp = num;
        for(int i=0;i<=b;i++) st.insert(i);
        for(int i=0;i<b;i++){
            auto it = st.lower_bound(ord[i]);
            if(op[*it] == '-') tmp[(*next(it))] = tmp[(*it)] - tmp[(*next(it))];
            else if(op[*it] == '+') tmp[(*next(it))] = tmp[(*it)] + tmp[(*next(it))];
            else if(op[*it] == '*') tmp[(*next(it))] = tmp[(*it)] * tmp[(*next(it))];
            st.erase(ord[i]);
                        // for(int i:st) cout<<tmp[i]<<" ";
                        // cout<<"\n";
        }
               
        ans = max(tmp[b], ans);
    }while(next_permutation(ord, ord+b));

    cout<<ans<<"\n";

    return 0;
}

:::