---
# System prepended metadata

title: 交大GPE程式檢定2025.09.24題目+題解

---

# 交大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，除了我這次考的這場以外，另外兩場分別跟資工系直屬日、系抓撞期，學校真的很會挑時間耶～。



