# APCS實作題2025年6月第2題：轉盤得分

> 日期：2025年6月26日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=q837)

<br />

## 題目

### 問題描述

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

每個回合，每個輪盤會基於上一個回合結束的狀態做轉動，然後計算當前狀態的得分：

1. 每個輪盤的轉動可以是正數（順時針）、負數（逆時針）或 0（不轉）。
2. 當所有輪盤都轉動完畢後，觀察它們對齊位置上的字元。
3. 對於每一個位置（從上到下的每一格），統計出現次數最多的字元，並將該字元的出現次數計入分數。
4. 每個回合的得分為這 $n$ 格的對齊統計加總。

最終總得分為所有回合的得分總和。

**範例**

一開始有三個輪盤：apcsie, taiwan, icpeda，三個輪盤的轉動距離分別是：1 0 -4

結果：
1. eapcsi ← apcsie 右轉 1
2. taiwan ← 不動
3. daicpe ← icpeda 左轉 4

分數計算：
1. 第一格: (e, t, d) 出現最多的字元出現 1 次
2. 第二格: (a, a, a) 出現最多的字元出現 3 次
3. 第三格: (p, i, i) 出現最多的字元出現 2 次
4. 第四格: (c, w, c) 出現最多的字元出現 2 次
5. 第五格: (s, a, p) 出現最多的字元出現 1 次
6. 第六格: (i, n, e) 出現最多的字元出現 1 次

這次轉動後的分數是 $10 = 1+3+2+2+1+1$
<br />

### 輸入格式

第一行為 m n k
接下來有 m 行長度為 n 的小寫字母字串
最後 k 行為長度 m 的整數陣列，表示轉動距離

其中
- $m, n, k \leq 30$
- $-100 \leq 轉動距離 \leq 100$

子題配分
- 60%： $m = 3$
- 40%：無額外限制

<br />

### 輸出格式

每個回合轉動後的分數總和
<br />

### 範例一：輸入

3 6 2
apcsie
taiwan
icpeda
1 0 -4
7 -3 2

### 範例一：正確輸出

17

### 範例二：輸入

4 3 3
abc
bab
cbc
abc
-1 -6 -6 -7
5 -3 4 0
-7 4 2 8

### 範例二：正確輸出

21

<br />

### 評分說明

<br /><br />

## Python 程式碼

### 寫法1，用串列切片模擬每次轉動後輪盤的狀態

使用時間約為 35 ms，記憶體約為 3.7 MB，通過測試。

from collections import defaultdict

m, n, k = map(int, input().split())  # m 個輪盤，n 格，k 回合
roulettes = [list(input()) for _ in range(m)]  # 讀取輪盤資料
score = 0  # 分數
for _ in range(k):  # 讀取 k 回合轉動格數
    rotates = list(map(int, input().split()))  # 轉動格數
    for i in range(m):  # 依序讀取輪盤與轉動格數
        rotate = rotates[i]
        if rotate > 0:  # 順時鐘方向轉，資料向後平移
            rotate %= n  # 對 n 取餘數
            roulettes[i] = roulettes[i][n-rotate:] + roulettes[i][:n-rotate]
        elif rotate < 0:  # 逆時鐘方向轉，資料向前平移
            rotate = -rotate  # 轉回正值
            rotate %= n  # 對 n 取餘數
            roulettes[i] = roulettes[i][rotate:] + roulettes[i][:rotate]
    for i in range(n):  # 讀取每一格的字母
        cnt = defaultdict(int)  # 計數器
        for roulette in roulettes:  # 讀取每一個輪盤
            cnt[roulette[i]] += 1
        score += max(cnt.values())  # 加上同一個字母出現次數最大值
print(score)

<br />

### 寫法2，記錄每次轉動後的起點位置

使用時間約為 38 ms，記憶體約為 3.7 MB，通過測試。

from collections import defaultdict

m, n, k = map(int, input().split())  # m 個輪盤，n 格，k 回合
roulettes = [list(input()) for _ in range(m)]  # 讀取輪盤資料
starts = [0]*m   # 輪盤的起點
score = 0  # 分數
for _ in range(k):  # 讀取 k 回合轉動格數
    for i, step in enumerate(map(int, input().split())):  # 轉動格數
        if step > 0:  # 順時鐘方向轉，資料向後平移
            starts[i] += n - step%n
        elif step < 0:  # 逆時鐘方向轉，資料向前平移
            step = -step  # 轉回正值
            starts[i] += step%n
    for i in range(n):  # 讀取每一格的字母
        cnt = defaultdict(int)  # 計數器
        for j, roulette in enumerate(roulettes):  # 讀取每一個輪盤
            cnt[roulette[(i+starts[j])%n]] += 1  # 索引值要加上起點位置再對 n 取餘數
        score += max(cnt.values())  # 加上同一個字母出現次數最大值
print(score)

<br /><br />

## C++ 程式碼

### 寫法1，用 rotate 模擬每次轉動後輪盤的狀態

這個寫法速度較慢，使用時間約為 12 ms，記憶體約為 352 MB，通過測試。

#include <iostream>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n, k; cin >> m >> n >> k;  // m 個輪盤，n 格，k 回合
    vector<string> roulettes (m);  // 輪盤資料
    for(int i=0; i<m; i++) cin >> roulettes[i];
    int score = 0;  // 分數
    for(int i=0; i<k; i++) {  // 讀取 k 回合轉動格數
        for(int j=0; j<m; j++) {  // 依序讀取輪盤與轉動格數
            int step; cin >> step;
            if (step > 0) {  // 順時鐘方向轉，資料向後平移
                step %= n;  // 對 n 取餘數
                int d = n - step;  // 起點平移的距離
                rotate(roulettes[j].begin(), roulettes[j].begin()+d, roulettes[j].end());
            } else if (step < 0) {  // 逆時鐘方向轉，資料向前平移
                step = -step;  // 轉回正值
                step %= n;  // 對 n 取餘數
                rotate(roulettes[j].begin(), roulettes[j].begin()+step, roulettes[j].end());
            }
        }
        for(int j=0; j<n; j++) {  // 讀取每一格的字母
            map<char, int> cnt;  // 計數器
            for(auto roulette : roulettes) {  // 讀取每一個輪盤
                cnt[roulette[j]]++;
            }
            int imax = 0;  // 出現次數最大值
            for(auto it : cnt) imax = max(imax, it.second);
            score += imax;  // 加上同一個字母出現次數最大值
        }
    }
    cout << score << "\n";
    return 0;
}

<br />

### 寫法2，記錄每次轉動後的起點位置

使用時間約為 5 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n, k; cin >> m >> n >> k;  // m 個輪盤，n 格，k 回合
    string roulettes[m];  // 輪盤資料
    for(int i=0; i<m; i++) cin >> roulettes[i];
    int starts[m] = {0}, score = 0;  // 輪盤的起點，分數
    for(int i=0; i<k; i++) {  // 讀取 k 回合轉動格數
        for(int j=0; j<m; j++) {  // 依序讀取輪盤與轉動格數
            int step; cin >> step;
            if (step > 0) {  // 順時鐘方向轉，資料向後平移
                starts[j] += n - step%n;
            } else if (step < 0) {  // 逆時鐘方向轉，資料向前平移
                step = -step;  // 轉回正值
                starts[j] += step%n;
            }
        }
        for(int j=0; j<n; j++) {  // 讀取每一格的字母
            map<char, int> cnt;  // 計數器
            for(int t=0; t<m; t++) {  // 讀取每一個輪盤
                cnt[roulettes[t][(j + starts[t]) % n]]++;
            }
            int imax = 0;  // 出現次數最大值
            for(auto it : cnt) imax = max(imax, it.second);
            score += imax;  // 加上同一個字母出現次數最大值
        }
    }
    cout << score << "\n";
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`C++`、`Python`