---
# System prepended metadata

title: "\U0001F31FCPE一星題練習(下)"
tags: [c++, cpe 1*]

---

# 🌟CPE一星題練習(下)
題目表來源:https://yuihuang.com/cpe-level-1-49/
接續上篇:https://hackmd.io/@herbert1018/BkOGIOQcke

# 📦26~30題
## 26. d492. 10226 - Hardwood species
搞笑，測資硬要給你卡一個空格在那邊
```cpp=
#include<iostream>
#include<iomanip>
#include<map>

using namespace std;  
  
int main(){
	map<string, int> mp;
	int n;
	cin>>n;
	string str;
	getline(cin, str);
	getline(cin, str);
	while(n--){
		int sum=0;
		mp.clear();
		while(getline(cin, str)){
			if(str=="")break;
			mp[str]++;
			sum++;
		}
		for(auto x: mp){
			cout<<setprecision(4)<<fixed<<x.first<<" "<<(double)x.second/sum*100<<'\n';
		}
		cout<<'\n'; 
	}
    return 0; 
}
```
## 27. d387. 10235 – Simply Emirp
我最喜歡用bitset建表了，我是bitset玩家
```cpp=
#include<iostream>
#include<bitset>
using namespace std;  

int reverse(int x){
	int temp=0;
	while(x>0){
		temp+=x%10;
		temp*=10;
		x/=10;
	}
	return temp/10;
}
int main(){
	bitset<1000000> bs;
	bs.set(0);bs.set(1);
	for(int i=2; i<1001; i++){
		if(!bs[i]){
			for(int j=i*2; j<1000000; j+=i)bs.set(j);
		}
	}
	int N;
	while(cin>>N){
		cout<<N;
		if(bs[N])cout<<" is not prime.\n";
		else if(reverse(N)==N|| bs[reverse(N)])cout<<" is prime.\n";
		else cout<<" is emirp.\n";
	}
    return 0; 
}
```
## 28. e512. 10242 – Fourth Point!!
無情if機器人拖垮效能
```cpp=
#include<iostream>
#include<iomanip>
using namespace std;  

int main(){
	double a[8], d;
	int index=0;
	double x1, x2, x3, y1, y2, y3;
	while(cin>>d){
		a[index]=d;
		index=(index+1)%8;
		
		if(index==0){
			if(a[0]==a[4]&&a[1]==a[5]){
				x1=a[6], x2=a[0], x3=a[2];
				y1=a[7], y2=a[1], y3=a[3];
			}
			else if(a[0]==a[6]&&a[1]==a[7]){
				x1=a[4], x2=a[0], x3=a[2];
				y1=a[5], y2=a[1], y3=a[3];
			}
			else if(a[2]==a[4]&&a[3]==a[5]){
				x1=a[6], x2=a[2], x3=a[0];
				y1=a[7], y2=a[3], y3=a[1];
			}
			else{
				x1=a[4], x2=a[2], x3=a[0];
				y1=a[5], y2=a[3], y3=a[1];
			}
		    cout<<fixed<<setprecision(3)<<x1-x2+x3<<" "<<y1-y2+y3<<'\n';
		}
	}
    return 0; 
}
```
## 29. e507. 10252 – Common Permutation
no comment
```cpp=
#include<iostream>
#include<bitset>
#include<algorithm>
using namespace std;  

int main(){
	int cnta[26], cntb[26];
	string a, b;
	while(cin>>a>>b){
		for(int i=0; i<26; i++){
			cnta[i]=0; cntb[i]=0;
		}//也可以用fill
		for(char c: a)cnta[c-'a']++;
		for(char c: b)cntb[c-'a']++;
		for(int i=0; i<26; i++){
			int t=min(cnta[i], cntb[i]);
			while(t--)cout<<(char)('a'+i);
		}cout<<'\n';
	}
    return 0; 
}
```
## 30. f444: 10268 – 498-bis
wow sstream還可以這樣用，學到了
```cpp=
#include<iostream>
#include<cmath>
#include<sstream>
#include<vector>
using namespace std;  

int main(){
	int x, a, ans;
	string str;
	while(cin>>x){
		ans=0;
		vector<int> poly;
		getline(cin, str);//cin.ignore();
		getline(cin, str);
		stringstream ss(str);
		while(ss>>a){
			poly.push_back(a);
		}
		for(int i=poly.size()-2, n=1; i>=0; i--, n++){
			ans+=pow(x, n-1)*poly[i]*n;
		}
		cout<<ans<<'\n';
	}
    return 0; 
}
```

# 📦31~35題
## 31. e516. 10409 – Die Game
owo
```cpp=
#include<iostream>
using namespace std;  

int main(){
	int n=-1;
	string s;
	while(cin>>n && n!=0){
		int dir[3]={1, 2, 3};
		while(n--){
			cin>>s;
			if(s=="north"){
				swap(dir[0], dir[1]);
				dir[0]=7-dir[0];
			}
			else if(s=="south"){
				swap(dir[0], dir[1]);
				dir[1]=7-dir[1];
			}
			else if(s=="east"){
				swap(dir[0], dir[2]);
				dir[2]=7-dir[2];
			}
			else{
				swap(dir[0], dir[2]);
				dir[0]=7-dir[0];
			}
		}
		cout<<dir[0]<<'\n';
	}
    return 0; 
}
```
## 32. e531. 10415 – Eb Alto Saxophone Player
建表bro
```cpp=
#include<iostream>
#include<map>
#include<vector>
#include<bitset>
using namespace std;  

int main(){
	map<char, vector<bool>> mp;
	mp['c']={0, 1, 1, 1, 0, 0, 1, 1, 1, 1};
	mp['d']={0, 1, 1, 1, 0, 0, 1, 1, 1, 0};
	mp['e']={0, 1, 1, 1, 0, 0, 1, 1, 0, 0};
	mp['f']={0, 1, 1, 1, 0, 0, 1, 0, 0, 0};
	mp['g']={0, 1, 1, 1, 0, 0, 0, 0, 0, 0};
	mp['a']={0, 1, 1, 0, 0, 0, 0, 0, 0, 0};
	mp['b']={0, 1, 0, 0, 0, 0, 0, 0, 0, 0};
	mp['C']={0, 0, 1, 0, 0, 0, 0, 0, 0, 0};
	mp['D']={1, 1, 1, 1, 0, 0, 1, 1, 1, 0};
	mp['E']={1, 1, 1, 1, 0, 0, 1, 1, 0, 0};
	mp['F']={1, 1, 1, 1, 0, 0, 1, 0, 0, 0};
	mp['G']={1, 1, 1, 1, 0, 0, 0, 0, 0, 0};
	mp['A']={1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
	mp['B']={1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
	bitset<10> finger;
	string str;
	int t;
	cin>>t;
	getline(cin, str);
	while(t--){
		vector<int> time(10, 0);
		getline(cin, str);
		finger.reset();
		for(char c: str){
			vector<bool> hold=mp[c];
			for(int i=0; i<10; i++){
				if(hold[i]){
					if(!finger[i]){
						finger.set(i);
						time[i]++;
					}
				}
				else finger.reset(i);
			}
		}
		for(int i: time)cout<<i<<" ";
		cout<<'\n';
	}
    return 0; 
}
```
## 33. a743. 10420 – List of Conquests
c++玩家最喜歡用auto然後甚麼都不管了
```cpp=
#include<iostream>
#include<map>
using namespace std;  

int main(){
	int n;
	cin>>n;
	map<string, int> mp;
	string str;
	getline(cin, str);
	while(n--){
		cin>>str;
		mp[str]++;
		getline(cin, str);
	} 
	for(auto p: mp)cout<<p.first<<" "<<p.second<<'\n';
    return 0; 
}
```
## 34. i859. 10642 - Can You Solve It?
直接算出距離(0, 0)的位置在相減後絕對值。
溢位問題(用long long)
```cpp=
#include<iostream>
#include<cmath>
using namespace std;
long long decar(long long p[3]){
	long long ans=p[0]+((1+p[0])*p[0]/2)-(p[0]-p[1]);
	return ans;
}

int main(){
	int n;
	long long p1[3]={0}, p2[3]={0};
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>p1[1]>>p1[2]>>p2[1]>>p2[2];
		p1[0]=p1[1]+p1[2];
		p2[0]=p2[1]+p2[2];
		cout<<"Case "<<i<<": "<<abs(decar(p1)-decar(p2))<<'\n'; 
	}
	return 0;
}
```
## 35. c022. 10783 – Odd Sum
自己推一下公式
```cpp=
#include<iostream>
using namespace std;  

int main(){
	int n, a, b;
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>a>>b;
		int l=(a%2==1)?(a+1)/2:a/2;
		int u=(b%2==1)?(b-1)/2:b/2;
		cout<<"Case "<<i<<": "<<(b*b-a*a+a+b)/2-(u*u-l*l+l+u)<<'\n';
	}
    return 0; 
}
```
# 📦36~40題
## 36. c004. 10812 – Beat the Spread! 
(x+y)+(x-y)=2x
(x+y)-(x-y)=2y
```cpp=
#include<iostream>
using namespace std;  

int main(){
	int n, a, b;
	cin>>n;
	while(n--){
		cin>>a>>b;
		if((a+b)%2 || a<b)cout<<"impossible\n";
		else cout<<(a+b)/2<<" "<<(a-b)/2<<'\n';
	}
    return 0; 
}
```
## 37. e575. 10908 – Largest Squares
沒想到吧，我用三維的dp，空間換時間
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;  

int main(){
	int T, M, N, Q, r, c;
	cin>>T;
	while(T--){
		cin>>M>>N>>Q;
		cout<<M<<" "<<N<<" "<<Q<<'\n';
		vector<vector<char>> sq(M, vector<char>(N));
		for(int i=0; i<M; i++){
			for(int j=0; j<N; j++)cin>>sq[i][j];
		}
		vector<vector<vector<int>>> test(4, vector<vector<int>>(M, vector<int>(N, 1)));
		for(int i=0; i<M; i++){
			for(int j=1; j<N; j++)test[0][i][j]=(sq[i][j]==sq[i][j-1])?test[0][i][j-1]+1:1;
			for(int j=N-2; j>=0; j--)test[1][i][j]=(sq[i][j]==sq[i][j+1])?test[1][i][j+1]+1:1;
		}
		for(int j=0; j<N; j++){
			for(int i=1; i<M; i++)test[2][i][j]=(sq[i][j]==sq[i-1][j])?test[2][i-1][j]+1:1;
			for(int i=M-2; i>=0; i--)test[3][i][j]=(sq[i][j]==sq[i+1][j])?test[3][i+1][j]+1:1;
		}
		while(Q--){
			cin>>r>>c;
			int k=min(min(test[0][r][c], test[1][r][c]), min(test[2][r][c], test[3][r][c]));
			cout<<(2*k-1)<<'\n';
		}
	}
    return 0; 
}
```
## 38. d672. 10922 – 2 the 9s
基礎遞迴練習
```cpp=
#include<iostream>
#include<string>

using namespace std;  
int degree(string str, int de){
	int sum=0;
	for(int i=str.length()-1; i>=0; i--){
		sum+=str[i]-'0';
	}
	if(sum%9!=0)return 0;
	else if(sum!=9)return degree(to_string(sum), de+1);
	else return de;
}

int main(){
	string str;
	while(cin>>str){
		if(str=="0")return 0;
		cout<<str;
		int ans=degree(str, 1);
		if(ans!=0)cout<<" is a multiple of 9 and has 9-degree "<<ans<<".\n";
		else cout<<" is not a multiple of 9.\n";
	}
    return 0; 
}
```
## 39. d235. 10929 – You can say 11
喜歡用三元運算子
```cpp=
#include<iostream>
#include<string>
using namespace std;

int main(){
	string str="";
	while(cin>>str){
		if(str=="0")return 0;
		cout<<str;
		int ans=0;
		for(int i=str.length()-1; i>=0; i--){
			ans+=(i&1)?(str[i]-'0'):-(str[i]-'0');
		}
		if(ans%11!=0)cout<<" is not a multiple of 11.\n";
		else cout<<" is a multiple of 11.\n";
	}
    return 0; 
}
```
## 40. a132. 10931 – Parity
我也試了bs.test()或直接用一個bool維護的版本，但感覺差不了多少
```cpp=
#include<iostream>
#include<bitset>
using namespace std;

int main(){
	bitset<33> bs;
	int n;
	while(cin>>n){
		if(n==0)return 0;
		bs=n;
		string str=bs.to_string();
		cout<<"The parity of ";
		for(int i=str.find('1'); i<33; i++)cout<<str[i];
		cout<<" is "<<bs.count()<<" (mod 2).\n";
	}
    return 0; 
}
```

# 📦41~45題
## 41. UVA-11005 Cheapest Base
vjudge的測資在搞，必須要求格式嚴格相同，害我吃了兩次PE
```cpp=
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
	int n, test, num;
	cin>>n;
	for(int i=1; i<=n; i++){
		cout<<"Case "<<i<<":\n";
		vector<int> cost(37);
		for(int j=0; j<36; j++)cin>>cost[j];
		cin>>test;
		while(test--){
			cin>>num;
			cout<<"Cheapest base(s) for number "<<num<<":";
			vector<int> spend(37, 0);
			for(int k=2; k<=36; k++){
				int temp=num;
				while(temp>=k){
					spend[k]+=cost[temp%k];
					temp/=k;
				}spend[k]+=cost[temp];
			}
			int cheap=*min_element(spend.begin()+2, spend.end());
			for(int base=2; base<=36; base++)if(spend[base]==cheap)cout<<" "<<base;
			cout<<'\n';
		}
		if(i!=n)cout<<'\n';
	}
	return 0;
}
```
## 42. d123. 11063 – B2-Sequence
這題測資沒檢查必須嚴格遞增
```cpp=
#include<iostream>
#include<bitset>
using namespace std;

int main(){
	int N, i=1;
	bitset<20001> show, add;
	while(cin>>N){
		show.reset();
		add.reset();
		int p;
		bool flag=false;
		while(N--){
			cin>>p;
			show.set(p);
			if(((show<<p)&add).any())flag=true;
			add|=show<<p;
		}
		if(flag)cout<<"Case #"<<i++<<": It is not a B2-Sequence.\n\n";
		else cout<<"Case #"<<i++<<": It is a B2-Sequence.\n\n";
	}
	return 0;
}
```
## 43. d189. 11150 – Cola
這題題目應該要在加一句「每次喝都可以再借，但借多少就要還多少」
1. 多借1->剛好可以還
2. 多借2->只會給你一個瓶子導致不夠還
3. 借更多->更不夠還
```cpp=
#include<iostream>
#include<cmath>
using namespace std;

int main(){
	int N;
	while(cin>>N){
		cout<<floor(3*N/2)<<'\n';
	}
	return 0;
}
```
## 44. d750. 11321 – Sort! Sort!! and Sort!!!
自從學會lambda後，沒有問題解不出來的，~~寫程式就是開容器跟排序~~
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
	int N, M;
	while(cin>>N>>M){
		cout<<N<<" "<<M<<'\n';
		if(N==0&&M==0)return 0;
		vector<int> vc(N);
		for(int i=0; i<N; i++)cin>>vc[i];
		sort(vc.begin(), vc.end(), [&](int x, int y){
			int tx=x%2, ty=y%2;
			if((x%M==y%M)){
				if(tx!=ty){
					return (tx)?true:false;				
				}
				else if(tx==1&&ty==1){
					return x>y;
				}
				else{
					return x<y;	
				}
			}else return (x%M)<(y%M);
		});
		for(int i=0; i<N; i++)cout<<vc[i]<<'\n';
	}
	return 0;
}
```
## 45. c813. 11332 – Summing Digits
喜歡擠在一起，非常難讀
```cpp=
#include<iostream>
#include<functional>
using namespace std;

int main(){
	int n;
	function<int(int)> g=[&](int x){
		string str=to_string(x);
		int ans=0;
		for(int i=str.size()-1; i>=0; i--)ans+=(str[i]-'0');
		return (ans<10)?ans:g(ans);
	};
	while(cin>>n && n!=0){
		cout<<g(n)<<'\n';
	}
	return 0;
}
```
# 📦46~49題
## 46. e513. 11349 – Symmetric Matrix
被搞兩次，負數跟long long
```cpp=
#include<iostream>
#include<vector>
using namespace std;

int main(){
	int T, N;
	char c;
	cin>>T;
	for(int k=1; k<=T; k++){
		bool flag=false;
		cin>>c>>c>>N;
		vector<vector<long long>> M(N, vector<long long>(N));
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++)cin>>M[i][j];
		}
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				if(M[i][j]!=M[N-i-1][N-j-1]||M[i][j]<0){
					flag=true;
				}
			}
		}
		if(flag)cout<<"Test #"<<k<<": Non-symmetric.\n";
		else cout<<"Test #"<<k<<": Symmetric.\n";
	}
	return 0;
}
```
## 47. d255. 11417 – GCD
想知道125251哪來的
可以去寫看看leetcode這題
1128. Number of Equivalent Domino Pairs
```cpp=
#include<iostream>
using namespace std;

int gcd(int x, int y){
	while((x%=y)&&(y%=x));
	return x+y;
}
int main(){
	int n;
	uint16_t map[125251]={0};
	for(int i=1; i<500; i++){
		for(int j=i+1; j<=500; j++){
			map[(j*(j-1)/2+i-1)]=gcd(j, i);
		}
	}
	while(cin>>n && n!=0){
		int ans=0;
		for(int i=1; i<n; i++){
			for(int j=i+1; j<=n; j++){
				ans+=map[(j*(j-1)/2+i-1)];
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}
```

## 48. d186. 11461 – Square Numbers
向下取整還有向上取整
```cpp=
#include<iostream>
#include<cmath>
using namespace std;

int main(){
	int a, b;
	while(cin>>a>>b&&(a!=0&&b!=0)){
		cout<<floor(sqrt(b))-ceil(sqrt(a))+1<<'\n';
	}
	return 0;
}
```
## 49. f709. 12019 – Doom’s Day Algorithm
1月1號是Saturday
```cpp=
#include<iostream>
using namespace std;

int main(){
				//1   2   3    4   5   6    7    8     9   10   11   12
	int month[12]={0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}, T, M, D;
	string day[7]={"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
	cin>>T;
	while(T--){
		cin>>M>>D;
		cout<<day[(month[M-1]+D+4)%7]<<'\n';
	}
	return 0;
}
```
# 📜後記
感覺zerojudge測資跟題目敘述很多都不完整，比較像是考通靈，
而且題目難度蠻簡單就是有些很浪費時間，不過就是考基礎I/O所以還可以接受。
相比之下正式cpe就是在考英文+讀題目，外加其他題目稍微難那麼億點🤏🤏

這邊放上來提供參考交流，要直接抄我也管不著，反正就是做一個紀錄🤯

~~~
舉一些後面4~7題常出現的題目類型dp、bfs、dfs、subset、圖論、(外加一坨沒聽過的演算法)...

✨知識點: vector、sort(lambda自訂排序)、map、bitset、
         sstream、iomanip(setw、setpercition)、fixed、
         getline、字串處理(find等)...

✨操作手法: 建表(質數、prefix)、輾轉相除、two pointer、二分搜、sliding window、
            快速冪(可搭配狀態轉移矩陣)、...


基本上靠這些東西就可以5~6題了，阿7題看運氣，
考cpe就像在大鍋炒，把input翻過來炒過去，然後端出一坨給judge
~~~
