# 交大GPE程式檢定2025.09.24題目+題解
## 第一次考GPE的心得
原本想說多刷點Uva上的題目再報名，但是看到許晉瑞第一次考就破台（甚至只花了兩個小時，好電ww），我覺得好像可以先去考看看？於是就直接報名了這一場。考完之後才發現GPE好像都是搬Uva一模一樣的題目拿來考，也因為這樣，碰到有些比較老的Uva題目，它輸入輸出方式跟一般競程題目不太一樣，會給一些莫名其妙的字元來干擾我們正常cin>>東西進來，像是這次pE,pF的輸入輸出就特別繁瑣，我花了一堆時間處理這個問題，可能要特別注意一下這點。然後GPE的計分方式是每題100分，看你通過了幾個測資會有部分分數，滿分600分。我這次考試AC了pA,pB,pD，而pE,pF只拿到60,40分，最後總成績是400分，好像沒達到A+的門檻，所以應該還要再考下一次。
## 題目
### pA Sum of Consecutive Prime Numbers
Uva原題連結：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3651
#### 題意：
給定一個整數$n$，問有幾組連續的質數的和加起來剛好等於$n$？
#### 範圍：
$2 \leq n \leq 10^{4}$
#### 想法：
先計算出所有小於$10000$的質數，發現只有$1229$個，代表我們可以用簡單的兩層迴圈枚舉所有可能的連續質數和，並用map存它出現的次數，之後每一次詢問$n$都可以直接查表輸出。
#### 扣德：
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
vector<int>v;
for(int i=2;i<=10000;i++){
bool isPrime=true;
for(int j=2;j*j<=i;j++){
if(i%j==0){
isPrime=false;
break;
}
}
if(isPrime)v.push_back(i);
}
map<int,int>mp;
int arr[1300];
int idx=0;
for(auto x:v){
arr[idx]=x;
idx++;
}
for(int i=0;i<idx;i++){
int sum=arr[i];
mp[sum]++;
for(int j=i+1;j<idx;j++){
sum+=arr[j];
mp[sum]++;
}
}
int n;
while(cin>>n&&n){
cout<<mp[n]<<'\n';
}
}
```
---
### pB Children's Game
Uva原題連結：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1846
#### 題意：
給定$n$個整數，求這些整數怎樣排列才能夠形成最大的整數？
#### 範圍：
$n \leq 50$
#### 想法：
觀察發現對於兩個數字$a$,$b$，比較$ab$,$ba$的大小進行排序就對了，可以用內建的sort()，再自己寫cmp函式。考試的時候我是用long long來存數字，但不知道為什麼同樣的寫法傳到Uva不會過，底下的code是用string來實作。
備注：這邊說的$ab$不是$a*b$，若$a=45$,$b=123$，則$ab=45123$
#### 扣德：
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool cmp(string a,string b){
return a+b>b+a;
}
signed main(){
int n;
string arr[55];
while(cin>>n&&n){
for(int i=0;i<n;i++)cin>>arr[i];
sort(arr,arr+n,cmp);
for(int i=0;i<n;i++)cout<<arr[i];
cout<<'\n';
}
}
```
---
### pC Square root
Uva原題連結：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=964
#### 題意：
給一個整數$y$，求出$\sqrt{y}$？（題目保證答案也是整數）
#### 範圍：
$1 \leq y \leq 10^{1000}$
#### 想法：
由於題目給的$y$範圍非常大，必須要實作大數乘法，所以考試的時候我直接放棄這一題（我考試的時候不會大數...）。
#### 扣德:
```cpp=
#include <cstring>
#include <cstdio>
char buf[1111];
int tag[505], mul[505], tem[1111];
int lef[505], rig[505], mid[505];
void bs(int L)
{
for (int i = 0; i <= 500; ++ i)
lef[i] = rig[i] = 0;
int l = (L+1)>>1;
rig[l] = 1;
int ans = 0, small = 1, end = L;
while (small) {
for (int i = 0; i <= l; ++ i)
mid[i] = lef[i]+rig[i];
mid[0] ++;
for (int i = 0; i <= l; ++ i) {
mid[i+1] += mid[i]/1000;
mid[i] %= 1000;
}
for (int i = l; i >= 0; -- i) {
if (i && mid[i]%2)
mid[i-1] += 1000;
mid[i] >>= 1;
}
end = l;
while (end > 0 && !mid[end]) -- end;
for (int i = 0; i <= L; ++ i)
mul[i] = 0;
for (int i = 0; i <= end; ++ i)
for (int j = 0; j <= end; ++ j)
mul[i+j] += mid[i]*mid[j];
for (int i = 0; i <= L; ++ i) {
mul[i+1] += mul[i]/1000;
mul[i] %= 1000;
}
ans = 0;
for (int i = L; i >= 0; -- i)
if (mul[i] != tag[i]) {
ans = mul[i]-tag[i];
break;
}
if (ans > 0) {
for (int i = 0; i <= l; ++ i)
rig[i] = mid[i];
rig[0] --;
for (int i = 0; rig[i] < 0; ++ i) {
rig[i] += 1000;
rig[i+1] --;
}
}else {
for (int i = 0; i <= l; ++ i)
lef[i] = mid[i];
}
end = l;
while (end >= 0 && lef[end] == rig[end]) -- end;
small = (end >= 0 && lef[end] < rig[end]);
}
end = l;
while (end > 0 && !lef[end]) -- end;
printf("%d",lef[end --]);
while (end >= 0) printf("%03d",lef[end --]);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
while (n --) {
memset(tag, 0, sizeof(tag));
memset(tem, 0, sizeof(tem));
scanf("%s",buf);
int L = strlen(buf);
for (int i = L-1; i >= 0; -- i)
tem[i] = buf[L-1-i]-'0';
int save = 0;
for (int i = 0; i < L; i += 3)
tag[save ++] = tem[i]+tem[i+1]*10+tem[i+2]*100;
bs(save);
if (n) printf("\n");
}
return 0;
}
```
---
### pD Longest Common Subsequence
Uva原題連結：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1346
#### 題意：
給定兩個字串$s$,$t$，求兩者的最長共同子序列（經典DP題目）
#### 範圍：
$s.size()$,$t.size()$<$1000$
#### 想法：
定義dp[i][j]為結尾在s[i],t[j]的最長共同子字串，則$dp[i][j]=max(max(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]+ (s[i]==t[j])?1:0)$
#### 扣德：
```cpp=
#include<bits/stdc++.h>
#define MAX 1005
using namespace std;
int main(){
string s,t;
while(getline(cin,s)){
getline(cin,t);
int dp[MAX][MAX]={0};
s=" "+s;
t=" "+t;
for(int i=1;i<s.size();i++){
for(int j=1;j<t.size();j++){
int k=dp[i-1][j-1];
if(s[i]==t[j])k++;
dp[i][j]=max(max(dp[i-1][j],dp[i][j-1]),k);
}
}
cout<<dp[s.size()-1][t.size()-1]<<'\n';
}
}
```
---
### pE Show the Sequence
Uva原題連結：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=938
#### 題意：
每一輪都按照順序執行一次$[]$內的加法或乘法，輸出前$n$輪最後的計算結果。
#### 範圍：
$2\leq n\leq 50$
#### 想法：
這題的實作的難點是要怎麼把類似$[2*[1+[2+[1]]]]$這種東西正確的讀取進來，我是用遞迴的方式來實作，遇到新的左括號就開始遞迴。讀進來之後就用動態規劃的方式，從最小的的括號開始計算它前$n$輪的值，更大的括號可以用小括號的值計算出來。
另外，這題我考試的時候一直WA，只拿到60分，結果同樣的程式碼上傳到Uva卻AC了，蠻神奇的。
#### 扣德：
```cpp=
#include<bits/stdc++.h>
#define MAX 50005
#define int long long
using namespace std;
int arr[MAX];
char brr[MAX];
int idx1=0,idx2=0;
int cnt=0;
void dfs(){
cnt++;
cin>>arr[idx1];
idx1++;
cin>>brr[idx2];
if(brr[idx2]==']')return;
idx2++;
char x;cin>>x;
if(x=='[')dfs();
else return;
}
signed main(){
char c;
while(cin>>c){
idx1=0;idx2=0;cnt=0;
dfs();
for(int i=0;i<cnt-1;i++){char x;cin>>x;};
int k;cin>>k;
vector<int>v_new(k+1,0),v_old(k+1,0);
for(int i=0;i<=k;i++){
v_old[i]=arr[idx1-1];
}
for(int i=idx1-2;i>=0;i--){
if(brr[i]=='+'){
v_new[1]=arr[i];
for(int i=2;i<=k;i++){
v_new[i]=v_new[i-1]+v_old[i-1];
}
}else{
v_new[0]=arr[i];
for(int i=1;i<=k;i++){
v_new[i]=v_new[i-1]*v_old[i];
}
}
swap(v_new,v_old);
}
for(int i=1;i<=k;i++){
if(i==k)cout<<v_old[i];
else cout<<v_old[i]<<' ';
}
cout<<'\n';
}
}
```
---
### pF Set partition
Uva原題連結：我找不到...
#### 題意：
給長度為$n$的整數陣列$a$，求有幾種分組方式，可以將$a$的每個元素都分配到兩組，使得兩組的和相等。
#### 範圍：
$0< n \leq 30$,$0<a_i \leq 10^{12}$
#### 想法：
由於這題的$n$只有到$30$，我可以用int來表示集合，比方說6=(110)二進制，代表第一個數與第二個數一組，第三個數自己一組。枚舉出所有的集合，計算哪些集合符合兩組的和相等就可以了。考試的時候一直有bug沒找出來，蠻可惜的。
---
## 最後的小小抱怨
這學期前三場GPE分別是9/17,9/24,10/15，除了我這次考的這場以外，另外兩場分別跟資工系直屬日、系抓撞期，學校真的很會挑時間耶～。
Sign in with Wallet
Connect another wallet