# 2020 11 月 Ten Point Round #3 題解

## Div.2

### pA 能量合成

**Prepared By Colten**

考點 : 基本輸入輸出

備註 : 簽到題 (?

題目會給一個正整數 $c$ 希望你找到兩個正整數 $a,b$ 符合 $a+b=c$

注意的地方 : 題目有給你 $a,b$ 的範圍為 $(1\le a,b \le c )$

所以答案的其中一種為 $a=1 , b = c - 1$，如此一來 $1 + c - 1 = c$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int c;
	
	cin >> c;
	
	cout << 1 << " " << c - 1 << "\n";
	
	return 0;
}

:::

### pB 與數學老師的蘋果約定

**Prepared By Colten**

考點 : 簡易數論

題目希望你能在兩個區間內找到有幾個正整數的平方的個位數為 $2$

不過當你 $0 - 9$ 之間會發現，沒有一個數相乘的個位數是 $2$

故本題無論輸入如何，答案都為 $0$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int a,b;
	
	cin >> a >> b;
	
	cout << 0 << "\n";
	
	return 0;
}

:::

### pC 風原飲料販賣機

**Prepared By Colten**

考點 : 迴圈 Loop

簡單來說 : 題目想要求有幾個 $P <= M$

所以只要實作一下，答案就出來了

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n,m;
	
	cin >> m >> n;
	
	int ans = 0;
	
	while(n--)
	{
		int p;
		
		cin >> p;
		
		if( m >= p )
		{
			ans++;
		}
	}
	
	cout << ans << "\n";
	
	return 0;
}

:::

### pD 風原公倍數

**Prepared By Colten**

考點 : 條件判斷

題目要判斷 $N$ 是否符合以下條

1. 同時為 2 的倍數，也為 11 的倍數
2. 不可被 5 整除，也不可被 7 整除

只要會使用條件判斷這題就秒殺了 ouo

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n;
	
	cin >> n;
	
	if( n % 2 == 0 && n % 11 == 0 && n % 5 != 0 && n % 7 != 0 )
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}
	
	return 0;
}

:::

### pE 風原運動會 100 公尺查詢系統

**Prepared By Colten**

考點 : 排序 sorting & 陣列 Array

此題主要在考 sort 過後陣列 index 的觀念

在解此題須注意一個點是 **秒數會有浮點數**

把陣列 sort 過後，把查詢的名次對上 index 答案就出來了

**備註 : 此題因出現了小數點後為 0 且未省略的答案，經討論後已刪除爭議的測資並 rejudge 造成困擾非常抱歉**

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n,i,k;
	
	cin >> n;
	
	double a[15];
	
	for(i=0;i<n;i++)
	{
		cin >> a[i];
	}
	
	sort(a,a+n);
	
	int t;
	
	cin >> t;
	
	cout << a[t-1] << "\n";
	
	return 0;
}

:::

### pF 風原點名系統

**Prepared By Colten**

考點 : 陣列 - 標記

題目想要知道那些座號還沒回來，我們把一開始每個座號都標記成 0

輸入時，把回來的人的座號標記成 1，最後當座號還是 0 的人，就是還沒回來的人

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n,i,k;
	
	cin >> n;
	
	int a[40]={0};
	
	int back;
	
	while( cin >> back )
	{
		if( back == 0 )
		{
			break;
		}
		
		a[back-1] = 1;
	}
	
	for(i=0;i<n;i++)
	{
		if(a[i]==0)
		{
			cout << i + 1 << " ";
		}
	}
} 

:::

### pG 四則運算

**Prepared By joylintp**

簡單數學(？

因為 $1 \times 1 = 1$ 和 $1 \div 1 = 1$，且先乘除後加減，
因此所有的乘除法運算都可忽略，只須處理加減法即可

一種簡單的實作方式為，計算字串中 `+` 和 `-` 的數量差再加 1 即為答案。

本題輸入量較大，可能須使用各種語言的輸入優化才能通過。

:::spoiler 參考解法 (C++)

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

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;

        int cnt = 1;
        for (char &c : s)
            if (c == '+')
                cnt++;
            else if (c == '-')
                cnt--;
            else;

        cout << cnt << '\n';
    }

    return 0;
}

:::

### pH 獨一無二的完美數列

**Prepared By Colten**

考點 : STL-Set & 字串 String

題目想要知道是否有元素是重複的，我們可以利用 set 的特性

把每個元素拉近 set 裡後，去確認 set 的 size 是否跟 $N$ 相等

**特別注意 : 由於元素的大小最大到 $10^{100}$ 所以我們必須使用 字串 作解題**

**備註 : 此題被 Python 抓到一筆測資輸入方式錯誤，已修正並 rejudge 造成困擾，在此致歉**

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n;
	
	cin >> n;
	
	set <string> s;
	
	for(int i=0;i!=n;i++)
	{
		string input;
		
		cin >> input;
		
		s.insert(input);	
	}
	
	if( s.size() == n )
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}
	
	return 0;
}

:::

## Div.1

### pA

**同 Div.2 pG**

### pB

**同 Div.2 pH**

### pC 班上的數學成績

**Prepared By J.T.**

考點:排序、條件判斷

以下提供較為直觀的解法(不一定為最佳解)，首先當然是先讀入$N$,$K$，然後用陣列紀錄各子題的成績，根據題目的要求，在輸入的同時紀錄低於及格分數的最高分以及高於及格分數的最低分，讀完陣列後就是排序再輸出，最後就是判斷$re1$,$re2$是否有被更新，若有，則直接輸出$re1$,$re2$，若其中一者沒有更新，則依題意輸出 **"Hard Test!"** 或是 **"Easy Test!"** 。

這題應該沒什麼卡點，一開始大家都拿91分是因為我本來官解想偷懶，結果被Colten的測資捉到bug，在此向大家道歉，我不該偷懶QAQ

:::spoiler 參考解法 (C++)

#include<bits/stdc++.h> //finished
using namespace std;
int main(){
    int n,k;
    while(cin>>n>>k){
        int arr[n],re1=-1,re2=101; 
        //re1紀錄低於及格分數的最高分
        //re2紀錄高於及格分數的最低分
        for(int i=0;i<n;i++){
            cin>>arr[i];
            if(arr[i]<k&&arr[i]>re1){
                re1=arr[i];
            }else if(arr[i]>=k&&arr[i]<re2){
                re2=arr[i];
            }
        }
        sort(arr,arr+n);
        for(int i=0;i<n;i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
        if(re1>=0){
            if(re2<=100){
                cout<<re1<<endl<<re2<<endl;
            }else{
                cout<<re1<<endl<<"Hard Test!"<<endl;
            }
        }else{
            cout<<"Easy Test!"<<endl<<re2<<endl;
        }
    }
}

:::

### pD 淡稟與音樂遊戲

**Prepared By Joylintp**

**待公布**

### pE 風原特色圓環 Treffic Circle

**Prepared By Colten**

考點 : BFS 廣度優先搜尋

簡單來說:最一開始會從編號為 1 的圓環出發，希望找到距離 1 號圓環最近的風原特色圓環

本題注意事項 :
1. 1 號本身也可以是風原特色圓環
2. 有可能會有圓環跟本沒有連接道路
3. 有可能沒有符合的圓環，故什麼都不用輸出
4. 圓環的道路雙向皆可通行

我們從 1 號圓環開始去做 BFS 並在走到風原特色圓環時，將目前走的距離紀錄

最後取得最短的距離後，在去搜尋那些風原特色圓環距離 1 號圓環是這個距離

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

int n,i,k,m;

vector <int> check[30];

vector <int> circle;

int visited[30];

queue <int> u;

void bfs()
{
	u.push(1);
	
	visited[1] = 0;
	
	while( u.size() != 0 )
	{
		int t = u.front();
		
		u.pop();
		
		for(auto i : check[t])
		{
			if(visited[i] == -1)
			{
				visited[i] = visited[t] + 1;
				
				u.push(i);
			}
		}
	}
}
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	memset(check,0,sizeof check);
	
	memset(visited,-1,sizeof visited);
	
	cin >> n >> m;
	
	while(m--)
	{
		int a,b;
		
		cin >> a >> b;
		
		check[a].push_back(b);
		
		check[b].push_back(a);
	}
	
	int q;
	
	cin >> q;
	
	while(q--)
	{
		int input;
		
		cin >> input;
		
		circle.emplace_back(input);
	}
	
	bfs();
	
	int mn = 1e9;
	
	sort(circle.begin(),circle.end());
	
	for(auto i : circle)
	{
		if(visited[i] != -1)
		{
			mn = min(mn,visited[i]);
		}
	}
	
	for(auto i : circle)
	{
		if( visited[i] == mn && visited[i] != -1 )
		{
			cout << i << " ";
		}
	}
	
	return 0;
} 

:::

### pF 特別任務
**Prepared By amano_hina**

中等數論(?

這題的答案是先因數分解過後，只要有任何一個質數的冪次至少為2，就輸出(原數/此質數)和(原數-原數/此質數)

若沒有，則答案為無解

證明交給讀者自行思考囉:)

:::spoiler 參考解法 (C++)

#include<bits/stdc++.h>
using namespace std;
long long t,x,y,d;
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>t;
    while(t--)
    {
        cin>>x;
        d=0;
        y=sqrt(x);
        for(int i=2;i<=y;i++)
        {
            if(x%i==0)
            {
                if((x/i)%i==0)
                {
                    cout<<x/i<<" "<<x-x/i<<'\n';
                    d=1;
                    break;
                }
            }
        }
        if(d==0)
        {
            cout<<-1<<'\n';
        }
    }
}

:::

### pG 請公假萬歲
**Prepared By amano_hina**

簡單圖論(?

對題目給的三個點$x,y,z$分別運用dfs來記錄圖上各點與他們的距離，把算出來的三個距離加起來，最後在比較哪個點算出來的和最小就可以了

:::spoiler 參考解法 (C++)

#include<bits/stdc++.h>
using namespace std;
long long t,n,m,k,a[1000005],pos;
long long vis[1000005],x,y,z,d=0,minn;
long long dp[1000005],dp2[1000005],dp3[1000005];
vector<int> v[300005];
void dfs(int m)
{
    vis[m]=1;
    for(int i=0;i<a[m];i++)
    {
        if(vis[v[m][i]]==0)
        {
            dp[v[m][i]]=dp[m]+1;
            dfs(v[m][i]);
        }
    }
}
void dfs2(int m)
{
    vis[m]=1;
    for(int i=0;i<a[m];i++)
    {
        if(vis[v[m][i]]==0)
        {
            dp2[v[m][i]]=dp2[m]+1;
            dfs2(v[m][i]);
        }
    }
}
void dfs3(int m)
{
    vis[m]=1;
    for(int i=0;i<a[m];i++)
    {
        if(vis[v[m][i]]==0)
        {
            dp3[v[m][i]]=dp3[m]+1;
            dfs3(v[m][i]);
        }
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n-1;i++)
        {
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
            a[x]++;
            a[y]++;
 
        }
        cin>>x>>y>>z;
        dp[x]=0;
        dfs(x);
        for(int i=1;i<=n;i++)
        {
            vis[i]=0;
        }
        dp2[y]=0;
        dfs2(y);
        for(int i=1;i<=n;i++)
        {
            vis[i]=0;
        }
        dp3[z]=0;
        dfs3(z);
        for(int i=1;i<=n;i++)
        {
            vis[i]=0;
        }
        minn=LONG_LONG_MAX;
        for(int i=1;i<=n;i++)
        {
            if(dp[i]+dp2[i]+dp3[i]<minn)
            {
                minn=dp[i]+dp2[i]+dp3[i];
                pos=i;
            }
        }
        cout<<pos<<'\n';
        for(int i=0;i<=n;i++)
        {
            v[i].clear();
            a[i]=0;
        }
    }
}

:::

### pH 菜月昴與奧托
**Prepared By Fysty**

簡單幾何+進階數論(?

小故事：其實原題是給定長方形的四個頂點，輸出一個可以平分其面積的直線方程式，然後因為被說很簡單所以就反過來問了。

首先若$n$或$m$是奇數，則必存在頂點的中點不是整點，此時輸出None。

再來我們先換個角度想：能將一個長方形切成兩個面積相同的兩半的直線，要有什麼必須符合的條件呢？

答案是這條直線一定要通過長方形的中心，也就是對角線的中點。(此證明留給讀者)

所以$ax+by=1$要通過長方形的中點，而從題目的條件又近一步限制此中心為整點。

也就是說，只要能求出$ax+by=1$的一組整數解就好了。

若$\gcd(|a|,|b|)>1$的話必無解，輸出None。

否則我們可以用Extended Euclidean Algorithm就能求出一組解$(x_0,y_0)$。

而所求的兩點座標$(x_1,y_1),(x_2,y_2)$即為以下兩組答案之一(注意輸出的整數大小限制)：

$(x_0-\frac{n}{2},y_0-\frac{m}{2}),(x_0+\frac{n}{2},y_0+\frac{m}{2})$或$(x_0-\frac{m}{2},y_0-\frac{n}{2}),(x_0+\frac{m}{2},y_0+\frac{n}{2})$。

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define F first
#define S second
ll g;
pair<ll,ll> exgcd(ll a,ll b)
{
    if(b==0)
    {
        g=a;
        return {1,0};
    }
    pll p=exgcd(b,a%b);
    return {p.S,p.F-a/b*p.S};
}
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll m,n,a,b;
        cin>>m>>n>>a>>b;
        if(m%2||n%2) cout<<"None\n";
        else
        {
            ll A=abs(a),B=abs(b);
            pll p=exgcd(A,B);
            if(g>1) cout<<"None\n";
            else
            {
                cout<<"Found\n";
                ll da=B/g,db=A/g;
                if(a<0) p.F=-p.F;
                if(b<0) p.S=-p.S;
                cout<<p.F-m/2<<" "<<p.S-n/2<<" "<<p.F+m/2<<" "<<p.S+n/2<<"\n";
            }
        }
    }
}

:::