ZeroJudge 解題筆記：c093. 00608 - Counterfeit Dollar

作者：王一哲
日期：2026年2月28日


ZeroJudge 題目連結：c093. 00608 - Counterfeit Dollar

解題想法

這題的困難之處在於分析測量結果，詳情請參考下方程式碼之中的註解。我是用集合儲存硬幣資料，由於 Python 的集合可以直接取聯集 (union)、差集 (difference)，寫起來比較簡單。

Python 程式碼

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

T = int(input())  # T 組測資
for _ in range(T):
    """ 前置作業 """
    data = []  # 測試資料，內容為 [left, right, satatus]
    coins = set()  # 所有參與測試的硬幣
    status = dict()  # 硬幣狀態，內容為 name: [light possible, heavy possible]
    for _ in range(3):  # 讀取 3 次測試結果
        left, right, state = input().split()  # 左側硬幣，右側硬幣，右側狀態
        data.append([left, right, state])  # 資料加到 data
        for coin in left: coins.add(coin)  # 更新 coins
        for coin in right: coins.add(coin)
    for coin in coins:  # 更新 status，預設值為 [True, True]
        status[coin] = [True, True]
    """ 處理測試資料 """
    for left, right, state in data:  # 依序讀取測試資料
        if state == "even":  # 如果兩側平衡，左、右的硬幣都是真的
            for coin in left: status[coin] = [False, False]  # 更新 status，兩種狀態都是 False
            for coin in right: status[coin] = [False, False]
        elif state == "up":  # 如果右側較高，代表左側較重、右側較輕，假的硬幣一定在這些硬幣之中
            leri = set(left).union(set(right))  # 兩側硬幣的聯集
            for coin in coins.difference(leri):  # 沒有參與這次測試的硬幣都是真的
                status[coin] = [False, False]
            for coin in left: status[coin][0] = False  # 左側硬幣不可能比真的硬幣輕
            for coin in right: status[coin][1] = False  # 右側硬幣不可能比真的硬幣重
        else:  # 如果右側較低，代表左側較輕、右側較重，假的硬幣一定在這些硬幣之中
            leri = set(left).union(set(right))  # 兩側硬幣的聯集
            for coin in coins.difference(leri):  # 沒有參與這次測試的硬幣都是真的
                status[coin] = [False, False]
            for coin in left: status[coin][1] = False  # 左側硬幣不可能比真的硬幣重
            for coin in right: status[coin][0] = False  # 右側硬幣不可能比真的硬幣輕
    """ 結束測試，找答案 """
    fake, result = "", ""  # 假的硬幣名稱、狀態
    for coin, (light, heavy) in status.items():  # 依序讀取 status 的資料
        if light and not heavy:  # 如果這個硬幣可能比較輕、不可能比較重
            fake = coin  # 找到假的硬幣
            result = "light"  # 較輕
            break  # 中止迴圈
        if not light and heavy:  # 如果這個硬幣不可能比較輕、可能比較重
            fake = coin  # 找到假的硬幣
            result = "heavy"  # 較重
            break  # 中止迴圈
    print(f"{fake:s} is the counterfeit coin and it is {result:s}.")

C++ 程式碼

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <algorithm>  // for set_difference
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;  // t 組測資
    for(int i=0; i<t; i++) {
        /* 前置作業 */
        vector<vector<string>> data;  // 測試資料，內容為 [left, right, satatus]
        set<char> coins;  // 所有參與測試的硬幣
        map<char, vector<bool>> status;  // 硬幣狀態，內容為 name: [light possible, heavy possible]
        for(int j=0; j<3; j++) {  // 讀取 3 次測試結果
            string left, right, state;  // 左側硬幣，右側硬幣，右側狀態
            cin >> left >> right >> state;
            data.push_back({left, right, state});  // 資料加到 data
            for(char coin : left) coins.insert(coin);  // 更新 coins
            for(char coin : right) coins.insert(coin);  // 更新 coins
        }
        for(char coin : coins) {  // 更新 status，預設值為 [True, True]
            status[coin] = {true, true};
        }
        /* 處理測試資料 */
        for(auto d : data) {  // 依序讀取測試資料
            string left = d[0], right = d[1], state = d[2];
            if (state == "even") {  // 如果兩側平衡，左、右的硬幣都是真的
                for(char coin : left) status[coin] = {false, false};  // 更新 status，兩種狀態都是 False
                for(char coin : right) status[coin] = {false, false};
            } else if (state == "up") {  // 如果右側較高，代表左側較重、右側較輕，假的硬幣一定在這些硬幣之中
                for(char coin : coins) {  // 沒有參與這次測試的硬幣都是真的
                    if (left.find(coin) != string::npos) continue;  // 如果在 left 之中找到 coin，繼續找下一個
                    if (right.find(coin) != string::npos) continue;  // 如果在 right 之中找到 coin，繼續找下一個
                    status[coin] = {false, false};
                }
                for(char coin : left) status[coin][0] = false;  // 左側硬幣不可能比真的硬幣輕
                for(char coin : right) status[coin][1] = false;  // 右側硬幣不可能比真的硬幣重
            } else {  // 如果右側較低，代表左側較輕、右側較重，假的硬幣一定在這些硬幣之中
                for(char coin : coins) {  // 沒有參與這次測試的硬幣都是真的
                    if (left.find(coin) != string::npos) continue;  // 如果在 left 之中找到 coin，繼續找下一個
                    if (right.find(coin) != string::npos) continue;  // 如果在 right 之中找到 coin，繼續找下一個
                    status[coin] = {false, false};
                }
                for(char coin : left) status[coin][1] = false;  // 左側硬幣不可能比真的硬幣重
                for(char coin : right) status[coin][0] = false;  // 右側硬幣不可能比真的硬幣輕
            }
        }
        /* 結束測試，找答案 */
        char fake = 'Z'; string result = "";  // 假的硬幣名稱、狀態
        for(auto it : status) {  // 依序讀取 status 的資料
            char coin = it.first;
            bool light = it.second[0], heavy = it.second[1];
            if (light && !heavy) {  // 如果這個硬幣可能比較輕、不可能比較重
                fake = coin;  // 找到假的硬幣
                result = "light";  // 較輕
                break;  // 中止迴圈
            }
            if (!light && heavy) {  // 如果這個硬幣不可能比較輕、可能比較重
                fake = coin;  // 找到假的硬幣
                result = "heavy";  // 較重
                break;  // 中止迴圈
            }
        }
        cout << fake << " is the counterfeit coin and it is " << result << ".\n";
    }
    return 0;
}