# 🌟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;
}
```
Sign in with Wallet
Connect another wallet