猜拳 題解|APCS 2020 年 1 月初級 第 1 題
簡潔題意
猜拳以 \(0\)(石頭)、\(2\)(剪刀)、\(5\)(布)表示:\(0\) 贏 \(2\)、\(2\) 贏 \(5\)、\(5\) 贏 \(0\)。哥哥第一輪出 \(F\),之後每一輪照兩條策略出拳:妹妹若連續兩輪出一樣的拳,哥哥下一輪就出「打敗那個拳」的拳;否則下一輪出「跟妹妹前一輪一樣」的拳。一分出勝負,遊戲立刻結束。
輸出哥哥每一輪出的拳(空格隔開),接著印 : Won at round k 或 : Lost at round k(在第 \(k\) 輪哥哥贏了或輸了);比完 \(N\) 輪都平手就印 : Drew at round N。(\(1 \le N \le 10\);出拳只會是 \(0\)、\(2\)、\(5\))
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(20\) 分):\(N = 1\)。
- 子題組 2(\(20\) 分):\(N = 2\) 且 \(y_1 \ne y_2\)。
- 子題組 3(\(60\) 分):無額外限制。
先拿下子題組 1(20 分):只有一輪,連迴圈都不用
\(N = 1\) 的時候整場比賽就一輪:哥哥出 \(F\)、妹妹出她唯一的拳,判一次勝負就結束了。這一段先把「勝負怎麼判」練起來,它也是完整解的核心零件。
判勝負最好的順序是先認平手:兩人出一樣的拳(f == y)就是平手。不平手的話,把哥哥「贏」的三種組合用 || 串起來(3.3):石頭贏剪刀、剪刀贏布、布贏石頭。不平手又沒贏,剩下的只能是輸——輸的三種組合不用再寫一遍,一個 else 收掉(3.5)。
輸出格式也在這裡就顧好:哥哥的拳後面先印一個空格,再接 : 結果。對照範例輸出 0 : Won at round 1——冒號前後都有空格。
#include <iostream>
using namespace std;
int main() {
int f, n, y;
cin >> f >> n >> y; // 子題組 1 保證 n = 1:妹妹只有一個拳
cout << f << " "; // 哥哥第一輪出的拳,後面接一個空格
if (f == y) {
cout << ": Drew at round 1" << endl;
} else if ((f == 0 && y == 2) || (f == 2 && y == 5) || (f == 5 && y == 0)) {
cout << ": Won at round 1" << endl;
} else {
cout << ": Lost at round 1" << endl;
}
return 0;
}
範例 1 剛好第一輪就分出勝負,可以直接拿它驗這一版。範例 2~4 會 WA 是正常的——它們要比很多輪。APCS 逐筆給分,這一版至少穩拿子題組 1 的 \(20\) 分(其他子題組裡第一輪就分出勝負的測資也會順便對)。
從 20 分到 100 分:一個變數就記得住妹妹上一輪的拳
\(N \le 10\),規模極小,照題意模擬就是正解。動手之前先想清楚:妹妹的拳要記住幾個?
哥哥決定下一輪要出什麼,看的是妹妹「這一輪」和「上一輪」的拳。「連續兩輪出一樣的拳」=「妹妹這一輪的拳,跟上一輪的拳相同」;「跟妹妹前一輪一樣」也只回頭看一輪。既然永遠只需要回頭一步,妹妹的拳就不必全部存起來:這一輪的拳剛讀進來、放在 y,另外拿一個變數 prev 記住上一輪那個就夠了——讀一個處理一個,邊讀邊算。
用一個 for 迴圈(4.3)跑每一輪,每輪做三件事:
- 印出哥哥這一輪的拳(後面固定接一個空格)。
- 判勝負:用上一段練好的判法。分出勝負就把
: 結果印完、return 0;直接結束程式——1.1 的return 0;不一定要寫在最後,執行到它,程式就在那裡結束,迴圈剩下的輪次都不會再跑。 - 走到這裡代表平手,比賽繼續,決定哥哥下一輪的拳。
第 3 步就是把兩條策略翻譯成程式,有兩個重點:
- 記住上一輪的變數,初值要挑一個「不可能出現的拳」。出拳只會是 \(0\)、\(2\)、\(5\),所以設 \(-1\):第一輪比對時
y == prev永遠不成立,自然走「模仿」那條規則——「第一輪沒有上一輪」這個特例就這樣消失了,不必另外寫條件。(千萬別設 \(0\),\(0\) 是合法的拳,那就變成常犯錯誤第 \(1\) 條了。) - 「打敗 \(x\) 的拳」用對照表寫:打敗石頭(\(0\))的是布(\(5\))、打敗剪刀(\(2\))的是石頭(\(0\))、打敗布(\(5\))的是剪刀(\(2\))。\(0\)、\(2\)、\(5\) 不是連續數字,別想用加減乘除去「算」,
if / else if / else三行對照最穩。
迴圈整個跑完都沒分出勝負,就印 : Drew at round N。完整程式(同一行的拳用空格隔開,cin >> 會自動跳過空白和換行,所以在迴圈裡一個一個讀就好):
#include <iostream>
using namespace std;
int main() {
int f, n;
cin >> f >> n;
int prev = -1; // 妹妹上一輪出的拳;-1 代表「還沒有上一輪」
for (int i = 1; i <= n; i++) {
int y;
cin >> y; // 讀妹妹這一輪的拳
cout << f << " "; // 哥哥這一輪出的拳(後面固定接一個空格)
if (f != y) {
// 分出勝負了:不是贏就是輸
bool win = (f == 0 && y == 2) || (f == 2 && y == 5) || (f == 5 && y == 0);
if (win) {
cout << ": Won at round " << i << endl;
} else {
cout << ": Lost at round " << i << endl;
}
return 0; // 遊戲結束,整個程式直接結束
}
// 走到這裡代表平手,決定哥哥下一輪的拳
if (y == prev) {
// 妹妹連續兩輪同拳:出打敗它的拳
if (y == 0) {
f = 5; // 打敗石頭的是布
} else if (y == 2) {
f = 0; // 打敗剪刀的是石頭
} else {
f = 2; // 打敗布的是剪刀
}
} else {
f = y; // 跟妹妹上一輪出一樣的
}
prev = y; // 這一輪妹妹的拳,下一輪就變成「上一輪」
}
cout << ": Drew at round " << n << endl;
return 0;
}
分出勝負就 return 0; 走人,後面沒讀完的拳不用管——評測不會因為你沒把輸入讀完而扣分。
拿範例 3 走一遍(\(F = 5\),妹妹出 5 5 0 0):第 \(1\) 輪 \(5\) 對 \(5\) 平手,只有一輪、只能模仿,下一輪出 \(y_1 = 5\);第 \(2\) 輪 \(5\) 對 \(5\) 平手,妹妹連兩輪出 \(5\),下一輪出打敗布的剪刀 \(2\);第 \(3\) 輪 \(2\) 對 \(0\),石頭贏剪刀,哥哥輸了——輸出 5 5 2 : Lost at round 3,跟範例一致。
檢查小技巧:比賽能進到第 \(i\) 輪,代表前面每一輪都平手——平手就是兩人出的拳一樣,所以哥哥印出來的拳除了最後一個,一定跟妹妹出的一模一樣(範例 4 兩串完全相同就是這麼來的)。你的輸出如果前段就跟妹妹的拳對不上,不用等評測就知道有 bug。
測過再交:範例缺了「中途獲勝」和「一輪就結束」
盤點四個範例:Won 只出現在第 \(1\) 輪、Lost 在第 \(2\)、\(3\) 輪、Drew 只有比滿 \(6\) 輪的——「比了幾輪之後哥哥贏」和「\(N = 1\)」的局面完全沒測到。構造測資的心法:想讓比賽多比幾輪,就讓妹妹一直出「哥哥即將出的拳」製造平手。自己補這四筆:
| 餵什麼 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
0/1/0 |
0 : Drew at round 1 |
\(N = 1\)(子題組 1)平手收場:Drew 也可能在第 \(1\) 輪 |
2/2/2 5 |
2 2 : Won at round 2 |
範例裡缺席的「中途獲勝」 |
0/2/0 0 |
0 0 : Drew at round 2 |
第一輪就平手、妹妹第一拳是 \(0\)——專堵常犯錯誤第 \(1\) 條 |
0/3/0 0 5 |
0 0 5 : Drew at round 3 |
「打敗」規則觸發之後比賽繼續的局面 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 第一輪就套「連續兩輪同拳」規則:把
prev初值設成 \(0\)——\(0\) 是合法的拳,只要第一輪平手、妹妹第一拳又剛好是 \(0\),第一輪就會被誤判成「連續兩輪同拳」,誤觸發「打敗」規則。四個範例都沒有這種局面——範例全過,交出去照樣掉分。自測表第 \(3\) 列專堵它:正確輸出是0 0 : Drew at round 2,這個錯會印成0 5 : Won at round 2。 - 分出勝負卻沒有立刻結束:把結果記下來、迴圈照樣跑完,後面的拳全印出去了。範例 1 當場抓到——正確是
0 : Won at round 1,這樣寫會印成0 2 5 0 : Won at round 1。用return 0;當場結束程式最省事。 - 「打敗」對照寫反(寫成「輸給 \(x\) 的拳」:\(0 \to 2\)、\(2 \to 5\)、\(5 \to 0\)):範例 3 當場抓到——會印
5 5 0 0 : Drew at round 4(正確是5 5 2 : Lost at round 3)。 - 平手忘了更新哥哥的拳(永遠出第一輪的 \(F\)):範例 3 當場抓到——會印
5 5 5 : Won at round 3。 - 只寫了「模仿」那條規則、忘了「連續兩輪同拳要出打敗它的拳」:症狀跟上一條一模一樣,範例 3 同樣印出
5 5 5 : Won at round 3——範例 3 就是專門在驗策略規則的,兩條規則都寫齊才過得了。 - 冒號跟拳黏在一起:輸出格式是最後一個拳後面有一個空格再接
:。印成0: Won at round 1的話,評測比對的是一串一串的文字——0:和0不是同一串,會 WA。照參考碼「每個拳後面固定印一個空格、分出勝負再印: 結果」就自然正確。