---
# System prepended metadata

title: 程式能力檢定_2020
tags: [ISU109a]

---

# 程式能力檢定_2020
###### tags: `ISU109a`

## 01. 基本I/O
### 輸入類型題目
- 上課講解
1. 讀入 𝑛 筆資料 (知道讀幾個)
   - Ex: UVA 10041 Vito's family
2. 讀至檔案結束 (不知讀幾個，讀到沒有資料為止)
   - Ex: UVA 10055 Hashmat the brave warrior
3. 讀至 0 結束     (不知讀幾個，讀到符合條件資料為止)
   - Ex: UVA 10035 Primary Arithmetic

- 練習題目

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)

- Q & A

## 02. 善用暨有資源

### 利用已有資源
- 上課講解
1. 自己撰寫函數 (字串、口語數字)
   - Ex: UVA 10101 Bangla Numbers
``` 'C++'=
#include <iostream>
#include <string>
using namespace std;
const string s[]={" lakh"," hajar"," shata",""};

void kuti(int d) {
	int base[] = {100000,1000,100,1};
	int mod[] = {100,100,10,100};
	int v;
	for(int i=0; i<4; i++) {
		v=d/base[i]%mod[i];
		if(v!=0) cout<<" "<<v<<s[i];
	}
}

int main() {
	long long n,a,b,c,base=10000000;
	int cnt=1;
	
	while(cin>>n) {
		cout<<"    "<<cnt++<<".";
		a=n/base/base;
		b=n/base%base;
		c=n%base;
		if(a!=0) {
			kuti(a);
			cout<<" kuti";
		}
		if((a|b)!=0) {
			kuti(b);
			cout<<" kuti";
		}
		if(c!=0) {
			kuti(c);
		}
		if(n==0) cout<<" 0";
		cout<<endl;
	}
	return 0;
}

```

2. 字串、排序
   - Ex: UVA 10420 List of Conguests
3. 迴圈、排序
   - Ex: UVA 11321 Sort! Sort!! and Sort!!!
``` 'C++'=
#include <iostream>
#include <algorithm>
using namespace std;

struct Num {
	int n;
	int r,o;
};

bool comp(Num x, Num y) {
	bool result=true;
	if(x.r<y.r) result=true;
	else if(x.r>y.r) result=false;
	else if(x.o!=y.o) result=(x.o>y.o);
	else {
		if(x.o==1) result=(x.n>y.n);
		else result=(x.n<y.n); 
	}
	return result;
}

int main() {
	Num ad[10000];	
	int m,n;
	while((cin>>n>>m) && (m!=0 || n!=0)) {
		for(int i=0; i<n; i++) {
			cin>>ad[i].n;
			ad[i].r = ad[i].n%m;
			ad[i].o = ad[i].n&0x1; //%2之義 
		}
		sort(ad,ad+n,comp);
		cout<<n<<" "<<m<<endl;
		for(int i=0; i<n; i++) cout<<ad[i].n<<endl;
	}
	cout<<"0 0"<<endl;
	return 0;
}
```

``` 'c++'=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Num {
	int n;
	int r,o;  //r: 除以m餘數, o: 1為奇數, 0為偶數 
};

bool comp(Num x, Num y) {
	bool result=true;
	if(x.r<y.r) result=true;
	else if(x.r>y.r) result=false;
	else if(x.o!=y.o) result=(x.o>y.o);
	else {
		if(x.o==1) result=(x.n>y.n);
		else result=(x.n<y.n); 
	}
	return result;
}

int main() {
	vector<Num> ad;	
	int m,n;
	Num d;
	while((cin>>n>>m) && (m!=0 || n!=0)) {
		ad.clear();
		for(int i=0; i<n; i++) {
			cin>>d.n;
			d.r = d.n%m;
			d.o = d.n&0x1; //%2之義 
			ad.push_back(d);
		}
		sort(ad.begin(),ad.end(),comp);
		cout<<n<<" "<<m<<endl;
		for(int i=0; i<n; i++) cout<<ad[i].n<<endl;
	}
	cout<<"0 0"<<endl;
	return 0;
}
```


## 03.  一顆星選集 – 字串

* 上課講解
要領:
  - Count
  - Table lookup
  - Type convert
  - Substring 
* Count 
  * 8. What's Cryptanalysis? (CPE10402, UVA10008) 
```C++=
#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;
}
```
```C++=
#include<iostream>
using namespace std;
struct count {
	int num=0;
	char a;
};
int main(){
	int n;
	string str;
	cin>>n;
	n++;
	count c1[26];
		for(int i=0;i<26;i++)
		{
			c1[i].a=i+65;
		}
	while(n--){
		getline(cin,str);
		for(int i=0;i<str.length();i++)
		{
			if(str[i]>96&&str[i]<123)
			{
				str[i]-=32;
			}
			if(str[i]>64&&str[i]<91)
			{
				c1[str[i]-65].num++;
			}
		}

	}
	int max=0;
	
		for(int i=0;i<26;i++)
		{
			if(c1[i].num>max)
			max=c1[i].num;
		}
	
		for(int j=max;j>=1;j--)
		{
			for(int i=0;i<26;i++)
			{
			if(c1[i].num==j)
			cout<<c1[i].a<<" "<<c1[i].num<<endl;
			
			}
		}
}
```
* Type Convert
  * 13. TeX Quotes (CPE22131, UVA272)
 ```C++=
 #include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
	int n;
	bool flag=false;
	string tex;
	while(getline(cin,tex))
	{
		for(int i=0;i<tex.length();i++)
		{ 
			if(tex[i]==34&&flag==true)
				{
					cout<<"''";
					flag=false;
				}
			else if(tex[i]==34)
			{
				cout<<"``";
				flag=true;
				
			}
			
			else
				cout<<tex[i];
		}
		cout<<endl;
	}
	return 0;
}
```

* 練習題目

8. What's Cryptanalysis? (CPE10402, UVA10008)
9. Decode the Mad man (CPE10425, UVA10222)
參考解答
```C++=

```
11. Problem J: Summing Digits (CPE10473, UVA11332)
12. Common Permutation (CPE10567, UVA10252)
參考解答
```C++=
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	string a,b,x;
	int la,lb,ala[26],alb[26],lc;
	while(cin>>a>>b) {
		la = a.length();
		lb = b.length();
		for(int i=0; i<26; i++) ala[i]=alb[i]=0;
		for(int i=0; i<la; i++) ala[a[i]-'a']++;
		for(int i=0; i<lb; i++) alb[b[i]-'a']++;
		for(int i=0; i<26; i++) {
			lc = min(ala[i],alb[i]);
			if(lc!=0) 
				for(int j=0; j<lc; j++) cout<<(char)('a'+i);
		}
		cout<<endl;
	}
	return 0;
} 
```

13. Rotating Sentences (CPE21914, UVA490)
14. TeX Quotes (CPE22131, UVA272)

* Q & A

## 2020.10.20 CPE 測驗
1. Hartals (UVa10050, 答對人數 827/2180)
```C++=
#include <iostream>
using namespace std;

int main() {
	int n,d,p,pd[3650],ha,c,t;
	cin>>n; // #test data 
	for(int i=0; i<n; i++) {
		cin>>d; //#days
		for(int j=0; j<d; j++) pd[j]=0;
		cin>>p; // #parties
		for(int k=0; k<p; k++) {
		    cin>>ha;
		    for(int j=ha-1; j<d; j+=ha) pd[j]++; 
		}
		c=0;
		for(int j=0; j<d; j++) {
                    t=j%7;
                    if(t!=5 && t!=6 && pd[j]!=0) c++;
		}	
		cout<<c<<endl;
	}
	return 0;
}
```
2. The Decoder (UVa00458, 答對人數 980/2180)
```C++=
#include <string>
#include <iostream>
using namespace std;

int main() {
	string s;
	while(getline(cin,s)) {
		for(int i=0; i<s.length(); i++) s[i]-=7;
		cout<<s<<endl;		
	}
	return 0;
}
```
```C++=
#include<iostream>
using namespace std;
int main() {
	string a;
	while(cin>>a){
		for(int i=0;i<a.length();i++){
			a[i]=a[i]-7;
		}
		cout<<a<<endl;		
	}
	return 0;
}
//這題剛好可以用cin輸入 
```
3. Basically Speaking (UVa00389, 答對人數 391/2180)
```C++=
#include <string>
#include <iostream>
using namespace std;

int main() {
	string si,so;
	int bi,bo,t,i;
	char d[] = {'0','1','2','3','4','5','6','7',
	            '8','9','A','B','C','D','E','F'};
	while(cin>>si>>bi>>bo) {
		t=0;
		for(i=0; i<si.length(); i++) {
			if(si[i]>='0' && si[i]<='9') 
				t= t*bi+(si[i]-'0');
			else if(si[i]>='A' && si[i]<='F') 
				t= t*bi+(si[i]-'A'+10);
		}
		so = "      0";
		i=6;
		while(t>0 && i>=0) {
			so[i]=d[t%bo];
			t/= bo;
			i--;
		}
		if(t==0) cout<<so<<endl;
		else cout<<"  ERROR"<<endl;
	}
	return 0;
}
```
4. Graphical Editor (UVa10267, 答對人數 79/2180)
```C++=

```
5. Is It A Tree? (UVa00615, 答對人數 69/2180)
```C++=

```
6. String Theory (UVa01746, 答對人數 2/2180)
```C++=

```
7. Stamps (UVa00165, 答對人數 21/2180)
```C++=

```

## 04.  一顆星選集 – 數學計算

* 上課講解
Main topics
  * Calendar、Set、Probability、Arithmetic series、Geometric series
   (日曆 、集合、機率、等差級數、等比級數)
  * Area、Algebra、Polynomial、Simultaneous equations、Matrix、Basic physics
   面積、代數、多項式、聯立方程式、矩陣、基本物理

* Key Point
  * Understand the requirement, then design the method, finally write program.
(了解題意後，先想出解法再撰寫程式)

1. d097. UVa 10038 - Jolly Jumpers
參考程式
```C++=
#include <iostream>
using namespace std;

int main() {
	int i,n,flag,t,d[3001],num[3001];
	while(cin>>n) {
		cin>>num[0];
		for(i=1; i<n; i++) {
			cin>>num[i]; d[i]=0;
		}
		flag=1; //flag 0:Not Jolly, 1:Jolly
		i=1;
		while(flag==1 && i<n) {
			t=num[i]-num[i-1]; 
			if(t<0) t=-t;
			if(t>0 && t<n && d[t]==0) d[t]++;
			else flag=0;
			i++;
		}
		if(flag==1) cout<<"Jolly"<<endl;
		else cout<<"Not jolly"<<endl;
	}
	return 0;
} 
```
2. c022. UVa 10783 - Odd Sum
參考程式
```C++=
#include <iostream>
using namespace std;

int main() {
	int n,a,b,sum;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>a>>b;
		sum=0;
		if(a%2==0) a++;
		for(int j=a; j<=b; j+=2) sum+=j;
		cout<<"Case "<<i+1<<": "<<sum<<endl;
	}
		
	return 0;
}
```
3. d186. UVa 11461 - Square Numbers
參考程式
```C++=
#include <iostream>
using namespace std;

int main() {
	int a,b,i,cnt;
	while(cin>>a>>b && (a!=0||b!=0)) {
		cnt=0; i=1;
		while(i*i<a) i++;
		while(i*i<=b) {
			cnt++; i++;
		}
		cout<<cnt<<endl;
	}
			
	return 0;
}
```

```cpp=
#include <cmath>
#include <iostream>
using namespace std;

int main() {
	int a,b,cnt;
	while(cin>>a>>b && (a!=0||b!=0)) {
		cnt=floor(sqrt(b))-ceil(sqrt(a))+1;
		cout<<cnt<<endl;
	}
	return 0;
}
```

4. d226. UVa 10071 - Back to High School Physics
參考程式
```C++=
#include <iostream>
using namespace std;

int main() {
	int v,t;
	while(cin>>v>>t) {
		cout<<2*v*t<<endl;
	}
	return 0;
}
```

## 05.  一顆星選集 – 質數、因數、倍數

1. d387. UVa 10235 - Simply Emirp
1. d672. UVa 10922 - 2 the 9s
1. d255. UVa 11417 - GCD
1. a007. 判斷質數 (體驗:使用特別演算法)
採用費馬小定理(Miller-Rabin test)
需自行撰寫模指數運算
```Cpp=
#include <iostream>
using namespace std;
bool PrimeTest(long);
long long modexp(long long, long long, long long);

int main() {
    long aaa;
    while(cin >> aaa){
		if (PrimeTest(aaa)) cout<<"質數"<<endl;
		else cout<<"非質數"<<endl;
    }
    return 0;
}

bool PrimeTest(long a) {
	bool isPrime;
	long t,r[] = {2,3,5,7,11,13,17,19};
	int i;
	for(i=0; i<8; i++) {
		if(a==r[i]) return true;
		else if(a%r[i]==0) return false;
	}
	i=0; isPrime=true;
	while(isPrime && i<8) {
		t=modexp(r[i],a-1,a);
		if(t!=1) isPrime=false;
		i++;
	}
	return isPrime;
}

long long modexp(long long a, long long e, long long p) {
	long long c,d=0x40000000;
	c=1;
	while(d!=0) {
		c=(c*c)%p;
		if((d&e)!=0) c=(c*a)%p;
		d>>=1;
	} 
	return c;
}
```
5. d904. 換零錢 (體驗:動態程式規劃)
```cpp=
#include <iostream>
using namespace std;

int main() {
	int c,n,coin[10],mco[1001],t;
	cin>>c>>n;
	for(int i=0; i<n; i++) cin>>coin[i];
	for(int i=0; i<=c; i++) mco[i]=i;
	for(int i=0; i<n; i++) {
		for(int j=coin[i]; j<=c; j++) {
			t=mco[j-coin[i]]+1;
			if(t<mco[j]) mco[j]=t;
		}
	}	
	cout<<mco[c]<<endl;
	return 0;	
}
```

DP挑戰題
d133. UVa 00357 - Let Me Count The Ways
```cpp=
#include <iostream>
using namespace std;

int main() {
	int n,i;
	int coin[] = {1,5,10,25,50};
	long long mco[30001];
 	for(i=0; i<=30000; i++) mco[i]=1;
	for(i=1; i<=4; i++) {
		mco[coin[i]]++;
		for(int j=coin[i]+1; j<=30000; j++) {
			mco[j]+= mco[j-coin[i]];
		}
	}	
	while(cin>>n) {
		if(mco[n]==1)
			cout<<"There is only "<<mco[n]<<" way to produce "<<n<<" cents change.\n"; 
		else
			cout<<"There are "<<mco[n]<<" ways to produce "<<n<<" cents change.\n";
	}
	return 0;	
}
```

## 06. 一顆星選集 – 排序與中位數

 1. e512. UVa 10242 - Fourth Point!!
```C++=
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	double p[8],x,y;
	while(cin>>p[0]) {
		for(int i=1; i<8; i++) cin>>p[i];
		if(p[2]==p[4] && p[3]==p[5]) {
			x = p[0]+p[6]-p[2]; 
			y = p[1]+p[7]-p[3];
		}
		else if(p[2]==p[6] && p[3]==p[7]) {
			x = p[0]+p[4]-p[2]; 
			y = p[1]+p[5]-p[3];
		}
		else if(p[0]==p[4] && p[1]==p[5]) {
			x = p[2]+p[6]-p[0]; 
			y = p[3]+p[7]-p[1];
		}
		else if(p[0]==p[6] && p[1]==p[7]) {
			x = p[2]+p[4]-p[0]; 
			y = p[3]+p[5]-p[1];
		}
		cout<<fixed<<setprecision(3)<<x<<" "<<y<<endl; 		
	}	
	return 0;
}
```

 3. e606. UVa 10057 - A mid-summer nights dream
```C++=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n,cnt,pc,min,t,mid;
	long long sum;
	vector<int> x,y;
	while(cin>>n) {
		x.clear();  
		for(int i=0; i<n; i++) {
			cin>>t;
			x.push_back(t);
		}
		sort(x.begin(),x.end());
		mid = x[n/2];
		cnt = count(x.begin(),x.end(),mid);
		pc = 1;
		if(n%2==0 && mid!= x[n/2-1]) {
			pc = mid-x[n/2-1]+1;
			mid = x[n/2-1];	
			cnt+= count(x.begin(),x.end(),mid);
		}
		cout<<mid<<" "<<cnt<<" "<<pc<<endl;		
	}
	return 0;
}
```

 5. e561. UVa 00299 - Train Swapping
```C++=
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
	int tn,n,c,a[50];
	cin>>tn;
	for(int m=0; m<tn; m++) {
		while(cin>>n) {
			c=0;
			for(int i=0; i<n; i++) cin>>a[i];
			for(int i=1; i<n; i++) {
				for(int j=0; j<i; j++) 
					if(a[j]>a[i]) c++;
			} 
			cout<<"Optimal train swapping takes "<<c<<" swaps."<<endl; 
		}	
	}
	return 0;
}
```
