# CPE練習: 一顆星選集
###### tags: `ISU` `CPE`
:::info
資料來源
* [CPE環境與教材](https://cpe.cse.nsysu.edu.tw/environment.php#starList)
* [歷屆試題與參考程式](https://cpe.cse.nsysu.edu.tw/history.php)
學習資源
* [YUI HUANG 演算法學習筆記](https://yuihuang.com/)
* [一顆星共筆](http://bit.ly/cpework)
練習環境
* [Zerojudge](https://zerojudge.tw/)
* [ACM onlinejudge](https://onlinejudge.org/)
考題講解
* [2023.10.17 CPE](https://hackmd.io/@wcyang77/H1NcTsGGp)
:::
## 基本練習
### CPE給予資料的方式
:::success
1. 一次給一筆資料, Ex: ZJ a001, a002
2. 已經知道要讀幾個, Ex: ZJ a005, a058
3. 讀至特定資料為止, Ex: ZJ a147, d649
4. 讀至沒有資料為止, Ex: ZJ a004, a263
5. 混合型態, Ex:ZJ a148
:::
#### 1. 一次給一筆資料
Ex: [a001: 哈囉](https://zerojudge.tw/ShowProblem?problemid=a001)
```cpp=
// c++參考程式
#include <string>
#include <iostream>
using namespace std;
int main() {
string s;
cin>>s;
cout<<"hello, "<<s<<endl;
return 0;
}
```
```python=
# python參考程式
s = input()
print('hello,',s)
```
Ex: [a002: 簡易加法](https://zerojudge.tw/ShowProblem?problemid=a002)
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
int main() {
int a,b;
cin >> a >> b;
cout << a+b << endl;
return 0;
}
```
```python=
# python參考程式
# 輸入
a,b = input().split()
a,b = int(a), int(b)
# 處理
c =a+b
# 輸出
print(c)
```
#### 2. 已經知道要讀幾個
Ex: [a005: Eva 的回家作業](https://zerojudge.tw/ShowProblem?problemid=a005)
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
int main() {
int t,a,b,c,d,e;
cin>>t;
for(int i=0; i<t; i++) {
cin>>a>>b>>c>>d;
if(b-a==c-b && c-b==d-c)
e = d+(d-c);
else e = d*(d/c);
cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl;
}
return 0;
}
```
```python=
# python參考程式
t = int(input())
for i in range(t):
a,b,c,d = input().split()
a,b,c,d = int(a),int(b),int(c),int(d)
if b-a==c-b and c-b==d-c:
e = d+(d-c)
else:
e = d*(d//c)
print(a,b,c,d,e)
```
Ex:[ a058: MOD3](https://zerojudge.tw/ShowProblem?problemid=a058)
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
int main() {
int n,x,c[3]={0,0,0};
// 輸入
cin>>n;
// 處理
for(int i=0; i<n; i++) {
cin>>x;
c[x%3]++;
}
// 輸出
cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<endl;
return 0;
}
```
#### 3. 讀至特定資料為止
Ex: [a147: Print it all](https://zerojudge.tw/ShowProblem?problemid=a147)
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
int main() {
int a;
// 輸入
cin>>a;
// 處理 & 輸出
while(a!=0) {
for(int i=1; i<a; i++)
if(i%7!=0) cout<<i<<" ";
cout<<endl;
cin>>a;
}
return 0;
}
```
Ex: [d649: 數字三角形](https://zerojudge.tw/ShowProblem?problemid=d649)
```cpp=
// c++參考程式
#include<iostream>
using namespace std;
int main(){
int a;
int b;
cin >> a;
while(a != 0){
int x = 0;
b = a;
for(int i = 0; i < a; i++){
x = x + 1;
b = b - 1;
for(int j = 0; j < b; j++){
cout << "_";
}
for(int j = 0; j < x; j++){
cout << "+";
}
cout << endl;
}
cin >> a;
}
}
```
#### 4. 讀至沒有資料為止
Ex: [a004: 文文的求婚](https://zerojudge.tw/ShowProblem?problemid=a004)
* Note: 閏年判斷邏輯
```cpp=
// c++參考程式
#include<iostream>
using namespace std;
int main(){
int a;
while(cin>>a){
if(a%400==0 || (a%4==0 && a%100!=0))
cout << "閏年"<<endl;
else
cout << "平年"<<endl;
}
}
```
```python=
# python參考程式
while True:
try:
y = int(input())
if y%4==0 and y%100!=0 or y%400==0:
print('閏年')
else:
print('平年')
except:
break
```
```python=
import sys
for y in sys.stdin:
y = int(y)
if y%4==0 and y%100!=0 or y%400==0:
print('閏年')
else:
print('平年')
```
Ex: [a263: 日期差幾天](https://zerojudge.tw/ShowProblem?problemid=a263)
```cpp=
// c++參考程式
#include <iostream>
#include <string>
using namespace std;
int mm[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
//與公元元年元旦的差距
int dlen(int y,int m,int d) {
int len;
len = 365*(y-1)+mm[m-1]+d;
len+= (y-1)/400*97+(y-1)%400/4-(y-1)%400/100;
if((m>2) && (y%4==0 && y%100!=0 || y%400==0))
len++;
return len;
}
int main() {
int y1,m1,d1,y2,m2,d2,dd;
while(cin>>y1>>m1>>d1>>y2>>m2>>d2) {
dd = dlen(y2,m2,d2)-dlen(y1,m1,d1);
if(dd<0) dd=-dd;
cout<<dd<<endl;
}
return 0;
}
```
```python=
# python參考程式
days = 31,28,31,30,31,30,31,31,30,31,30,31
def countDays(y,m,d):
cd = 365*(y-1) + (y-1)//4 - (y-1)//100 + (y-1)//400
for i in range(m-1):
cd+= days[i]
if m>2:
if (y%4==0 and y%100!=0) or y%400==0:
cd+= 1
cd+= d
return cd
while True:
try:
y1,m1,d1 = input().split()
y1,m1,d1 = int(y1),int(m1),int(d1)
y2,m2,d2 = input().split()
y2,m2,d2 = int(y2),int(m2),int(d2)
print(abs(countDays(y1,m1,d1)-countDays(y2,m2,d2)))
except:
break
```
```python=
# python參考程式-使用現有模組
import sys
from datetime import date
for in1 in sys.stdin:
d1 = [int(x) for x in in1.split()]
d2 = [int(x) for x in input().split()]
d1 = date(d1[0],d1[1],d1[2])
d2 = date(d2[0],d2[1],d2[2])
print(abs((d2-d1).days))
```
#### 5. 混合型態
Ex: [a148: You Cannot Pass?!](https://zerojudge.tw/ShowProblem?problemid=a148)
```cpp=
// c++參考程式
#include<iostream>
using namespace std;
int main(){
int a;
int x;
float sum;
cin >> a;
while(cin){
for(int i=0; i<a; i++){
cin >> x;
sum = sum + x;
}
if(sum / a > 59)
cout << "no" << endl;
else
cout << "yes" << endl;
cin >> a;
sum = 0;
}
}
```
```python=
# python參考程式
import sys
for s in sys.stdin:
d = s.split()
n,sum = int(d[0]),0
for i in range(1,n+1):
sum+= int(d[i])
if(sum>59*n):
print('no')
else:
print('yes')
```
## 一些重要的函式庫(Library)
* 要能查詢如何使用： [Cpluspluse Reference](https://cplusplus.com/reference/)
* [Python 標準函式庫 (Standard Library)](https://docs.python.org/zh-tw/3/library/index.html)
* 重要功能
* string
* In C++: cstring, string
* C++ vector
* algorithm - sort
```cpp=
// c++參考程式
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp1(int a, int b) {
return a>b;
}
bool cmp2(int a, int b) { //奇在前偶在後、奇數大在前小在後、偶數小在前大在後
bool flag = true;
if(a%2<b%2) flag = false;
else if(a%2==b%2) {
if(a%2==1 && a<b) flag = false;
else if(a%2==0 && a>b) flag = false;
}
return flag;
}
int main() {
int a[] = {1,3,5,7,2,4,6,8};
int b[] = {1,3,5,7,2,4,6,8};
int c[] = {1,3,5,7,2,4,6,8};
for(int i=0; i<8; i++) cout<<a[i]<<" ";
cout<<endl;
// 由小到大
sort(a,a+8);
for(int i=0; i<8; i++) cout<<a[i]<<" ";
cout<<endl;
// 由大到小
sort(b,b+8,cmp1);
for(int i=0; i<8; i++) cout<<b[i]<<" ";
cout<<endl;
// 特定規則
sort(c,c+8,cmp2);
for(int i=0; i<8; i++) cout<<c[i]<<" ";
cout<<endl;
return 0;
}
```
## CPE樣題 (49題) - 每次出現一題
### 一、基本題型
:::success
1. Vito's family (CPE10406, UVA10041)
2. Hashmat the brave warrior (CPE10407, UVA10055)
3. Primary Arithmetic (CPE10404, UVA10035)
4. The 3n + 1 problem (CPE10400, UVA100)
5. You can say 11 (CPE10460, UVA10929)
6. Bangla Numbers (CPE10414, UVA10101)
7. List of Conquests (CPE21924, UVA10420)
:::
#### 1. Vito's family (CPE10406, UVA10041)
- **題目**
- [原始題目連結](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=982)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=a737)
- **題意**
- 有個人有很多親戚需要拜訪。想找一間離所有親戚家最近的房子，使得他拜訪所有親戚時，距離的總和是最小值。
（輸入測資後，求距離的最小值）
- **解法**
- 差異絕對值相加，最小值出現在排好數列的中位數時，用中位數帶入即可。
- 若資料個數為偶數，不需要取中間兩樹平均值，取中間任何一個數當基準計算即可。
- 可以使用 C++ vector 做動態陣列，提升撰寫效率。
- 可以使用 C++ algorithm 之 sort 排序，提升撰寫效率。
```cpp=
// c++參考程式
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n,s[500],r;
cin>>n;
for(int i=0; i<n; i++) {
cin>>r;
for(int j=0; j<r; j++) cin>>s[j];
sort(s,s+r);
int mid=s[r/2],sum = 0;
for(int j=0; j<r; j++) sum+=abs(s[j]-mid);
cout<<sum<<endl;
}
return 0;
}
```
```cpp=
// c++參考程式
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n,r,t;
vector<int> s;
cin>>n;
for(int i=0; i<n; i++) {
cin>>r;
s.clear();
for(int j=0; j<r; j++) {
cin>>t;
s.push_back(t);
}
sort(s.begin(),s.end());
int mid=s[r/2],sum = 0;
for(int j=0; j<r; j++) sum+=abs(s[j]-mid);
cout<<sum<<endl;
}
return 0;
}
```
```python=
# python參考程式
n = int(input())
for i in range(n):
adr = input().split()
adr.pop(0)
adr = [int(s) for s in adr]
adr.sort()
med = adr[len(adr)//2]
ll = 0
for a in adr:
ll+= abs(a-med)
print(ll)
```
#### 2. Hashmat the brave warrior (CPE10407, UVA10055)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=996)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=a012)
- **題意**
- ...
- **解法**
- ...
```cpp=
// c++參考程式
#include <stdio.h>
int main() {
long long a,b,c;
while(scanf("%lld %lld",&a,&b)!=EOF) {
c = a-b;
if(c<0) c = -c;
printf("%lld\n",c);
}
return 0;
}
```
```python=
# python參考程式
import sys
for s in sys.stdin:
a,b = s.split()
a,b = int(a),int(b)
print(abs(a-b))
```
#### 3. Primary Arithmetic (CPE10404, UVA10035)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=976)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=c014)
- **題意**
- ...
- **解法**
- ...
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
int main() {
int a,b,c,cnt;
while(cin>>a>>b && ((a!=0)||(b!=0)) ) {
c=0; cnt=0;
for(int i=0; i<10; i++) {
if((a%10)+(b%10)+c>9) { c=1; cnt++; }
else c=0;
a/=10; b/=10;
}
if(cnt>1) cout<<cnt<<" carry operations."<<endl;
else if(cnt==1) cout<<"1 carry operation."<<endl;
else cout<<"No carry operation."<<endl;
}
return 0;
}
```
```python=
# python參考程式
a,b = map(int,input().split())
while a!=0 or b!=0:
c,cnt = 0,0 # initial value of carry and its count
for i in range(10):
if a%10+b%10+c>9: c,cnt = 1,cnt+1
else: c = 0
a,b = a//10,b//10
if cnt>1: print(cnt,'carry operations.')
elif cnt==1: print('1 carry operation.')
else: print('No carry operation.')
a,b = map(int,input().split())
```
#### 4. The 3n + 1 problem (CPE10400, UVA100)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=c039)
- **題意**
- ...
- **解法**
- ...
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
int main() {
int a,b,c,d,cmax,cnt,t;
while(cin>>a>>b) {
cmax=0; c=a; d=b;
if(c>d) { t=c; c=d; d=t; }
for(int i=c; i<=d; i++) {
cnt=1; t=i;
while(t!=1) {
if(t&1!=0) { t=3*t+1; cnt++; }
else { t>>= 1; cnt++; }
}
if(cmax<cnt) cmax = cnt;
}
cout<<a<<" "<<b<<" "<<cmax<<endl;
}
return 0;
}
```
```python=
# python參考程式
import sys
for s in sys.stdin:
a,b = map(int,s.split())
xa,xb = a,b
if xa>xb: xa,xb = xb,xa
ma = 1
for x in range(xa,xb+1):
cnt = 1
while x!=1:
if x&1==0: x//= 2
else: x = 3*x+1
cnt+= 1
if cnt>ma: ma = cnt
print(a,b,ma)
```
#### 5. You can say 11 (CPE10460, UVA10929)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1870)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=d235)
- **題意**
- ...
- **解法**
- ...
```cpp=
// c++參考程式
#include <string>
#include <iostream>
using namespace std;
int main() {
string s;
int es,os;
while(cin>>s && s!="0") {
es=os=0;
for(int i=0; i<s.length(); i++)
if(i%2==0) es+= s[i]-'0';
else os+= s[i]-'0';
if((es-os)%11==0)
cout<<s<<" is a multiple of 11."<<endl;
else
cout<<s<<" is not a multiple of 11."<<endl;
}
return 0;
}
```
```python=
# python參考程式
s = input()
while s!='0':
es,os = 0,0
for i in range(len(s)):
t = int(s[i])
if i%2==0: es+= t
else: os+= t
if (es-os)%11==0: print(s,'is a multiple of 11.')
else: print(s,'is not a multiple of 11.')
s = input()
```
#### 6. Bangla Numbers (CPE10414, UVA10101)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1042)
- [Zerojudge收納](https://)
- **題意**
- ...
- **解法**
- ...
```cpp=
// c++參考程式
#include <string>
#include <iomanip>
#include <sstream>
#include <iostream>
using namespace std;
const string u[] = {" lakh"," hajar"," shata",""};
void kuti(int d) {
int base[] = {100000,1000,100,1};
int modu[] = {100,100,10,100};
int v;
for(int i=0; i<4;i++) {
v = d/base[i]%modu[i];
if(v!=0) cout<<" "<<v<<u[i];
}
return;
}
int main() {
string s;
int cnt=1,len,n,r,x;
while(cin>>s) {
cout<<setw(4)<<cnt++<<".";
if(s=="0") cout<<" 0"<<endl;
else {
len = s.size();
n = len/7; r = len%7;
if(r==0) { r=7; n--; }
for(int i=0; i<=n; i++) {
stringstream ss;
if(i==0) ss<<s.substr(0,r);
else {
ss<<s.substr(r,7);
r+=7;
}
ss>>x;
kuti(x);
if(i<n) cout<<" kuti";
}
cout<<endl;
}
}
return 0;
}
```
```python=
# python參考程式
def sec(num):
if num//10000000>0:
sec(num//10000000) # 遞迴處理
print(" kuti",end='')
num%= 10000000
if num//100000>0:
print(' ',num//100000,' lakh',sep='',end='')
num%=100000
if num//1000>0:
print(' ',num//1000,' hajar',sep='',end='')
num%=1000
if num//100>0:
print(' ',num//100,' shata',sep='',end='')
num%=100
if num>0:
print(' ',num,sep='',end='')
cnt = 1
while True:
try:
n = int(input())
print(cnt,'.',sep='',end='')
if n==0: print(' 0',end='')
else: sec(n)
print()
cnt+= 1
except:
break
```
#### 7. List of Conquests (CPE21924, UVA10420)
- **題目**
- [原始題目連結](https://)
- [Zerojudge收納](https://)
- **題意**
- ...
- **解法**
- ...
```cpp=
// c++參考程式
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int n,i,cnt;
string s[2000],name,t;
// 1. 讀入個數
cin>>n;
// 2. 讀入所有字串
for(i=0; i<n; i++) {
cin>>s[i];
getline(cin,name);
}
// 3. 排序
sort(s,s+n);
// 4. 統計 & 輸出
t=s[0]; i=1; cnt=1;
while(i<n) {
if(s[i]==t) cnt++;
else {
cout<<t<<" "<<cnt<<endl;
t = s[i]; cnt = 1;
}
i++;
}
cout<<t<<" "<<cnt<<endl;
return 0;
}
```
```python=
# python參考程式
# 讀入個數
n = int(input())
# 讀入字串、計數，沒有就新增
bu = {}
for i in range(n):
s = input().split()[0]
if s in bu.keys(): bu[s]+= 1
else: bu.update({s:1})
# 排序 & 輸出
for i in sorted(bu):
print(i,bu[i])
```
### 二、字元與字串
:::success
8. What's Cryptanalysis? (CPE10402, UVA10008)
9. Decode the Mad man (CPE10425, UVA10222)
10. Problem J: Summing Digits (CPE10473, UVA11332)
11. Common Permutation (CPE10567, UVA10252)
12. Rotating Sentences (CPE21914, UVA490)
13. TeX Quotes (CPE22131, UVA272)
:::
#### 8. What's Cryptanalysis? (CPE10402, UVA10008)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=949)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=c044)
- **題意**
- ...
- **解法**
- ...
```cpp=
// C++ 參考作法 1
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
int al[26];
string s;
for(int i=0; i<26; i++) al[i]=0;
cin>>n;
cin.get();
for(int i=0; i<n; i++) {
getline(cin,s);
//cout<<s<<": length="<<s.length()<<endl;
for(int j=0; j<s.length();j++) {
if(s[j]>='A' && s[j]<='Z') al[s[j]-'A']++;
if(s[j]>='a' && s[j]<='z') al[s[j]-'a']++;
}
}
int max=0;
for(int i=0; i<26; i++) if(al[i]>max) max=al[i];
while(max>0) {
for(int i=0; i<26; i++)
if(al[i]==max)
cout<<(char) ('A'+i)<<" "<<al[i]<<endl;
max--;
}
return 0;
}
```
```cpp=
// c++參考作法 2
#include <algorithm>
#include <iostream>
using namespace std;
struct ALS {
char ch;
int cnt;
};
bool comp(ALS a, ALS b) {
return a.cnt>b.cnt;
}
int main() {
ALS al[26];
int n;
char c;
for(int i=0; i<26; i++) {
al[i].ch='A'+i;
al[i].cnt = 0;
}
cin>>n;
while(cin>>c) {
if(c>='a' && c<='z') al[c-'a'].cnt++;
if(c>='A' && c<='Z') al[c-'A'].cnt++;
}
stable_sort(al,al+26,comp);
for(int i=0; i<26; i++) {
if(al[i].cnt!=0)
cout<<al[i].ch<<" "<<al[i].cnt<<endl;
}
return 0;
}
```
```cpp=
// c++參考作法 3
#include <iostream>
#include <cctype>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
int n;
cin>>n;
cin.ignore(); //怕說按完enter會影響下面getline的判斷所以用這個
string line; //line變數=每一行讀完放哪裡
map<char, int> mapmain; //定義一下map 等等要存letter跟數字。用mapmain＝map的主體
while(n>0){ //多少行
getline(cin, line); //開讀
for(char ch: line){ //設一個變數來代替line(在這個for而已)。將line的所有字母都讀進去。
//因為只要取每個字母就好，所以用char。
if(isalpha(ch)){ //確認一下輸入的是字母
char mapkey=toupper(ch); //讓map的key也就是第一屬性＝(line一個一個讀進來的char)大寫後的
mapmain[mapkey]++; //主體裡面[key值對應的value]++
}
}
n--; //讀完一行，-1，讀下一行
}
vector<pair<char, int>> newmain(mapmain.begin(), mapmain.end());//把map值存進vector。
//用.begin() .end()表示存哪些
auto compare=[](const auto& a, const auto& b){//lambda寫如何排序。auto會自己變成變數，就不用寫出pair了
if(a.second==b.second){ //當第二項一樣，那以第一項去比。上一行（數值不會改變加const &代表給予權利改值）
return a.first < b.first;//那就第一項小到大
}
return a.second > b.second; //第二項大到小
};
sort(newmain.begin(), newmain.end(),compare); //sort加上更改排序的方式
for (const auto& au: newmain){ // 將vector裡面的那堆pair
cout<< au.first<<" "<<au.second <<endl; //cout出來
}
return 0;
}
```
```cpp=
// c++參考作法 3
#include <iostream>
#include <cctype>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
int n;
cin>>n;
cin.ignore(); //怕說按完enter會影響下面getline的判斷所以用這個
string line; //line變數=每一行讀完放哪裡
map<char, int> mapmain; //定義一下map 等等要存letter跟數字。用mapmain＝map的主體
while(n>0){ //多少行
getline(cin, line); //開讀
for(char ch: line){ //設一個變數來代替line(在這個for而已)。將line的所有字母都讀進去。
//因為只要取每個字母就好，所以用char。
if(isalpha(ch)){ //確認一下輸入的是字母
char mapkey=toupper(ch); //讓map的key也就是第一屬性＝(line一個一個讀進來的char)大寫後的
mapmain[mapkey]++; //主體裡面[key值對應的value]++
}
}
n--; //讀完一行，-1，讀下一行
}
vector<pair<char, int>> newmain(mapmain.begin(), mapmain.end());//把map值存進vector。
//用.begin() .end()表示存哪些
auto compare=[](const auto& a, const auto& b){//lambda寫如何排序。auto會自己變成變數，就不用寫出pair了
if(a.second==b.second){ //當第二項一樣，那以第一項去比。上一行（數值不會改變加const &代表給予權利改值）
return a.first < b.first;//那就第一項小到大
}
return a.second > b.second; //第二項大到小
};
sort(newmain.begin(), newmain.end(),compare); //sort加上更改排序的方式
for (const auto& au: newmain){ // 將vector裡面的那堆pair
cout<< au.first<<" "<<au.second <<endl; //cout出來
}
return 0;
}
```
```python=
# python參考做法
n = int(input())
freq = [0]*26
au = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
al = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
s = input()
for c in s:
if c in au:
freq[ord(c)-65]+= 1
elif c in al:
freq[ord(c)-97]+= 1
ma = max(freq)
while ma>0:
for i in range(26):
if freq[i]==ma:
print(chr(i+65),freq[i])
ma-= 1
```
#### 9. Decode the Mad man (CPE10425, UVA10222)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1163)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e578)
- **題意**
- ...
- **解法**
- ...
```cpp=
// C++ 參考
#include <iostream>
using namespace std;
int main() {
string s,dic = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
while(getline(cin,s)) {
for(int i=0; i<s.length(); i++)
if(s[i]!=' ')
s[i] = dic[dic.find(s[i])-2];
cout<<s<<endl;
}
return 0;
}
```
```python=
# python 參考
src = "234567890-=ertyuiop[]\dfghjkl;'cvbnm,./"
dic = "`1234567890qwertyuiop[asdfghjklzxcvbnm,"
while True:
try:
s = input()
for c in s:
c = c.lower()
if c in src:
print(dic[src.index(c)],end='')
else:
print(" ",end='')
print()
except: break
```
#### 10. Problem J: Summing Digits (CPE10473, UVA11332)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2307)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=c813)
- **題意**
- ...
- **解法**
- ...
#### 11. Common Permutation (CPE10567, UVA10252)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1193)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e507)
- **題意**
- ...
- **解法**
- ...
#### 12. Rotating Sentences (CPE21914, UVA490)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=431)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=c045)
- **題意**
- ...
- **解法**
- ...
#### 13. TeX Quotes (CPE22131, UVA272)
- **題目**
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=208)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=c007)
- **題意**
- ...
- **解法**
- ...
```cpp=
// C++ 參考
#include <string>
#include <iostream>
using namespace std;
int main() {
int st=0;
string s;
while(getline(cin,s)) {
for(int i=0; i<s.length(); i++) {
if(s[i]!='\"') cout<<s[i];
else {
if(st==0) {
cout<<"``";
st = 1;
}
else {
cout<<"\'\'";
st = 0;
}
}
}
cout<<endl;
}
return 0;
}
```
```python=
# Python 參考
st = 0
while True:
try:
s = input()
for c in s:
if c!='"': print(c,end='')
else:
if st==0:
print("``",end='')
st = 1
else:
print("''",end='')
st = 0
print()
except:
break
```
### 三、數學計算
:::success
14. A - Doom's Day Algorithm (CPE22801, UVA12019)
15. Jolly Jumpers (CPE10405, UVA10038)
16. What is the Probability!! (CPE10408, UVA10056)
17. The Hotel with Infinite Rooms (CPE10417, UVA10170)
18. 498’ (CPE10431, UVA10268)
19. Odd Sum (CPE10453, UVA10783)
20. Beat the Spread! (CPE10454, UVA10812)
21. Symmetric Matrix (CPE10478, UVA11349)
22. Square Numbers (CPE10480, UVA11461)
23. B2-Sequence (CPE23621, UVA11063)
24. Back to High School Physics (CPE10411, UVA10071)
:::
#### 14. A - Doom's Day Algorithm (CPE22801, UVA12019)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3170)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=f709)
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
// 回推各日期餘數對應的星期
string week[] = {"Friday","Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday"};
int count[] = {0,31,59,90,120,151,181,212,243,273,304,334,365};
int main() {
int n,m,d;
cin>>n;
for(int i=0; i<n; i++) {
cin>>m>>d;
cout<<week[(count[m-1]+d)%7]<<endl;
}
return 0;
}
```
```python=
# python參考程式
week = "Friday","Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday"
count = 0,31,59,90,120,151,181,212,243,273,304,334,365
n = int(input())
for i in range(n):
m,d = map(int,input().split())
print(week[(count[m-1]+d)%7])
```
#### 15. Jolly Jumpers (CPE10405, UVA10038)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=979)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=d097)
#### 16. What is the Probability!! (CPE10408, UVA10056)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=997)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
* 公式推導
* 等比級數 $S = a+ar+ar^2+\cdots+ar^{k-1}=\frac{a(1-r^n)}{1-r}$
* 第一位贏的機率: 第一次贏、第一輪大家輸第二輪贏、...
$p_1=p+p(1-p)^n+p(1-p)^{2n}+\cdots=\frac{p}{1-(1-p)^n}$
$p_2=(1-p)p(1+(1-p)^n+(1-p)^{2n}+\cdots) =\frac{(1-p)p}{1-(1-p)^n}$
$$\vdots$$
$p_i=(1-p)^{i-1}p(1+(1-p)^n+(1-p)^{2n}+\cdots) =\frac{(1-p)^{i-1}p}{1-(1-p)^n}$
```Cpp=
// C 參考程式
#include <cstdio>
#include <cmath>
int main() {
int s,n,i;
double p,r;
scanf("%d",&s);
for(int t=0; t<s; t++) {
scanf("%d %lf %d",&n,&p,&i);
r = pow(1.0-p,i-1)*p/(1.0-pow(1.0-p,n));
printf("%6.4f\n",r);
}
return 0;
}
```
```cpp=
// C++ 參考程式
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
int s,n,i;
double p,r;
cin>>s;
for(int t=0; t<s; t++) {
cin>>n>>p>>i;
r = pow(1.0-p,i-1)*p/(1.0-pow(1.0-p,n));
cout<<fixed<<setprecision(4)<<r<<endl;
}
return 0;
}
```
```python=
# Python參考程式
s = int(input())
for t in range(s):
n,p,i = input().split()
n,p,i = int(n),float(p),int(i)
r = (1-p)**(i-1)*p/(1-(1-p)**n)
print('%6.4f' %r)
```
#### 17. The Hotel with Infinite Rooms (CPE10417, UVA10170)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1111)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e555)
#### 18. 498’ (CPE10431, UVA10268)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1209)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
#### 19. Odd Sum (CPE10453, UVA10783)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1724)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
#### 20. Beat the Spread! (CPE10454, UVA10812)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1753)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
#### 21. Symmetric Matrix (CPE10478, UVA11349)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2324)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
#### 22. Square Numbers (CPE10480, UVA11461)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2456)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
#### 23. B2-Sequence (CPE23621, UVA11063)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2004)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
#### 24. Back to High School Physics (CPE10411, UVA10071)
- 題目
- [原始題目連結](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1012)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=e510)
### 四、進位制轉換
:::success
25. An Easy Problem! (CPE10413, UVA10093)
26. Fibonaccimal Base (CPE10401, UVA948)
27. Funny Encryption Method (CPE10403, UVA10019)
28. Parity (CPE10461, UVA10931)
29. Cheapest Base (CPE10466, UVA11005)
:::
#### 25. An Easy Problem! (CPE10413, UVA10093)
#### 26. Fibonaccimal Base (CPE10401, UVA948)
```cpp=
#include <iostream>
using namespace std;
void fib(int b[]) {
b[1]=1; // b[0]: # of fib_base
b[2]=2; // b[i]: the bases
int i=2;
while(b[i]<=100000000) {
i++;
b[i]=b[i-1]+b[i-2];
}
b[0]=i-1;
return;
}
int main() {
int b[39],n,num,tn,k;
char r[39];
fib(b);
cin>>n;
for(int i=0; i<n; i++) {
cin>>num;
tn=num; k=b[0];
while(tn<b[k]) k--;
for(int j=k; j>0; j--)
if(tn<b[j]) r[k-j]='0';
else {
r[k-j]='1';
tn-= b[j];
}
r[k]=0;
cout<<num<<" = "<<r<<" (fib)"<<endl;
}
return 0;
}
```
#### 27. Funny Encryption Method (CPE10403, UVA10019)
```cpp=
#include <iostream>
using namespace std;
int hw[] = {0,1,1,2,1,2,2,3,1,2};
int DecW(int n) {
int c=0;
while(n!=0) {
if(n&1!=0) c++;
n/= 2;
}
return c;
}
int HexW(int n) {
int c=0;
while(n!=0) {
c+= hw[n%10];
n/= 10;
}
return c;
}
int main() {
int t,n;
cin>>t;
for(int i=0; i<t; i++) {
cin>>n;
cout<<DecW(n)<<" "<<HexW(n)<<endl;
}
return 0;
}
```
```python=
t = int(input())
for i in range(t):
n = input()
x1 = bin(int(n))[2::].count('1')
x2 = bin(int(n,16))[2::].count('1')
print(x1,x2)
```
#### 28. Parity (CPE10461, UVA10931)
#### 29. Cheapest Base (CPE10466, UVA11005)
### 五、質數、因數與倍數
:::success
30. Hartals (CPE10517, UVA10050)
31. All You Need Is Love! (CPE10421, UVA10193)
32. Divide, But Not Quite Conquer! (CPE10419, UVA10190)
33. Simply Emirp (CPE10428, UVA10235)
34. 2 the 9s (CPE10458, UVA10922)
35. GCD (CPE11076, UVA11417)
:::
#### 30. Hartals (CPE10517, UVA10050)
#### 31. All You Need Is Love! (CPE10421, UVA10193)
#### 32. Divide, But Not Quite Conquer! (CPE10419, UVA10190)
#### 33. Simply Emirp (CPE10428, UVA10235)
#### 34. 2 the 9s (CPE10458, UVA10922)
#### 35. GCD (CPE11076, UVA11417)
### 六、幾何與座標
:::success
36. Largest Square (CPE10456, UVA10908)
37. Satellites (CPE10424, UVA10221)
38. Can You Solve It? (CPE10447, UVA10642)
39. Fourth Point!! (CPE10566, UVA10242)
:::
#### 36. Largest Square (CPE10456, UVA10908)
#### 37. Satellites (CPE10424, UVA10221)
#### 38. Can You Solve It? (CPE10447, UVA10642)
#### 39. Fourth Point!! (CPE10566, UVA10242)
### 七、排序與中位數
:::success
40. A mid-summer night’s dream (CPE10409, UVA10057)
41. Tell me the frequencies! (CPE10410, UVA10062)
42. Train Swapping (CPE22811, UVA299)
43. Hardwood Species (CPE10426, UVA10226)
:::
#### 40. A mid-summer night’s dream (CPE10409, UVA10057)
#### 41. Tell me the frequencies! (CPE10410, UVA10062)
#### 42. Train Swapping (CPE22811, UVA299)
#### 43. Hardwood Species (CPE10426, UVA10226)
### 八、模擬
:::success
44. Minesweeper (CPE10418, UVA10189)
45. Die Game (CPE11019, UVA10409)
46. Eb Alto Saxophone Player (CPE11020, UVA10415)
47. Mutant Flatworld Explorers (CPE23641, UVA118)
48. Cola (CPE11067, UVA11150)
:::
#### 44. Minesweeper (CPE10418, UVA10189)
#### 45. Die Game (CPE11019, UVA10409)
#### 46. Eb Alto Saxophone Player (CPE11020, UVA10415)
#### 47. Mutant Flatworld Explorers (CPE23641, UVA118)
#### 48. Cola (CPE11067, UVA11150)
### 九、其他
:::success
49. Sort! Sort!! and Sort!!! (CPE11069, UVA11321)
:::
#### 49. Sort! Sort!! and Sort!!! (CPE11069, UVA11321)
- **題目**
- [原始題目連結](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2296)
- [Zerojudge收納](https://zerojudge.tw/ShowProblem?problemid=d750)
- **題意**
- ...
- **解法**
- ...
```cpp=
// c++參考程式
#include <algorithm>
#include <iostream>
using namespace std;
int m;
bool comp(int a, int b) {
bool flag;
int ra,rb,ia,ib;
ra=a%m; rb=b%m;
ia=a%2; ib=b%2;
if(ra!=rb) flag = ra<rb;
else {
if(ia!=ib) flag = ia>ib;
else {
if(ia==1) flag = a>b;
else flag = a<b;
}
}
return flag;
}
int main() {
int d[10000];
int n;
//1. 讀入 N,M及所有整數
while(cin>>n>>m && n!=0 && m!=0) {
for(int i=0; i<n; i++) cin>>d[i];
//2. 排序
sort(d,d+n,comp);
//3. 輸出
cout<<n<<" "<<m<<endl;
for(int i=0; i<n; i++) cout<<d[i]<<endl;
}
cout<<"0 0"<<endl;
return 0;
}
```
```python=
# python參考程式
```
## 考題交流
### [歷屆考題](https://cpe.cse.nsysu.edu.tw/cpe/test_data/problems)
### 2023.03.21 (二)
* [10035: Primary Arithmetic](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10035.pdf)
- [ZJ-c014](https://zerojudge.tw/ShowProblem?problemid=c014)
- **題意**:
- **解法**:
```cpp=
// c++參考程式
#include <iostream>
using namespace std;
int main() {
int a,b,c,cnt;
//輸入
while(cin>>a>>b && !(a==0 && b==0)) {
//處理 - 從右到左逐字整理
c = 0; cnt=0; //c:進位、cnt:進位數
while(a!=0 || b!=0) { //當a,b不全為0，相加一位數
if(a%10+b%10+c>9) {
c=1; cnt++;
}
else c=0;
a/= 10; b/= 10;
}
//輸出
if(cnt==0) cout<<"No carry operation.\n";
else if(cnt>1) cout<<cnt<<" carry operations.\n";
else cout<<"1 carry operation.\n";
}
return 0;
}
```
```python=
# python參考程式
a,b = input().split()
while a!='0' or b!='0':
a,b = int(a),int(b)
c,cnt = 0,0
while a!=0 or b!=0:
if a%10+b%10+c>9: c,cnt = 1,cnt+1
else: c=0
a,b = a//10,b//10
if cnt>1: print(cnt,'carry operations.')
elif cnt==1: print('1 carry operation.')
else: print('No carry operation.')
a,b = input().split()
```
* [11824: A Minimum Land Price](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11824.pdf)
- [ZJ-j038](https://zerojudge.tw/ShowProblem?problemid=j038)
- **題意**:
- **解法**:
```cpp=
// c++參考程式
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a,int b) {
return a>b;
}
int main() {
int n,al[40],x,cnt;
double p,t;
cin>>n;
for(int i=0; i<n; i++) {
cnt = 0;
while(cin>>x && x!=0) al[cnt++]=x;
sort(al,al+cnt,cmp);
p = 0.0;
for(int j=0; j<cnt; j++) {
p+= 2*pow(al[j],j+1);
}
if(p<=5000000.0) cout<<int(p)<<endl;
else cout<<"Too expensive"<<endl;
}
return 0;
}
```
```python=
# python參考程式
n = int(input())
for i in range(n):
al = []
x = int(input())
while x!=0:
al.append(x)
x = int(input())
al.sort(reverse=True)
p = 0
for j in range(len(al)):
p+= 2*al[j]**(j+1)
if p<=5000000: print(p)
else: print('Too expensive')
```
### 2022.12.13 (二)
* [10931: Parity](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10931.pdf)
- [ZJ-a132](https://zerojudge.tw/ShowProblem?problemid=a132)
- **題意**:
- **解法**:
```cpp=
// c++參考程式
#include <string>
#include <iostream>
using namespace std;
int main() {
int x,w,a[32],i;
while(cin>>x && x!=0) {
i=0; w=0;
while(x!=0) {
a[i]=x%2;
if(a[i]!=0) w++;
x/= 2; i++;
}
cout<<"The parity of ";
for(int j=i-1; j>=0; j--) cout<<a[j];
cout<<" is ";
cout<<w;
cout<<" (mod 2)."<<endl;
}
return 0;
}
```
```python=
# python參考程式
a = int(input())
while a!=0:
aa = bin(a)[2::]
print('The parity of',aa,'is',aa.count('1'),'(mod 2).')
a = int(input())
```
* [10789: Prime Frequency](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10789.pdf)
- [ZJ-a537](https://zerojudge.tw/ShowProblem?problemid=a537)
- **題意**:
- **解法**:
```cpp=
// c++參考程式
#include <cmath>
#include <string>
#include <iostream>
using namespace std;
//檢查是否為質數
const int PM = (int) sqrt(2000);
bool isPrime(int a) {
bool isp=true;
if(a==1 && a==0) isp=false;
else if(a>2) {
if(a%2==0) isp=false;
else {
int t=3;
while(t<PM && isp) {
if(a%t==0) isp = false;
t+=2;
}
}
}
return isp;
}
int main() {
int n,p;
string s,ds="0123456789";
string as0="ABCDEFGHIJKLMNOPQRSTUVWXYZ",as1="abcdefghijklmnopqrstuvwxyz";
string ads = ds+as0+as1;
int adc[62];
cin>>n;
for(int i=0; i<n; i++) {
for(int j=0; j<62; j++) adc[j]=0;
cin>>s;
//字元統計
for(int j=0; j<s.length(); j++) {
p = ads.find(s[j]);
adc[p]++;
}
//輸出
for(int j=0; j<62; j++)
if(isPrime(adc[j])) cout<<ads[j];
cout<<endl;
}
return 0;
}
```
```python=
# python參考程式
def pt2001():
pt = [2,3,5,7]
for i in range(9,2001,2):
isPrime = True
for x in pt:
if i%x==0: isPrime = False
if isPrime: pt.append(i)
return pt
pt = pt2001()
cs0 = '0123456789'
cs1 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
cs2 = 'abcdefghijklmnopqrstuvwxyz'
cs = cs0+cs1+cs2
n = int(input())
for i in range(1,n+1):
print('Case ',i,': ',sep='',end='')
s = input()
cnt = 0
for c in cs:
if s.count(c) in pt:
print(c,end='')
cnt+= 1
if cnt==0: print('empty')
else: print()
```
### 2024.10.15 (二) [CPE](https://cpe.cse.nsysu.edu.tw/cpe/test_data/2024-10-15)
* 1. 10008: What's Cryptanalysis?
```cpp=
#include <iostream>
using namespace std;
int main() {
char c;
int n,freq[26],ma;
for(int i=0; i<26; i++) freq[i]=0;
cin>>n;
while(cin>>c) {
if(c>='A' && c<='Z') freq[c-'A']++;
else if(c>='a' && c<='z') freq[c-'a']++;
}
ma = 0;
for(int i=0; i<26; i++)
if(ma<freq[i]) ma = freq[i];
for(int i=ma; i>0; i--)
for(int j=0; j<26; j++)
if(freq[j]==i) {
c = 'A'+j;
cout<<c<<' '<<i<<endl;
}
return 0;
}
```
```python=
freq = [0]*26
n =int(input())
for i in range(n):
s = input()
for c in s:
t = ord(c.upper())-65
if t in range(26): freq[t]+= 1
ma = max(freq)
for i in range(ma,0,-1):
for j in range(26):
if freq[j]==i:
print(chr(65+j),i)
```
```python=
alf = {}
for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
alf.update({c:0})
n =int(input())
for i in range(n):
s = input()
for c in s:
d = c.upper()
if d in alf.keys(): alf[d]+= 1
alf = dict(sorted(alf.items(), key = lambda item:item[1], reverse=True))
for c in alf:
if alf[c]>0: print(c,alf[c])
```
* 2. 10107: What is the Median?
```cpp=
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long long x;
vector <long long> a;
while(cin>>x) {
a.push_back(x);
sort(a.begin(),a.end());
cout<<(a[a.size()/2]+a[(a.size()-1)/2])/2<<endl;
}
return 0;
}
```
```python=
n,a = 0,[]
while True:
try:
x = int(input())
a.append(x)
a.sort()
n+= 1
if n%2==1: print(a[n//2])
else:
print((a[n//2]+a[n//2-1])//2)
except:
break
```
* 3. 10110: Light, more light
```cpp=
#include <cmath>
#include <iostream>
using namespace std;
int main() {
long long n;
int r;
cin>>n;
while(n!=0) {
r = (int) sqrt(n);
if(n==r*r) printf("yes\n");
else printf("no\n");
cin>>n;
}
return 0;
}
```
```python=
n = int(input())
while n!=0:
r = int(n**0.5)
if n==r*r: print('yes')
else: print('no')
n = int(input())
```
* 4. 10539: Almost Prime Numbers
```cpp=
```
```python=
pt = [1]*1000001
apt = []
def getpt():
pt[0],pt[1] = 0,0
for i in range(2,1001):
for j in range(i+i,1000001,i): pt[j] = 0
return
def getapt():
for i in range(len(pt)):
if pt[i]!=0:
t = i*i
while t<1000000000000:
apt.append(t)
t*= i
apt.sort()
getpt()
getapt()
n = int(input())
for i in range(n):
a,b = input().split()
a,b = int(a),int(b)
print(len([x for x in apt if a<=x<=b]))
```
```python=
import bisect
pt = [1]*1000001
apt = []
def getpt():
pt[0],pt[1] = 0,0
for i in range(2,1001):
for j in range(i+i,1000001,i): pt[j] = 0
return
def getapt():
for i in range(len(pt)):
if pt[i]!=0:
t = i*i
while t<1000000000000:
apt.append(t)
t*= i
apt.sort()
getpt()
getapt()
n = int(input())
for i in range(n):
a,b = input().split()
a,b = int(a),int(b)
x = bisect.bisect_left(apt,a)
y = bisect.bisect_right(apt,b)
print(y-x)
```
## 有興趣一起討論的題目
### 同學建議題目
* CPE 2023/03/21 第4題
* 題意
* …
* 解法
* …
[11240: Antimonotonicity](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11240.pdf)
```cpp=
// c++參考程式
# include <iostream>
using namespace std;
int count(int n,int seq[]) {
int leng=1; // 長度最小為 1
int st=0; // 0:找>、1找<
for(int i=1; i<n; i++) {
if(st==0) {
if(seq[i-1]>seq[i]) { leng++; st=1; }
}
else if(st==1) {
if(seq[i-1]<seq[i]) { leng++; st=0; }
}
}
return leng;
}
int main() {
int t,n,seq[30000];
cin>>t;
for(int i=0; i<t; i++) {
cin>>n;
for(int j=0; j<n; j++) cin>>seq[j];
cout<<count(n,seq)<<endl;
}
return 0;
}
```
```python=
# python參考程式
def count(seq):
leng = 1 # 長度最小為 1
st = 0 # 0:找>、1找<
for i in range(1,len(seq)):
if st==0:
if seq[i-1]>seq[i]:
leng,st = leng+1,1
elif st==1:
if seq[i-1]<seq[i]:
leng,st = leng+1,0
return leng
t = int(input())
for i in range(t):
s = input().split()
s.pop(0)
for j in range(len(s)): s[j]=int(s[j])
print(count(s))
```
### 老師建議題目
Sign in with Wallet
Connect another wallet