# 程式能力檢定_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;
}
```
Sign in with Wallet
Connect another wallet