棒球遊戲 (APCS 2016-10 中級) 的題解
簡潔題意
九位球員固定依 \(1, 2, \ldots, 9, 1, 2, \ldots\) 的順序輪流打擊。輸入給的是每位球員各自的歷次打擊結果(第 \(i\) 行先給次數 \(a_i\),再給 \(a_i\) 個結果),要還原成實際發生的順序來模擬:1B、2B、3B 讓打者和壘上所有跑者各前進 \(1\)、\(2\)、\(3\) 個壘,HR 讓所有人回本壘,每回到本壘得 \(1\) 分;SO、FO、GO 出局數加 \(1\)、跑者不動;每累積 \(3\) 次出局就清空壘包。求第 \(b\) 次出局發生時的總得分(\(1 \le a_i \le 5\)、\(1 \le b \le 27\),紀錄保證至少有 \(b\) 次出局)。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(20\) 分):打擊結果只有
HR與SO。 - 子題組 2(\(20\) 分):安打只有
1B,且 \(b = 3\)。 - 子題組 3(\(20\) 分):\(b = 3\)。
- 子題組 4(\(40\) 分):無額外限制。
先把順序排對:第 \(t\) 次打擊是誰的第幾次?
輸入是「一人一行」,比賽卻是「一人一次輪著來」——這題的第一個關卡就是把兩者接起來。把全場的打擊從 \(0\) 開始編號,第 \(t\) 次打擊:
- 是第 \(t \bmod 9\) 位球員(\(0\) 起算)——每九次輪一圈;
- 是他的第 \(t / 9\) 次打擊(整數除法)——每輪一圈,每個人各多打了一次。
\(t \bmod 9\) 與 \(t / 9\) 是上冊 2.6 的餘數與整除;九行長度不一樣的紀錄,用巢狀 vector<vector<string>> 收(10.3),record[i][j] 就是第 \(i\) 位球員的第 \(j\) 次結果。接下來只要讓 \(t\) 從 \(0\) 開始一路數上去,每次查 record[t % 9][t / 9],數到第 \(b\) 次出局就停——題目保證 \(b\) 次出局一定會在紀錄用完之前發生,所以不用擔心查到不存在的紀錄。
不能一位球員的整行處理完再換下一位:範例 1 的第 1 位球員打了 \(5\) 次,但第 \(3\) 次出局在他第 \(2\) 次上場之前就發生了。
先拿下子題組 1(20 分):只有全壘打和三振
只有 HR 和 SO 時壘上永遠沒人:HR 就是打者自己回本壘得 \(1\) 分,SO 就是出局數加 \(1\),數到第 \(b\) 次就停。這一段的重點是上面那個順序:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<vector<string>> record(9); // record[i][j]:第 i 位球員的第 j 次結果
for (int i = 0; i < 9; i++) {
int a;
cin >> a;
record[i].resize(a);
for (int j = 0; j < a; j++) cin >> record[i][j];
}
int b;
cin >> b;
int outs = 0, score = 0;
for (int t = 0; ; t++) { // 第 t 次打擊:第 t%9 位球員的第 t/9 次
string result = record[t % 9][t / 9];
if (result == "HR") {
score++; // 子題組 1 保證壘上沒人:全壘打只有打者得分
} else { // SO
outs++;
if (outs == b) break; // 第 b 次出局:停
}
}
cout << score << '\n';
return 0;
}
兩個範例都有安打,這份程式交上去範例會 WA——這是正常的,逐筆給分之下子題組 1 的 \(20\) 分穩穩到手;想自己驗,用自測表的第 4 列。
從 20 分到 100 分:壘包用一排格子推
安打之後「打者和壘上每個人各前進 \(d\) 個壘」,用一個四格的陣列 base[0..3] 來記:base[1]、base[2]、base[3] 是一、二、三壘有沒有人(題目講「第幾壘」,照 6.3 從 \(1\) 用起),base[0] 是打者站的本壘。前進 \(d\) 個壘不用分一壘安打、二壘安打各寫一套——一格一格推 \(d\) 次就好:每推一次,三壘的人回本壘得分,二壘的人到三壘,一壘的人到二壘,本壘的打者到一壘。全壘打就是推 \(4\) 次,壘上所有人連打者都會回來。
出局時出局數加 \(1\),剛好湊滿 \(3\) 的倍數就把 base[1..3] 清空;加到 \(b\) 就停,後面的紀錄不看。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<vector<string>> record(9); // record[i][j]:第 i 位球員的第 j 次結果
for (int i = 0; i < 9; i++) {
int a;
cin >> a;
record[i].resize(a);
for (int j = 0; j < a; j++) cin >> record[i][j];
}
int b;
cin >> b;
bool base[4] = {false, false, false, false}; // base[1..3]:一、二、三壘有沒有人
int outs = 0, score = 0;
for (int t = 0; ; t++) { // 第 t 次打擊:第 t%9 位球員的第 t/9 次
string result = record[t % 9][t / 9];
if (result == "SO" || result == "FO" || result == "GO") {
outs++;
if (outs == b) break; // 第 b 次出局:停,後面不算
if (outs % 3 == 0) { // 三出局:清空壘包
base[1] = base[2] = base[3] = false;
}
} else {
int d; // 要前進幾個壘
if (result == "HR") d = 4;
else d = result[0] - '0'; // "1B" → 1、"2B" → 2、"3B" → 3
base[0] = true; // 打者站上本壘
for (int step = 0; step < d; step++) { // 一格一格推 d 次
if (base[3]) score++; // 三壘的人回本壘得分
base[3] = base[2];
base[2] = base[1];
base[1] = base[0];
base[0] = false;
}
}
}
cout << score << '\n';
return 0;
}
result[0] - '0' 是 8.2 的字元轉數字;全場最多 \(45\) 次打擊、每次最多推 \(4\) 格,運算量小到不用算。子題組 2、3 的 \(b = 3\) 不需要特別處理——跑到第 \(3\) 次出局自然就停了。
測過再交:兩個範例的 \(b\) 都是 \(3\) 的倍數
兩個範例用同一份紀錄,只差 \(b = 3\) 和 \(b = 6\)——都剛好停在半局結束。沒蓋到的:\(b\) 停在半局中間(後面的得分不能算)、滿壘全壘打、三壘安打把跑者送回來、以及九個人打擊次數不一樣時的順序。自己造的時候每人只給一、兩次紀錄,用「第 \(t\) 次是第 \(t \bmod 9\) 位的第 \(t / 9\) 次」在紙上排一遍就能算出答案。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 1B / 1 1B / 1 1B / 1 HR / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 |
4 |
滿壘全壘打:三位跑者加打者共 \(4\) 分,第 \(1\) 次出局就停 |
1 1B / 1 3B / 1 GO / 1 GO / 1 2B / 1 SO / 1 SO / 1 SO / 1 SO / 3 |
2 |
三壘安打把一壘跑者送回本壘、自己站三壘;兩出局後二壘安打再送他回來 |
1 1B / 1 SO / 1 SO / 1 SO / 1 1B / 1 3B / 1 SO / 1 SO / 1 SO / 4 |
1 |
三出局後壘包清空:第 1 位的跑者不能留到下半局被三壘安打送回來(不清空會印 2) |
1 HR / 1 SO / 1 HR / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 |
1 |
\(b = 1\) 停在半局中間:第 \(1\) 次出局之後的全壘打不算(子題組 1 版就能驗) |
2 1B HR / 2 1B SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 8 |
1 |
打擊次數不一樣:第 1、2 位的第二次要排在其他七人之後;一行一行處理會把兩支安打接在一起算成 2 |
五筆都親眼看過正確,這題就穩了。
常犯錯誤
- 一位球員的整行處理完再換下一位:範例 1 印
3、範例 2 印3。 - 三出局沒清空壘包:範例 2 印
8;自測表第 3 列印2。 - 把 \(b\) 湊成整局(\(b\) 不是 \(3\) 的倍數也算到半局結束):兩個範例都剛好過,自測表第 4 列印
2。 - 全壘打忘了打者自己也得分(只推 \(3\) 格、打者留在三壘):兩個範例都剛好過——他後來被別人的安打送回來了;自測表第 1 列印
3、第 4 列印0。 - 自己重排順序時用錯了長度(例如拿第 \(9\) 位的打擊次數當輪數):讀到不存在的紀錄,直接當掉。
- 第 \(b\) 次出局之後還繼續算到紀錄用完:範例 1、2 都印
9。