---
# System prepended metadata

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

---

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

刷了一點leetcode的easy跟medium後回來寫看看基礎一星題。
很多題都還可以寫得更好點，但要再研究，
阿程式架構的部分只是為了縮排才全塞一起。

# 📦1~5題
## 1. c039. 00100 – The 3n + 1 problem
直觀題，遞迴直接解，注意一下I跟J的大小關係。
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;

int count(int n){
	if(n==1)return 1;
	if(n%2==1)return count(n*3+1)+1;
	return count(n/2)+1;
}
int main(){
	int i, j;
	while(cin>>i>>j){
		int ans=0;
		cout<<i<<' '<<j<<' ';
		if(i>j)swap(i, j);
		for(int n=i; n<=j; n++){
			ans=max(ans, count(n));
		}
		cout<<ans<<'\n';
	}
	return 0;
}
```
## 2. c082. 00118 – Mutant Flatworld Expolrers
來浪費時間的，我還在試著讓它變更短，
目前是直接用mod來維護方向、二維陣列控制前進座標、輸入輸出時用map轉換。
```cpp=
#include<iostream>
using namespace std;
int land[52][52]={0};
int dir[4][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
char dirMp[4]={'N', 'E', 'S', 'W'};

int main(){
	char face;
	string move;
	int mx, my, nx, ny;//max, now;
	cin>>mx>>my;
	while(cin>>nx>>ny>>face>>move){
		int flag=0, temp=104+(face=='E')+(face=='S')*2+(face=='W')*3;//mod
		for(char c: move){
			if(c=='F'){
				int tx=nx+dir[temp%4][0], ty=ny+dir[temp%4][1];
				if(tx>mx || ty>my || tx<0 || ty<0){
					if(land[nx][ny])continue;
					flag=land[nx][ny]=1;
					break;
				}
				else{nx=tx; ny=ty;} 
			}
			temp+=(c=='L')*-1+(c=='R');
		}
        cout<<nx<<' '<<ny<<' '<<dirMp[temp%4]<<((flag)?" LOST":"")<<'\n';
	}
	return 0;
}
```
## 3. c007. 00272 – TeX Quotes
用cin.get來讀取所有字元(包括空白及換行)，用三元運算子跟and來精簡指令。
```cpp=
#include<iostream>
using namespace std;

int main(){
	int temp=0;
	char c;
	while(cin.get(c)){
		if(c=='"')cout<<((temp++&1)?"''":"``");
		else cout<<c;
	}
	return 0;
}
```
## 4. e561. 00299 – Train Swapping
用最原始的bubble sort
```cpp=
#include<iostream>
using namespace std;

int main(){
	int N, L=0;
	cin>>N;
	while(N--){
		cin>>L;
		int T[L], ans=0;
		for(int i=0; i<L; i++)cin>>T[i];
		
		for(int i=0; i<L; i++){
			for(int j=0; j<L-i-1; j++){
				if(T[j]>T[j+1]){
					swap(T[j], T[j+1]);
					ans++;
				}
			}
		}
		cout<<"Optimal train swapping takes "<<ans<<" swaps.\n";
	}
	return 0;
}
```
## 5. c045. 00490 – Rotating Sentences
這題zerojudge的測資有誤，下面解法送出後是對的，
只是很簡單的行列對調，不夠的地方補" "。
```cpp=
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int main(){
	int size=0;
	string str;
	vector<string> sen;
	while(getline(cin, str)){
		sen.push_back(str);
		size=max(size, (int)str.length()); 
	}
	for(int i=0; i<size; i++){
		for(int j=sen.size()-1; j>=0; j--){
			if(i>=sen[j].size())cout<<" ";
			else cout<<sen[j][i];
		}
		cout<<'\n';
	}
	return 0;
}
```

# 📦6~10題
## 6. a134. 00948 – Fibonaccimal Base
數字很小(最多只有38個)，直接建表。
```cpp=
#include<iostream>
using namespace std;

int main(){
	int fib[39]={1, 1};
	for(int i=2; i<39; i++)fib[i]=fib[i-1]+fib[i-2];
	
	int N, num; 
	cin>>N;
	while(N--){
		int flag=0;
		cin>>num;
		cout<<num<<" = ";
		for(int i=38; i>0; i--){
			if(num>=fib[i]){
				flag=1;
				cout<<1;
				num-=fib[i];
			}
			else if(flag)cout<<0;
		}
		cout<<" (fib)\n";
	}
	return 0;
}
```
## 7. c044. 10008 – What’s Cryptanalysis
預先配置一個pair<char, int>做的vector，然後用lambda自訂排序
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pci=pair<char, int>;

int main(){
	int n;
	string str;
	cin>>n;
	cin.ignore();
	vector<pci > mp;
	for(char c='A'; c<='Z'; c++)mp.push_back({c, 0});

	while(n--){
		getline(cin, str);
		for(char c:str){
			if(isalpha(c)){
				c=toupper(c);
				mp[c-'A'].second++;
			}
		}
	}
	sort(mp.begin(), mp.end(), [&mp](pci x, pci y){
        if(x.second!=y.second)return x.second>y.second;
        else return x.first<y.first;
	});
	for(pci in: mp){
		if(in.second==0)break;
		cout<<in.first<<" "<<in.second<<'\n';
	}
	return 0;
}
```
## 8. e545. 10019 – Funny Encryption Method
__builtin_popcount可以回傳此數的2進裡有幾個1，阿16進就拆開看就好，
也可以寫一個簡單的function算，但我不要。
```cpp=
#include<iostream>
using namespace std;

int main(){
	int T;
	cin >> T;
	while(T--){
		int N, b1=0, b2=0;
		cin >> N;
		b1=__builtin_popcount(N);
		while(N!=0){
			b2+=__builtin_popcount(N%10);
			N/=10;
		}
		cout<<b1<<' '<<b2<<'\n';
	}
	return 0;
}
```

## 9. c014. 10035 – Primary Arithmetic
注意最後面輸出的s
```cpp=
#include<iostream>
using namespace std;

int main(){
	int x, y;
	while(cin>>x>>y){
		if(x==0 && y==0)break;
		int ans=0, carry=0;
		while(x!=0 || y!=0){
			int a=x%10, b=y%10;
			carry=(a+b+carry)/10;
			if(carry)ans++;
			x/=10; y/=10;
		}
		if(ans)cout<<ans;
		else cout<<"No";
		if(ans>=2)cout<<" carry operations.\n";
		else cout<<" carry operation.\n";
		
	}
	return 0;
}
```


## 10. d097. 10038 – Jolly Jumpers
他是說要1到n-1每個都要有一個，不是說只要小於n就好。
```cpp=
#include<iostream>
#include<vector>
using namespace std;

int main(){
	int n;
	while(cin >> n){
		int a, b;
		vector<int> test(n, 0);
		cin>>a;
		for(int i=1; i<n; i++){
			cin>>b;
			test[abs(b-a)]++;
			a=b;
		}
		bool flag=0;
		for(int i=1; i<n; i++){
			if(test[i]!=1){
				flag=1;
				break;
			}
		}
		cout<<((flag)?"Not jolly":"Jolly")<<'\n';
	}
	return 0;
}
```

# 📦11~15題
## 11. a737. 10041 – Vito’s family
這題的問題是找中位數，而且沒有小數且偶數情況可以向下一數取整
所以就全用r/2。
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
	int n, r;
	cin>>n;
	while(n--){ 
		cin>>r;
		int h[r];
		for(int i=0; i<r; i++)cin>>h[i];
		sort(h, h+r);
		
		int ans=0;
		for(int i=0; i<r; i++)ans+=abs(h[i]-h[r/2]);
		cout<<ans<<'\n';
	}
	return 0;
}
```
## 12. e579. 10050 – Hartals
bitset硬幹法
```cpp=
#include<iostream>
#include<bitset>
using namespace std;
int main(){
	bitset<3652> day;
	int T;
	cin >> T;
	while(T--){
		day.reset();
		int N, P, num;
		cin >> N >> P;
		while(P--){
			cin >> num;
			for(int i=1; i<=N/num; i++)day.set(num*i);
		}
		for(int i=0; i<N/7; i++){
			day.reset(7*i+6);
			day.reset(7*i+7);
		}
		cout << day.count()<<'\n';
	}
	return 0;
}
```

## 13. a012. 10055 – Hashmat the Brave Warrior
來搞笑的大數，用abs處理前後問題就好。
不過更大的話就得改用python，它作弊根本不在乎大數
```cpp=
#include<iostream>
using namespace std;
int main(){
	long long a, b;
	while(cin>>a>>b){
		cout<<abs(b-a)<<'\n';
	}
	return 0;
}
```
## 14. e510. 10056 – What is the Probability? 
題目敘述很繞，反正就是無窮等比級數求和，第一次用到iomanip
裡面的fixed(對齊小數:0.01->0.0100)、setprecision(看過沒用過)
```cpp=
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main(){
	cin.tie(0); 
	int S;
	cin>>S;
	while(S--){
		int N, i;
		double p;
		cin>>N>>p>>i;
		if(p==0.0){
			cout<<"0.000\n";
			break;
		}
		cout<<fixed<<setprecision(4)
            <<pow(1.0-p, i-1)*p/(1.0-pow(1-p, N))<<'\n';
	}
	return 0;
}
```
## 15. e606. 10057 – A mid-summer nights dream
阿不是跟前面第11題一樣，但這題測資很大不排除可能是暴力解
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    while (cin >> n){
        int num[n];
        for(int i=0; i<n; i++)cin>>num[i];
        sort(num, num+n);
        int mid1=num[(n-1)/2], mid2=num[n/2], ans=0;
        for (int i=0; i<n; i++){
            if (num[i]==mid1 || num[i]==mid2)ans++;
        }
        cout<<mid1<<" "<<ans<<" "<<mid2-mid1+1<<"\n";
    }
    return 0;
}
```
# 📦16~20題
## 16. c012. 10062 – Tell me the frequencies! 
也是前面出現過的(第7題)，只是變記ascii，然後可能會有空白行(換用getline)
突然發現也可以直接用傳統陣列放。
```cpp=
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
using pii=pair<int, int>;
 
int main() {
    string str;
    while (getline(cin, str)){
    	pii mp[256];
    	for(int i=0; i<256; i++)mp[i]={i, 0}; 
        for(char i: str)mp[(int)i].second++;
		sort(mp, mp+256, [&mp](pii x, pii y){
			if(x.second!=y.second)return x.second<y.second;
			else return x.first>y.first;
		});
		for(pii i: mp){
			if(i.second==0)continue;
			cout<<i.first<<" "<<i.second<<'\n';
		}
		cout<<'\n';
    }
    return 0;
}
```
## 17. d226. 10071 – Back to High School Physics
啊?
```cpp=
#include<iostream>
using namespace std;
 
int main() {
    int v, t;
    while(cin >> v >> t){
    	cout<<2*v*t<<'\n';
	} 
    return 0;
}
```
## 18. UVA-10093 An Easy Problem!
zero judge版 n786. 10093 - An Easy Problem!
https://zerojudge.tw/ShowProblem?problemid=n786
OK解題就算了，題目還讓你看都看不懂
```cpp=
#include<iostream>
using namespace std;
 
int main() {
	string str;
	while(cin>>str){
		int temp=0, sum=0, i=1;
		for(char c: str){
			if(c>='0' && c<='9')temp=c-'0';
			else if(c>='A' && c<='Z')temp=c-'A'+10;
			else if(c>='a' && c<='z')temp=c-'a'+36;
			i=max(temp, i);
			sum+=temp;
		}
		for(; i<62; i++){
			if(sum%i==0){
				cout<<i+1<<'\n';
				break;
			}
		}
		if(i==62)cout<<"such number is impossible!\n";
	}
    return 0;
}
```
## 19. a741. 10101 – Bangla Numbers
不管，暴力遞迴解
```cpp=
#include<iostream>
#include<iomanip>
using namespace std;
void bangla(long long x){
	if(x>=10000000){
		bangla(x/10000000);
		cout<<" kuti";
		x%=10000000;
	}
	if(x>=100000){
		bangla(x/100000);
		cout<<" lakh";
		x%=100000;
	}
	if(x>=1000){
		bangla(x/1000);
		cout<<" hajar";
		x%=1000;
	}
	if(x>=100){
		bangla(x/100);
		cout<<" shata";
		x%=100;
	}
	if(x)cout<<" "<<x;
}
int main() {
	long long n, t=1;
	while(cin>>n){
		cout<<setw(3)<<t++<<".";
		if(n==0)cout<<0;
		else bangla(n);
		cout<<'\n';
	}
    return 0;
}
```
## 20. e555. 10170 – The Hotel with Infinite Rooms
算梯形面積，上底S是初始人數，下底Z是答案，然後不要超過面積D
(S+Z)x(Z-S+1)/2<=D -> ZxZ+Z<=2D+Sx(S-1)

阿你很閒還可以確認上下限後再寫一個二分搜，應該會快很多
```cpp=
#include<iostream>
using namespace std;
int main(){
	long long S, D;
    while(cin>>S>>D){
    	long long max=2*D+S*(S-1), Z=1; 
    	while(Z*Z+Z<max)Z++;
    	cout<<Z<<'\n';
	}
	return 0;
}
```
# 📦21~25題
## 21. e605. 10189 - Minesweeper
直接開n+2乘m+2的int陣列，省去判斷的麻煩直接用雙迴圈++。
```cpp=
#include<iostream>
using namespace std;
int main(){
	int F=1, n=0, m=0;
	while(cin>>n>>m){
		if(!(n||m))return 0;
		
		int map[n+2][m+2]={0};
		bool posion[n+2][m+2]={0};
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				char c;
				cin>>c;
				if(c=='*'){
					posion[i+1][j+1]++;
					for(int k=0; k<3; k++){
						for(int l=0; l<3; l++){
							map[k+i][l+j]++;
						}
					}
				}
			}
		}
		cout<<"Field #"<<F++<<":\n";
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				if(!posion[i][j])cout<<map[i][j];
				else cout<<'*';
			}
			cout<<'\n';
		}
	}
	return 0;
}
```
## 22. e566. 10190 - Divide, But Not Quite Conquer!
也可以直接用vector寫，但我寫過了想試試看用遞迴寫
```cpp=
#include<iostream>
using namespace std;
bool boring(int n, int &m){
	if(n==1)return false;
	if(n%m!=0)return true;
	return boring(n/m, m);
}
int main(){
	int n, m;
	while(cin>>n>>m){
		if(n==0||m==0||boring(n, m))cout<<"Boring!\n";
		else{
			while(n>0){
				cout<<n<<' ';
				n/=m;
			}
			cout<<'\n';
		}
	}
	return 0;
}
```
## 23. d306. 10193 - All You Need Is Love
先轉成int在找最大公因數(gcd)。有一說一，此輾轉相除寫法不適用0的情形
```cpp=
#include <iostream>
#include <string>
using namespace std;
 
int gcd(int x, int y){
    while ((x %= y) && (y %= x));
    return x + y;
}

int s2n(string &str){
	int n=0;
	for (int i = 0; i < str.size(); i++){
	    n *= 10;
	    n += str[i] - '0';
	}
	return n;
}
int main() {
    int N;
    string S1, S2;
    cin >> N;
    for (int Case = 1; Case <= N; Case++){
        cin >> S1 >> S2;
        int n1 = s2n(S1), n2 = s2n(S2);
        cout << "Pair #" << Case;
        if (gcd(n1, n2) > 1) cout << ": All you need is love!\n";
        else cout << ": Love is not all you need!\n";
    }
    return 0;
}
```
## 24. UVA-10221 Satellites
WTF，直接看題解的，根本不知道是三小
```cpp=
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
#define PI acos(-1)

int main() {
    double s, a, r=6440;
    string str;
    while(cin>>s>>a>>str){
    	if(str=="min")a/=60;
    	if(a>180)a=360-a;
    	double chord=(r+s)*sin(a*PI/360)*2;
    	double arc=2*PI*(r+s)*a/360;
    	cout<<fixed<<setprecision(6)<<arc<<" "<<chord<<'\n';
	}
    return 0;
}
```
## 25. e578. 10222 - Decode the Mad man
硬幹法
```cpp=
#include<iostream> 
#include<string>
using namespace std;  
  
int main(){
	string s="`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
	string str;
	while(getline(cin, str)){
		for(char c: str){
			if(c==' ')cout<<" ";
			else if(c=='`'|| c=='1'|| c=='q'|| c=='w'||
                               c=='a'|| c=='s'|| c=='z'|| c=='x')break;
			else{
				int it=s.find(c);
				cout<<s[it-2];
			}
		}cout<<'\n';
	} 
    return 0; 
}
```
