# 交大GPE程式檢定2025.10.29題目和題解
## 題目
### pA Power Crisis
Uva原題連結：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=87&mosmsg=Submission+received+with+ID+30765429
#### 題意：
給定一個整數$n$，從$1$開始每次往右走$m$步（超過回到1），走過的不會重複計算到，走過的標記起來，如果想要最後才走到13，最小的$m$是多少？
#### 範圍：
$13 \leq n \leq 100$
#### 想法：
枚舉從小到大所有$m$，用bool陣列紀錄哪些走過了，用$step$紀錄本輪走過多少次沒走過的點，走了$n-1$個點後看$visited[13]$有沒有走過
#### 扣德：

#include<bits/stdc++.h>
using namespace std;
int n;
bool can(int m){
    int cnt=1;
    int idx=1;
    vector<bool>visited(n+1,0);
    visited[1]=true;
    while(cnt<n-1){
        int step=0;
        while(step<m){
            idx++;
            idx=idx%n;
            if(!visited[idx]){
                step++;
            }
        }
        //cerr<<idx<<'\n';
        visited[idx]=true;
        cnt++;
    }
    if(!visited[13])return true;
    else return false;
}
int main(){
    while(cin>>n&&n){
        for(int m=1;m<n;m++){
            if(can(m)){
                cout<<m<<'\n';
                break;
            }
        }
    }
}

---
### pB Dungeon Master
Uva原題連結：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=473&mosmsg=Submission+received+with+ID+30765465
#### 題意：
給一個立體的地圖，問能不能從起點走到終點，可以的話最快走幾步會到？
#### 範圍：
$l,r,c \leq 30$
#### 想法：
用BFS來做，如果能走到就代表有路，根據BFS的性質也可以保證步數是最少的。
(麻煩實作題)
#### 扣德：

#include<bits/stdc++.h>
using namespace std;
int l,r,c;
bool inrange(int x,int y,int z){
    return x>=0&&x<l&&y>=0&&y<r&&z>=0&&z<c;
}
class spot{
public:
    int x,y,z,cnt;
};
int main(){
    while(cin>>l>>r>>c){
        int sl,sr,sc,el,er,ec;
        if(l==0&&r==0&&c==0)break;
        char dungeon[35][35][35];
        for(int i=0;i<l;i++){
            for(int j=0;j<r;j++){
                for(int k=0;k<c;k++){
                    cin>>dungeon[i][j][k];
                    if(dungeon[i][j][k]=='S'){
                        sl=i;
                        sr=j;
                        sc=k;
                    }else if(dungeon[i][j][k]=='E'){
                        el=i;
                        er=j;
                        ec=k;
                    }
                }
            }
        }
        //cerr<<sl<<' '<<sr<<' '<<sc<<'\n';
        int dir[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
        bool visited[35][35][35]={0};
        visited[sl][sr][sc]=true;
        queue<spot>q;
        q.push({sl,sr,sc,0});
        bool flag=false;
        while(q.size()>0){
            spot t=q.front();q.pop();
            if(t.x==el&&t.y==er&&t.z==ec){
                cout<<"Escaped in "<<t.cnt<<" minute(s).\n";
                //cerr<<t.x<<' '<<t.y<<' '<<t.z<<'\n';
                //cerr<<el<<' '<<er<<' '<<ec<<'\n';
                flag=true;
                break;
            }
            for(int i=0;i<6;i++){
                if(inrange(t.x+dir[i][0],t.y+dir[i][1],t.z+dir[i][2])){
                    if(!visited[t.x+dir[i][0]][t.y+dir[i][1]][t.z+dir[i][2]]){
                        if(dungeon[t.x+dir[i][0]][t.y+dir[i][1]][t.z+dir[i][2]]!='#'){
                            q.push({t.x+dir[i][0],t.y+dir[i][1],t.z+dir[i][2],t.cnt+1});
                            visited[t.x+dir[i][0]][t.y+dir[i][1]][t.z+dir[i][2]]=true;
                        }
                    }
                }
            }
        }
        if(!flag)cout<<"Trapped!\n";
    }
}

---

### pC Automated Judge Script
Uva原題連結：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1129&mosmsg=Submission+received+with+ID+30765671
#### 題意：
給正確的字串以及使用者輸出的字串，判斷是：
1. AC：完全一模一樣
2. PE：數字一模一樣，但其他地方有錯
3. WA：其他情形
#### 範圍：
$1 \leq 字串總數 \leq 99$
#### 想法：
先跑一遍看有沒有完全一樣，有地方不一樣的話就提取出純數字的字串，判斷這個字串有沒有一模一樣。
#### 扣德:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int round=1;
    while(cin>>n&&n){
        cin.ignore();
        string s[105];
        for(int i=0;i<n;i++)getline(cin,s[i]);
        int m;cin>>m;
        cin.ignore();
        string t[105];
        for(int i=0;i<m;i++)getline(cin,t[i]);
        
        bool flag=false;
        
        if(n!=m){
            flag=true;
        } else {
            for(int i=0;i<n;i++){
                if(s[i].size()!=t[i].size()){
                    flag=true;
                    break;
                }
                for(int j=0;j<s[i].size();j++){
                    if(s[i][j]!=t[i][j]){
                        flag=true;
                        goto here;
                    }
                }
            }
        }
        
        here:
        if(!flag){
            cout<<"Run #"<<round<<": Accepted\n";
            round++;
            continue;
        }else{
            bool out=false;
            vector<char>new_s,new_t;
            
            for(int i=0;i<n;i++){
                for(int j=0;j<s[i].size();j++){
                    if('0'<=s[i][j]&&s[i][j]<='9'){
                        new_s.push_back(s[i][j]);
                    }
                }
            }
            for(int i=0;i<m;i++){
                for(int j=0;j<t[i].size();j++){
                    if('0'<=t[i][j]&&t[i][j]<='9'){
                        new_t.push_back(t[i][j]);
                    }
                }
            }
            
            if(new_s.size()!=new_t.size()){
                out=true;
            }else{
                for(int j=0;j<new_s.size();j++){
                    if(new_s[j]!=new_t[j]){
                        out=true;
                        goto he;
                    }
                }
            }
            
            he:
            if(out){
                cout<<"Run #"<<round<<": Wrong Answer\n";
                round++;
                continue;
            }else{
                cout<<"Run #"<<round<<": Presentation Error\n";
                round++;
                continue;
            }
        }
    }
}