# **竹北軟研社社內競賽解答(C++)**
##### by coldspeed
---

[題目](https://zerojudge.tw/ShowContest?contestid=15438)

## 第一題:

照做
C++ 解

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

int main() {
    int n, m, a;
    cin >> n >> m;
    
    int ans=0;
    for(int i=0; i<n; i++){
        cin >> a;
        if(a>=m){
            ans+=1;
        }
    }
    
    cout << ans << "\n";
}

## 第二題:
把基數，偶數先分開 排完序後再印出

C++ 解

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

int main(){
    int n, a;
    cin >>n;
    vector<int> odd, even;
    
    for(int i=0; i<n; i++){
        cin >> a;
        if(a%2){
            odd.push_back(a);
        }
        else{
            even.push_back(a);
        }
    }
    
    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());
    for(int i=0; i<odd.size(); i++){
        cout << odd[i] << ' ';
    }
    for(int i=0; i<even.size(); i++){
        cout << even[i] << ' ';
    }
    
    cout << "\n";
}

## 第三題:
帶入點到線距離公式，記的要加絕對值

C++ 解

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

int main(){
    int x, y, a, b, c;
    cin >> x >> y;
    cin >> a >> b >> c;
    
    int ans=abs(a*x+b*y+c)/sqrt(a*a+b*b);
    
    cout << ans << "\n";
    
}

## 第四題:

先計算所有數加起來的數**total**
再計算無條件捨去的 **average=total/n** 和餘數**remainder=total%n**

因為要把+1-1的次數做的越少次越好，所以可以把多的remainder給較大的數字。
remainder會把變成的數字變成 average + 1

example:

total = 47 average = 5 remainder = 3

原本的數字 : 9 8 8 7 6 3 3 2 2
變成的數字 : 6 6 6 5 5 5 5 5 5

減去平均後 : 4 3 3 2 1 2 2 3 3 (絕對值)
減去值正負 : + + + + + - - - -

### **證明+1, -1 數量一樣:**

以下為了簡化
**pos** = 數字減average是正的總和 (絕對值)
**neg** = 數字減average是負的總和 (絕對值)
**pos_num** = 數字減average是正的個數
**neg_num** = 數字減average是負或零的個數

### 例如上面的例子：
pos = 13, pos_num = 5
neg = 10, neg_num = 4

### 可以先由數學得知:
**pos - neg = remainder**
一個pos_num數減(average+1) => pos-=1
一個neg_num數減(average+1) => neg+=1

**+1數** = **-1數** :
pos - **min(pos_num, remainder)** = neg + **max(0, remainder-pos_num)**

### 三種情況 :
**pos_num < remainder:**

* pos - pos_num = neg + remainder - pos_num
* pos - ~~pos_num~~ = neg + remainder - ~~pos_num~~
* pos = neg + remainder
* 可由上面第一式得知**成立**

**pos_num > remainder**:

* pos - remainder = neg + 0 ( reminder - pos_num < 0 )
* pos = neg + remainder
* 可由上面第一式得知**成立**

**pos_num ＝ remainder**:
* pos - remainder = neg + 0 ( reminder - pos_num ＝ 0 )
* pos = neg + remainder
* 可由上面第一式得知**成立**

而最後答案會是　pos - min(pos_num, remainder)

C++ 解

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

#define ll long long

int main(){
    ll n;
    cin >> n;
    ll arr[n], tot=0;
    for(int i=0; i<n; i++){
        cin >> arr[i];
        tot+=arr[i];
    }
    
    ll rem=tot%n, average=tot/n;
    
    ll ans, pos=0, pos_num=0;
    
    for(int i=0; i<n; i++){
        if(arr[i]-average>0){
            pos += arr[i]-average;
            pos_num++;
        }
    }
    
    ans=pos - min(pos_num, rem);
    
    cout << ans << "\n";
    
}

## 第五題:
原題目：[link]()

如果想要聽的話禮拜三可以問我，抱歉我後面兩題出的有點太難了。

C++ 解

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

#define ll long long

const ll maxn = 3e5+1;
ll a[maxn], p[maxn];
vector<ll> v[maxn];
ll dis[maxn];
ll vis[maxn];
ll n;
void dfs(ll x){
    vis[x]=1;
    for(int u:v[x]){
        dis[u]=dis[x]+1;
        dfs(u);
    }
}

int main(){
    
    cin >> n;
    for(ll i=1; i<=n; i++){
        cin >> a[i];
    }

    for(ll i=2; i<=n; i++){
        cin >> p[i];
    }

    for(ll i=2; i<=n; i++){
        v[p[i]].push_back(i);
    }

    
    dfs(1);
    ll ans[n+1]={};

    for(ll i=1; i<=n; i++){
        if(!vis[i]){continue;}
        ans[dis[i]]+=a[i];
    }

    ll tot=0;
    for(int i=n; i>=0; i--){
        if(ans[i]!=0){
            tot=ans[i];
            break;
        }
    }

    if(tot==0){
        cout << 0 << "\n";
    }
    else if(tot>0){
        cout << "+\n";
    }
    else{
        cout << "-\n";
    }

}