# 2021 第一屆 NHDK Ten Point Round 初學者程式設計交流會 - 題解

## 團體賽

### Problem A 同心協力

**Prepared by Colten**

簽到題，給大家祝福的題目ww

考點 : 輸出

:::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);
    
   cout << "Team Fighting!\n";
   
   return 0;
}

:::

### Problem B 幸運的一天

**Prepared by Colten**

考點 : 字串

利用 **字串** 去比對每一個索引的字元是否為質數，然後最後確定數量是否剛好等於 $2$

:::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);
	
	string a;
	
	cin >> a;
	
	int check = 0;
	
	for(int i=0;i<a.size();i++)
	{
		if( a[i] == '2' || a[i] == '3' || a[i] == '5' || a[i] == '7' )
		{
			check++;
		}
	}
	
	cout << ( check == 2 ? "Lucky Day!\n" : "Normal Day\n");
	
	return 0;
}

:::

### Problem C 數字多樣性

**Prepared by Colten**

考點 : 資料結構(STL-set)

利用 set 元素獨一無二(不會有重複的集合)的特性，我們可以將所有的數字都拉近一個集合裡面

最後在將 set 的 size 大小輸出，這就是最後數字種類的數目

:::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,i,k;
	
	cin >> n >> m;
	
	set <int> s;
	
	for(i=0;i<n;i++)
	{
		for(k=0;k<m;k++)
		{
			int input;
			
			cin >> input;
			
			s.insert(input);
		}
	}
	
	cout << s.size() << "\n";
	
	return 0;
}

:::

### Problem D 公平的數列

**Prepared by Colten**

考點 : 實作

一開始我們可以先取得數列第二項以及第一項之差做為公差值

接著在輸入的同時，檢查是否有任相鄰兩項的差不是公差值

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

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
int a[200005];
 
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int q,n,i,k;
	
	cin >> q;
	
	while(q--)
	{
		bool ans = true;
		
		cin >> n;
		
		int d;
		
		for(i=0;i<n;i++)
		{
			cin >> a[i];
			
			if( i == 1 )
			{
				d = a[i] - a[i-1];	
			}
			else if( i != 0 )
			{
				if( a[i] - a[i-1] != d ) ans = false;
			}	
		}
		
		if( ans == true ) cout << "Yes\n";
		
		else cout << "No\n";	
	}
	
	return 0;
}

:::

### Problem E 撈金魚

**Prepared by Colten**

考點 : 排序 & 貪婪

我們可以將金魚的重量以及網子承受重量先進行排序，最後兩邊都從最重的網子以及最重的金魚開始比較

當網子的承受重量不比金魚低時，就將答案加上金魚的重量

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

#include <bits/stdc++.h>

#define int long long

using namespace std;

int a[200005],k[200005];

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

:::

### Problem F 滑雪

**Prepared by Colten**

考點 : 排序 & 動態規劃

這題如果使用 DFS(深度優先搜尋) 來做的話應該可以拿到 29 分

不過仔細想想題目給的條件，我們會發現是一個有向無環圖(DAG)

由於只能從高的山到達低的山，因此我們先對高度做個排序，將高度由大排到小

我們將 $dp[i]$ 定義為到達第 $i$ 座山的最遠距離

接著，我們從最高的山開始，我們對被選定的山 $u$ 去找比被選定的山還要高且能到達 $u$ 的山中，最大的 $dp[k]$

最後，$dp[u] = max( dp[k] ) + 1$

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

#include <bits/stdc++.h>

#define int long long

using namespace std;

vector <int> mp[200005];

int n,m,w[200005];

vector <int> dp(200005,-1e9);

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	cin >> n >> m;
	
	vector <pair<int,int>> w(n);
	
	for(int i=0;i<n;i++)
	{
		cin >> w[i].first;
		
		w[i].second = i;
	}
	
	for(int i=0;i<m;i++)
	{
		int a,b;
		
		cin >> a >> b;
		
		a--;
		
		b--;
		
		if( w[a] > w[b] )
		{
			mp[b].push_back(a);
		}
		else if( w[b] > w[a] )
		{
			mp[a].push_back(b);
		}
	}
	
	sort(w.begin(),w.end(),greater<pair<int,int>>());
	
	dp[0] = 0;
	
	for( pair<int,int> i : w )
	{
		int u = i.second;
		
		int cur = -1e9;
		
		if( u == 0 ) continue;
		
		for( int k : mp[u] )
		{
			cur = max(cur,dp[k]);
		}
		
		if( cur != -1e9 )
		{
			dp[u] = cur + 1;
		}
	}
	
	if( dp[n-1] == -1e9 ) cout << -1 << "\n";
	
	else cout << dp[n-1] << "\n";
	
	return 0;
}

:::

### Problem G 對決

**Prepared by Fysty**

為了方便我們稱雷姆是先手，翔子是後手。

首先考慮沒有$k$的情況，透過觀察會發現後手只會在$n$是$m+1$的倍數時才會贏，用遞迴關係和數學歸納法可以輕鬆得證，就不多說。(必勝策略大概就是一個人移動$x$格，另一個人就移動$m+1-x$格)

加上$x-k$這個操作感覺會差很多，但實際上不會，如果$k$不是$m+1$的倍數，那麼其實跟以上的必勝策略相同，因為目標都是每兩個回合都總共移動$m+1$的倍數個格子，所以答案跟沒有$k$一樣。

如果$k$是$m+1$的倍數，那麼當$n<k$時結論也一樣，但$n=k$時，先手會贏，
隨之而來的是$n=k+1$時，後手會贏，不過這時透過觀察發現$n=k+2,k+3,...,2k+2$的結論亦同，這時再使用數學歸納法可以得知，$n=t(k+1)+i$的結論跟$n=i$的結論相同，所以需要做的就些簡單整除關係判斷就好了。

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m,k;
        cin>>n>>m>>k;
        if(k<=m||k%(m+1))
        {
            if(n%(m+1)==0) cout<<"Shoko\n";
            else cout<<"Rem\n";
        }
        else
        {
            n%=(k+1);
            if(n==k||n%(m+1)) cout<<"Rem\n";
            else cout<<"Shoko\n";
        }
    }
}

:::

## 個人賽

### Problem A Hello 2021 Ten Point Round!

**Prepared by Colten**

考點 : 輸出

送上祝福的題目ww

:::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);
	
	cout << "Hello 2021 Ten Point Round in Tainan!\n";
	
	return 0;
}

:::

### Problem B 獎勵查詢

**Prepared by Colten**

考點 : 條件判斷

照著題目列舉每一種狀況或紀錄輸入的分數可以得到什麼獎勵皆可

:::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;
	
	bool a,b,c,d;
	
	a = b = c = d = 0;
	
	if( n >= 60 ) a = 1;
	
	if( n >= 70 ) b = 1;
	
	if( n >= 80 ) c = 1;
	
	if( n >= 90 ) d = 1;
	
	cout << "Drink ";
	
	if( d == 1 ) cout << "Yes\n";
	
	else cout << "No\n";
	
	cout << "Cookie ";
	
	if( c == 1 ) cout << "Yes\n";
	
	else cout << "No\n";
	
	cout << "Stationery ";
	
	if( b == 1 ) cout << "Yes\n";
	
	else cout << "No\n";
	
	cout << "Water ";
	
	if( a == 1 ) cout << "Yes\n";
	
	else cout << "No\n";
	
	return 0;
}

:::

### Problem C 連續加分

**Prepared by Colten**

考點 : 實作

在輸入的時候一併去紀錄目前連續到多少，並對目前記錄的數跟目前最大的連續數去做比較，取最大值並更新

:::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,ans = 0,now = 0;
	
	cin >> n;
	
	for(i=0;i<n;i++)
	{
		int input;
		
		cin >> input;
		
		if( input > 0 )
		{
			now++;
			
			ans = max(ans,now);
		}
		else
		{
			now = 0;
		}
	}
	
	cout << ans << "\n";
	
	return 0;
}

:::

### Problem D 琳瑯滿目

**Prepared by Colten**

考點 : 二分搜尋

將書籍的編號排序後，對每次查詢的數字取 upper_bound 以及 lower_bound，並將兩數相減即為所求

:::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;
	
	vector <int> v;
	
	cin >> n;
	
	for(i=0;i<n;i++)
	{
		int input;
		
		cin >> input;
		
		v.emplace_back(input);
	}
	
	sort(v.begin(),v.end());
	
	int q;
	
	cin >> q;
	
	while(q--)
	{
		int input;
		
		cin >> input;
		
		auto i1 = upper_bound(v.begin(),v.end(),input);
		
		auto i2 = lower_bound(v.begin(),v.end(),input);
		
		cout << i1 - i2 << "\n";
	}
	
	return 0;
}

:::

### Problem E 風原特色圓環 Traffic Circle III

**Prepared by Colten**

**改編自交大 2020 CPTC 程式競賽 pB**

考點 : 排序 & 貪婪

一開始我們先紀錄每一個圓環連接了幾條道路

然後我們可以知道，如果我們想要使架設路燈的金額最便宜

我們會使 **連接最多條道路的圓環，架設最便宜的路燈**

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

#include <bits/stdc++.h>

#define int long long

using namespace std;

int light[100005],circle[100005];

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int q,n,i,k;
	
	cin >> n;
	
	for(i=0;i<n;i++)
	{
		cin >> light[i];
	}
	
	cin >> q;
	
	while(q--)
	{
		int x,y;
		
		cin >> x >> y;
		
		circle[x-1]++;
		
		circle[y-1]++;
	}
	
	sort(light,light+n);
	
	sort(circle,circle+n);
	
	int ans = 0;
	
	for(i=0;i<n;i++)
	{
		ans += circle[n-i-1] * light[i];
	}
	
	cout << ans << "\n";
	
	return 0;
}

:::

### Problem F MEX it!

**Prepared by Fysty**

把所有重複的整數刪掉，假設刪掉了$a$個。

假設最後的飽和的陣列中最大的整數是$M$，則$M$一定在最一開始的陣列中，否則我可以省略掉一次MEX使答案變更小，故存在$i$使得原本的陣列中(已經刪掉所有重複的元素)，前$i$個都在最後的陣列中且其他通通都被刪掉，所以我們可以用滾動的方式跑過$i=0,1,...,n$，找出刪掉的最小數量$b$。

答案即為$a+b$。

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
set<ll> s;
int main()
{
    MottoHayaku
    ll n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        ll a;
        cin>>a;
        s.insert(a);
    }
    ll tmp=n-s.size();
    ll ans=s.size(),cur=0;
    while(!s.empty())
    {
        ll a=*s.begin();
        s.erase(s.begin());
        cur++;
        ans=min(ans,a+1-cur+s.size());
    }
    cout<<ans+tmp;
}

:::

### Problem G 卡牌遊戲

**Prepared by Colten**

考點 : 資料結構(STL-priority_queue)

這題的操作其實是在暗中提示使用**優先佇列**來做

我們將抽排以及一開始擁有的牌都使用 push 加進優先佇列之中

由於優先佇列中，預設最上層的元素會是最大值，因此對於出牌以及丟牌這兩個操作

我們可以使用 pop 來完成，接著就是照著題目的規則實作的部分了

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

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

priority_queue <int> a;

priority_queue <int> b;

void p1()
{
	for(int i=0;i<3;i++)
	{
		int input;
		
		cin >> input;
		
		a.push(input);
	}
}
void p2()
{
	for(int i=0;i<3;i++)
	{
		int input;
		
		cin >> input;
		
		b.push(input);
	}	
}
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int t,n;
	
	cin >> t >> n;
	
	for(int i=0;i<t;i++)
	{
		int input;
		
		cin >> input;
		
		a.push(input);
	}
	for(int i=0;i<t;i++)
	{
		int input;
		
		cin >> input;
		
		b.push(input);
	}
	
	int ans1 = 0,ans2 = 0;
	
	while(n--)
	{
		int x = a.top();
		
		int y = b.top();
		
		a.pop();
		
		b.pop();
		
		if( x > y )
		{
			ans1 += 5;
			
			ans2 += 3;
			
			p1();
			
			p2();
			
			a.pop();
			
			a.pop();
			
			b.pop();
		}
		else if( y > x )
		{
			ans1 += 3;
			
			ans2 += 5;
			
			p1();
			
			p2();
			
			a.pop();
			
			b.pop();
			
			b.pop();
		}
		else
		{
			ans1 += 3;
			
			ans2 += 3;
			
			p1();
			
			p2();
		}	
	}
	
	cout << ans1 << " " << ans2 << "\n";
	
	return 0;
}

:::

### Problem H 插隊

**Prepared by Colten**

考點 : 陣列

我們可以開兩個陣列去記錄目前編號 $i$ 的前面是誰，以及後面是誰

接著插隊進行的時候去對插隊者前面的人以及後面的人，還有被插隊者前面的人以及後面的人

以及插隊者跟被插隊者，對這幾個人紀錄的陣列進行更新

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

#include <bits/stdc++.h>

#define int long long

using namespace std;

int f[200005],b[200005];

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n,i,k;
	
	cin >> n;
	
	for(i=1;i<=n;i++)
	{
		f[i] = i - 1;
		
		b[i] = i + 1; 
	}
	
	int q;
	
	cin >> q;
	
	while(q--)
	{
		int x,y;
		
		cin >> y >> x;
		
		f[b[x]] = f[x];
		
		b[f[x]] = b[x];
		
		f[x] = f[y];
		
		b[f[y]] = x;
		
		f[y] = x;
		
		b[x] = y;
	}
	
	int start;
	
	for(i=1;i<=n;i++)
	{
		if( f[i] == 0 )
		{
			start = i;
			
			break;
		}
	}
	
	int now = 0,last = start;
	
	while( now != n )
	{
		if( now == 0 )
		{
			cout << start << " ";
		}
		else
		{
			cout << b[last] << " ";
			
			last = b[last];
		}
		
		now++;
	}
	
	return 0;
}

:::

### Problem I 密碼

**Prepared by Fysty**

令$A=AND(p),B=XOR(p),C=OR(p)$
我們分開討論$n$個數的第$i$位元有$cnt_i$種組合後，把$cnt_i$全部乘起來就好了。

如果$A$的第$i$位元是$1$或$C$的第$i$位元是$0$，那顯然前者只有全$1$，後者只有全$0$才能滿足條件，故$cnt_i=1$。
不然的話，先只考慮$B$的第$i$個位元$b$會發現若$b=0$則總要有偶數個$1$，若$b=1$則總要有奇數個$1$，此時都是$cnt_i=2^{n-1}$，然後考慮一些特殊情況：
若$b=0$且$C$的第$i$位元是$1$，則會發現全為$0$不滿足條件所以多算，故$cnt_i$要減一。
若$b=0,n$為偶數且$A$的第$i$位元是$0$，則會發現全為$1$不滿足條件所以多算，故$cnt_i$要減一。
若$b=1,n$為奇數且$A$的第$i$位元是$0$，則會發現全為$1$滿足前者但違反後者，故$cnt_i$要減一。
乖乖地判掉以上情況後，就能算出真正的$cnt_i$了。

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
const int MOD=1e9+7;
ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll ans=fpow(a*a%m,b/2,m);
    return (b%2?ans*a%m:ans);
}
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        ll x=0,y=(1LL<<k)-1,z=0;
        for(int i=0;i<n;i++)
        {
            ll a;
            cin>>a;
            x^=a,y&=a,z|=a;
        }
        ll ans=1,m=fpow(2,n-1,MOD);
        for(int i=0;i<k;i++)
        {
            ll a=y&1,b=z&1,c=x&1;
            y>>=1,z>>=1,x>>=1;
            if(a||!b) continue;
            if(c) 
            {
                if(n&1) ans=ans*(m-1)%MOD;
                else ans=ans*m%MOD;
            }
            else 
            {
                if(n&1) ans=ans*(m-1)%MOD;
                else ans=ans*(m-2)%MOD;
            }
        }
        cout<<ans<<"\n";
    }
}

:::

### Problem J FST 的煩惱

**Prepared by Fysty**

題目就是大數的質因數分解，用常見的方式做是$O(\sqrt{n})$，這顯然會TLE，不過或許能撈到不少的分數。

整個題敘其實就是Pollard's rho的概念和原理，有興趣的人可以上網自己google。

這題比較需要注意的大概是各種實作細節，這裡就直接附上AC code給大家參考。

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
vector<ll> ans;
ll x[105];
ll mul(ll a,ll b,ll p)
{
    a%=p,b%=p;
    ll ret=0;
    while(b)
    {
        if(b&1)
        {
            ret+=a;
            ret%=p;
        }
        a=(a+a)%p;
        b>>=1;
    }
    return ret;
}
ll fpow(ll a,ll b,ll p)
{
    ll ans=1;
	while(b)
    {
		if(b%2)	ans=mul(ans,a,p);
		a=mul(a,a,p);
		b/=2;
	}
	return ans;
}
bool MR(ll n)
{
    if(n%2==0)
    {
        if(n==2) return 1;
        else return 0;
    }
    ll k=n-1,r=0,q=20;
    while(k%2==0) r++,k/=2;
    while(q--)
    {
        ll a=rand()%(n-2)+2;
		x[0]=fpow(a,k,n);
		for(int i=1;i<=r;i++)
		{
			x[i]=mul(x[i-1],x[i-1],n);
			if(x[i]==1&&x[i-1]!=1&&x[i-1]!=n-1) return 0;
		}
		if(x[r]!=1) return 0;
    }
    return 1;
}
ll rho(ll n,ll c)
{
    ll cur=1,k=2,x=rand()%(n-1)+1,y=x,p;
    while(1)
    {
        x=(mul(x,x,n)+c)%n;
        p=__gcd((x-y+n)%n,n);
        if(p!=1&&p!=n) return p;
        if(x==y) return n;
        cur++;
        if(cur==k) y=x,k*=2;
    }
}
void findans(ll n,ll c)
{
	if(n==1) return;
	if(MR(n))
    {
		ans.push_back(n);
		return;
	}
	ll p=n,k=c%n;
	while(p>=n) p=rho(p,c--);
	findans(p,k);
	findans(n/p,k);
}
int main()
{
    MottoHayaku
    ll n;
    cin>>n;
    while(n%2==0)
    {
        ans.push_back(2);
        n/=2;
    }
    findans(n,107);
    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());
    for(ll u:ans) cout<<u<<" ";
}

:::