本篇含cpe必考1星題庫中31~40題。
本篇篇幅較大，可點選左列索引，跳至想查看的題目。
31. uva #10193
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40//23
using namespace std;
//目標找公因數=>用輾轉相除法找gcd
int gcd(int a, int b)
{
if(b==0) return a;
return gcd(b, a%b);
}
int main(){
int n;
string s1, s2;
long long num1, num2;
while(cin>>n){
for(int i=0; i<n; i++)
{
cin>>s1>>s2;
num1 = 0;
num2 = 0;
//轉decimal
for(int j=0; j<s1.length(); j++)
{
num1 = num1*2+(s1[j]-'0');
}
for(int j=0; j<s2.length(); j++)
{
num2 = num2*2+(s2[j]-'0');
}
//輾轉相除法
int l = gcd(num1, num2);
if(l!=1)
cout<<"Pair #"<<i+1<<": All you need is love!"<<endl;
else
cout<<"Pair #"<<i+1<<": Love is not all you need!"<<endl;
}
}
}
32. uva #10190
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48//15
using namespace std;
int main(){
vector<int> v;
int n, m;
bool flag = true;
while(cin>>n>>m)
{
flag = true;
//m==1時，無法脫離迴圈
if(m==0 || n==0 || m==1 || n==1)
flag = false;
else
{
v.push_back(n);
while(n>1)
{
//無法整除
if(n%m!=0)
{
flag = false;
break;
}
n/=m;
v.push_back(n);
}
}
if(flag)
{
for(int i=0; i<v.size(); i++)
{
cout<<v[i];
if(i!=v.size()-1)
cout<<" ";
else
cout<<endl;
}
}
else
cout<<"Boring!"<<endl;
v.clear();
}
}
33. uva #10235
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56//13
using namespace std;
int main(){
int n;
bool flag;
while(cin>>n)
{
flag = false;
for(int i=2; i<=sqrt(n); i++)
{
if(n%i==0)
{
flag = true;
break;
}
}
// 0 和 1不是prime
if(flag || n<2)
{
cout<<n<<" is not prime."<<endl;
}
else
{
//reverse
int tmp = n, re = 0;
while(tmp!=0)
{
re = re*10 + tmp%10;
tmp/=10;
}
flag = false;
for(int i=2; i<=sqrt(re); i++)
{
if(re%i==0)
{
flag = true;
break;
}
}
//若reverse等於自己(非diffent prime)，不算emirp
if(!flag && re!=n)
cout<<n<<" is emirp."<<endl;
else
cout<<n<<" is prime."<<endl;
}
}
}
34. uva #10922
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38//17
using namespace std;
// 999999999999999999999 => 189 => 18 => 9
int main(){
string s;
int sum, cnt;
while(cin>>s)
{
if(s=="0")
break;
cnt = 0;
sum = 0;
for(int i=0; i<s.length(); i++)
sum+=s[i]-'0';
cnt++;
while(sum>=10)
{
int tmp = sum;
sum = 0;
while(tmp>0)
{
sum += tmp%10;
tmp/=10;
}
cnt++;
}
if(sum == 9)
cout<<s<<" is a multiple of 9 and has 9-degree "<<cnt<<"."<<endl;
else
cout<<s<<" is not a multiple of 9."<<endl;
}
}
35. uva #11417
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27//9
using namespace std;
int GCD(int i, int j)
{
if(j==0) return i;
return GCD(j, i%j);
}
int main(){
long long N, G;
while(cin>>N)
{
if(N==0) break;
G=0;
for(int i=1;i<N;i++)
for(int j=i+1;j<=N;j++)
{
G+=GCD(i,j);
}
cout<<G<<endl;
}
}
36. uva #10908
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using namespace std;
int main(){
char rect[100][100];
int t, m, n, q, ir, ic;
bool flag;
while(cin>>t){
for(int i=0; i<t; i++){
cin>>m>>n>>q;
for(int j=0; j<m; j++)
for(int k=0; k<n; k++)
cin>>rect[j][k];
cout<<m<<" "<<n<<" "<<q<<endl;
for(int j=0; j<q; j++)
{
cin>>ir>>ic;
char ch = rect[ir][ic];
int l=0; //與rc距離
while(ir-l>=0 && ic-l>=0 && ir+l<m && ic+l<n)
{
flag = true;
//加左
for(int k=ir-l; k<=ir+l; k++)
{
if(rect[k][ic-l]!=ch)
{
flag = false;
break;
}
}
//加右
for(int k=ir-l; k<=ir+l; k++)
{
if(rect[k][ic+l]!=ch)
{
flag = false;
break;
}
}
//加上
for(int k=ic-l; k<=ic+l; k++)
{
if(rect[ir-l][k]!=ch)
{
flag = false;
break;
}
}
//加下
for(int k=ic-l; k<=ic+l; k++)
{
if(rect[ir+l][k]!=ch)
{
flag = false;
break;
}
}
if(flag == false)
{
break;
}
l++;
}
cout<<2*(l-1)+1<<endl;
}
}
}
}
37. uva #10221
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44//38
//用double算!!!!!否則精度不夠
/*
Degrees (°), minutes (‘), seconds (“)
1° = 60′
1′ = 60〃
*/
//弧長 arc = 2 * PI * R * a / 360 (deg>180, a=360-deg; deg<180, a=deg)
//弦長 chord = 2*( R * cos((90 – a / 2)) / 180 * PI)(中垂線法)
using namespace std;
int main(){
double r = 6440.0;
double s, a;
string st;
double arc, chord;
while(cin>>s>>a>>st){
//一律換成degree
if(st == "deg")
{
if(a>180) a = 360 - a;
}
else
{
a/=60.0;
}
//arc
arc = (2.0*M_PI*(r+s))*(a/360.0);
//chord
//cos(弧度)
chord = (cos((90-a/2.0)/180.0*M_PI)*(r+s))*2;
//cout
cout<<fixed<<setprecision(6)<<arc<<" "<<chord<<endl;
}
}
38. uva #10642
- 題目連結
- 題目大意：
- 核心思路：
原想法 - 超時QQ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
//不夠右，往左上到底，才能往右一步
//左上到底仍不夠高，往右一步繼續
int main()
{
long long n, flag, cnt, sx, sy, dx, dy;
while(cin>>n)
{
for(int i=0; i<n; i++)
{
cin>>sx>>sy>>dx>>dy;
long long x=sx;
long long y=sy;
long long r=sy;
flag=0;
cnt=0;
while(true)
{
if(y==dy && x==dx)
{
break;
}
if(y>0)
{
x++;
y--;
}
else
{
r++;
x=0;
y=r;
}
cnt++;
}
cout<<"Case "<<i+1<<": "<<cnt<<endl;
}
}
}
找規律 - 較簡化版
1 |
|
39. uva #10242
- 題目連結
- 題目大意：
- 核心思路：
法一:向量加法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44//39
using namespace std;
//重疊者做(x2, y2);
//向量加法：(x1-x2, y1-y2)+(x3-x2, y3-y2)=(x4-x2, y4-y2)
int main(){
double tmp[8], x[3], y[3];
int index[2];
while(cin>>tmp[0]>>tmp[1]>>tmp[2]>>tmp[3]>>tmp[4]>>tmp[5]>>tmp[6]>>tmp[7]){
//找重複
for(int i=0; i<4; i++)
{
for(int j=i+1; j<4; j++)
{
if(tmp[i*2]==tmp[j*2] && tmp[i*2+1]==tmp[j*2+1])
{
index[0] = i;
index[1] = j;
x[1] = tmp[i*2];
y[1] = tmp[i*2+1];
}
}
}
int k=0;
for(int i=0; i<4; i++)
{
if(i!=index[0] && i!=index[1])
{
x[k]=tmp[i*2];
y[k]=tmp[i*2+1];
k++;
}
if(k==1)k++;
if(k==3) break;
}
//向量加法
double dx = (x[0]-x[1]+x[2]-x[1]);
double dy = (y[0]-y[1]+y[2]-y[1]);
cout<<fixed<<setprecision(3)<<x[1]+dx<<" "<<y[1]+dy<<endl;
}
}法二：「對角線頂點座標和要相同」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//20
using namespace std;
//題目將給定平行四邊形的相鄰兩邊的頂點座標，根據已知的頂點求第四個頂點的座標。
//分析：「對角線頂點座標和要相同」
int main()
{
double x1, x2, x3, x4, y1, y2, y3, y4;
double rx,ry;
while(cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4)
{
//找對角
double ax1, ay1, ax2, ay2, ox, oy;
if(x1==x3&&y1==y3)
{
ax1=x2;
ax2=x4;
ay1=y2;
ay2=y4;
ox=x1;
oy=y1;
}
else if(x1==x4&&y1==y4)
{
ax1=x2;
ax2=x3;
ay1=y2;
ay2=y3;
ox=x1;
oy=y1;
}
else if(x2==x4&&y2==y4)
{
ax1=x1;
ax2=x3;
ay1=y1;
ay2=y3;
ox=x2;
oy=y2;
}
else
{
ax1=x1;
ax2=x4;
ay1=y1;
ay2=y4;
ox=x3;
oy=y3;
}
rx=ax1+ax2-ox;
ry=ay1+ay2-oy;
cout<<fixed<<setprecision(3)<<rx<<" "<<ry<<endl;
}
}
40. uva #10057
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47//29
using namespace std;
//三答案：
//ans1輸入中最小的中位數(偶數個輸入有兩個中位數，挑小的)
//ans2輸入中有幾個中位數(值和中位數相同者)
//ans3所有整數中符合A者(即偶數個輸入，值介於兩中位數者;或奇數輸入，值為中位數者)
int main(){
int n, mid;
int ans1, ans2, ans3;
while(cin>>n){
int *x = new int[n];
for(int i=0; i<n; i++)
cin>>x[i];
//sort
sort(x+0, x+n);
mid = n/2;
if(n%2==1)
{
ans1 = x[mid];
ans3 = 1;
ans2 = 0;
for(int j=0; j<n; j++)
{
if(x[j]==x[mid])
ans2++;
}
cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
}
else
{
ans1 = x[mid-1];
ans3 = x[mid]-x[mid-1]+1;
ans2 = 0;
for(int j=0; j<n; j++)
{
if(x[j] == x[mid-1] || x[j]==x[mid])
ans2++;
}
cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
}
delete [] x;
}
}