# 2025/6 APCS 實作題

# 第一題 - 小心陷阱
:::info
https://zerojudge.tw/ShowProblem?problemid=q836
:::

## 題目
在一維數線上進行一場模擬遊戲。遊戲規 則如下：
初始位置為0。
初始生命值為k（1 ≤ k ≤ 20）。
當前生命值為v時，角色會往右跳v格，也就是從位置p移動到p + v。
每次移動後，如果落在x1或x2的倍數上，會損失生命值：
若落在x1的倍數，生命值減少y1。
若落在x2的倍數，生命值減少y2。
若同時是x1和x2的倍數，生命值總共減少y1 + y2。
當生命值小於等於 0 時，遊戲結束，輸出當前所在的位置。

## 輸入說明:
輸入第一行 $k$ 表示初始生命值
第二行有 $x1$ 與 $y1$
第三行有 $x2$ 與 $y2$
輸入範圍k：初始生命值，
1 ≤ k ≤ 20
x1、x2：兩個陷阱的倍數條件，
1 ≤ x1, x2 ≤ 10
y1、y2：對應陷阱的扣血值，
1 ≤ y1, y2 ≤ 20
子題
40% : $x1=3, x2=4, y1=y2=k$
60% : 無額外限制

## 輸出說明:
輸出遊戲結束所在的位置
## 解題絲路

'''
當前生命值為v時，角色會往右跳v格，也就是從位置p移動到p + v。
每次移動後，如果落在x1或x2的倍數上，會損失生命值：
若落在x1的倍數，生命值減少y1。
若落在x2的倍數，生命值減少y2。
若同時是x1和x2的倍數，生命值總共減少y1 + y2。
當生命值小於等於 0 時，遊戲結束，輸出當前所在的位置。
'''
#include <bits/stdc++.h>
#define io ios::sync_with_stdio;cin.tie(0);
using namespace std;

int main(){ io;
    int k;

    cin >> k;
    int x1,y1;
    cin >> x1>>y1;
    int x2,y2;
    cin >> x2>>y2;
    int tmp=k;

    int curr=0;

    while (k>0){
        if (tmp%x1==0 && tmp%x2==0){
            k-=y1;
            k-=y2;
        }else if (tmp%x2==0){
            k-=y2;
        }else if (tmp%x1==0){
            k-=y1;
        }
        curr=tmp;
        tmp+=k;
    }
    cout <<curr;
}

---
# 轉盤得分
2025/06 實作第二題
:::info
{%preview https://zerojudge.tw/ShowProblem?problemid=q837 %}
:::
# 題目
q837. 2. 轉盤得分 - 高中生程式解題系統

你有m個輪盤，每個輪盤上有n格，每格上寫有一個小寫英文字母（a~z）一場遊戲有k個回合。

每個輪盤的轉動可以是正數（順時針）、負數（逆時針）或 0（不轉）。

當所有輪盤都轉動完畢後，觀察它們
對齊位置上的字元。
對於每一個位置（從上到下的每一格），統計出現次數最多的字元，並將該字元的出現次數計 入分數。
每個回合的得分為這n格的對齊統計加總。
最終總得分為所有回合的得分總和。

> 範例
> 一開始有三個輪盤：apcsie, taiwan, icpeda，三個輪盤的轉動距離分別是：1 0 -4
> 結果：
> eapcsi ← apcsie 右轉 1
> taiwan ← 不動
> daicpe ← icpeda 左轉 4

分數計算：
第一格: (e, t, d) 出現最多的字元出現 1 次
第二格: (a, a, a) 出現最多的字元出現 3 次
第三格: (p, i, i) 出現最多的字元出現 2 次
第四格: (c, w, c) 出現最多的字元出現 2 次
第五格: (s, a, p) 出現最多的字元出現 1 次
第六格: (i, n, e) 出現最多的字元出現 1 次
這次轉動後的分數是 $10 = 1+3+2+2+1+1$

## 輸入說明:
m n k
m 個長度 n 度小寫字母字串
k 行長度 m 的整數陣列表示轉動距離
m, n, k <= 30
-100 <= 轉動距離 <= 100
子題:
60%: m = 3
40%: 無額外限制

## 輸出說明:
每個回合轉動後的分數總和

## 解題絲路
這種圓環旋轉，可以用rotate()來快速完成，但rotate只能左旋轉，如何實現右旋轉?
:::info
仔細觀察就可以發現左旋轉其實就是n-右旋轉步數
:::

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int main(){io;

    int m,n,k;
    cin >> m >> n >> k;

    vector<string> li(m);
    for (int i=0;i<m;++i)cin >> li[i];


    int ans=0;
    for (int i=0;i<k;++i){
        for (int j=0;j<m;++j){
            int mv;
            cin >> mv;
            
            int r;

            if (mv < 0) {
                r = abs(mv);
                r%=n;
                rotate(li[j].begin(), li[j].begin()+r, li[j].end());
            } else if (mv > 0) {
                r = n-(mv%n);
                rotate(li[j].begin(), li[j].begin()+r, li[j].end());
            }

        }
        for (int j=0; j<n; ++j) {
            array<int,26> cnt = {}; // 0 初始化
            for (auto &s : li) {
                cnt[s[j]-'a']++;
            }
            int mx = *max_element(cnt.begin(), cnt.end());
            ans += mx;
        }

    }

    cout << ans;
    return 0;
}

:::warning
需要注意題目有說旋轉步數會>n，所以要記得%=n，避免溢位
:::
## 解法2
二維陣列與deque的運用。
題目分兩步驟:
1. 旋轉
2. 計算得分

### 旋轉
其實就用deque把頭或尾取出，再放到對的地方就好

### 計算得分
用字典紀錄後再設mx不斷比大小

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0)
using namespace std;

void rotate(int n,deque<char>& q){
    if (n<0){
        n = abs(n);
        while (n != 0){ // 左轉(負數)
            char st = q.front();
            q.pop_front();
            q.push_back(st);
            n--;
        }
    }
    else{
        while (n != 0){
            char st = q.back();
            q.pop_back();
            q.push_front(st);
            n--;
        }
    }
}

int count(string& s){ // 尋找最多次字元出現幾次
    unordered_map<char,int> um;

    for (auto i:s){
        um[i]++;
    }
    int mx=0;
    for (auto p:um){
        mx = max(mx,p.second);
    }
    return mx;
};

int main(){io;
    int m=0,n=0,k=0,ans=0;

    cin >> m >>n>>k;
    vector<string> li(m);
    vector<vector<int>> move(k, vector<int>(m));// 宣告二維陣列的語法

    for (int i=0; i<m ;++i){
        cin >> li[i];
    }

    for (int x=0;x<k;++x){
        for (int y=0;y<m;++y){
            cin >> move[x][y];
        }
    }

    // 將 list資料寫進deque
    vector<deque<char>> Q(m); // queue<string>是錯誤的
    for (int a=0;a<m ;++a){
        for (auto i: li[a]){
            Q[a].push_back(i);
        }
    }
           
    int c=0,w=0;
    for (int x=0;x<k;++x){
        string s="";
        
        for (int y=0;y<m;++y){ // 執行旋轉的動作
            rotate(move[x][y],Q[y]);
        }

        for (w=0;w<n;++w){ // 計算此輪分數
            for (c=0;c<m;++c){
                s+=Q[c][w];
            }
            ans+=count(s);
            s = "";
        }
    }

    cout << ans ;
    return 0;
}

---

:::info
趁機宣傳一下我自己的個人網站跟Youtube頻道 !!

**[個人網站](https://hyc.eshachem.com/) | [Youtube頻道](https://www.youtube.com/@Hy.C)**
:::
@2025 Hy.C 陳毓
> Copyright ©Hy.C 陳毓 CC BY-NC-SA 4.0 | 禁止商業用途 | 轉載標記出處 | 改編作品必須在相同條款下分享。