開啟章節選單

1657 Game

題目連結

題目敘述

有一個傳說 XVIII 世紀的數學家們喜歡玩一個遊戲。遊戲由三位數學家參與，其中一位為遊戲主持人。

首先，主持人宣佈一個正整數 N。然後，他從 1 到 N 中選擇兩個不同整數 X 和 Y，並將它們的和告訴玩家 S，將它們的積告訴玩家 P。每位玩家都知道自己收到的是和還是積。

接著玩家按順序向主持人回報是否已經知道被選出的兩個數字：

  1. 玩家 S（知道和者）先報告。
  2. 玩家 P（知道積者）接著報告。
    如此輪流進行，共報告 M 次「我不知道這兩個數字」。

例如，一段對話可能如下：

  • 主持人：「令 N = 10。」
  • 主持人選擇兩個 1 到 10 的數字，並告知 S 它們的和，告知 P 它們的積。
  • 玩家 S：「我不知道這兩個數字。」
  • 玩家 P：「我不知道這兩個數字。」
  • 玩家 S：「我不知道這兩個數字。」
  • 玩家 P：「我不知道這兩個數字。」
  • 玩家 S：「哦，現在我知道了。你選的是 3 和 6。」

給定 N 和 M（玩家共說了 M 次「我不知道這兩個數字」），請找出所有可能被主持人選出的數對 (X, Y)。

輸入說明

多組測試資料。每組第一行包含兩個整數 N 和 M（2 ≤ N ≤ 200，0 ≤ M ≤ 100）。

輸出說明

對於每組測試資料，首先輸出可能的數對總數。
接著按任意順序列出所有可能的數對，每行一個，格式為 “X Y”。

解題思路

主持人會從 1 ~ N 裡挑出兩個數字 X, Y
滿足 1 ≤ i < j ≤ N 的數對 (i, j)，皆有可能是 X, Y
先建立兩個陣列

  • add[s]：紀錄和等於 s 的數對 (i, j) 有幾種可能
  • mul[p]：紀錄積等於 p 的數對 (i, j) 有幾種可能

如果 S 發現 add[s] == 1，或是 P 發現 mul[p] == 1，也就是只有一種可能
玩家就能判定該唯一可能數對 (i, j) ，就是主持人的 (X, Y)

當玩家 S 說「我不知道」時
那麼目前一定 add[s] ≥ 2，於是可以將所有 add[s] == 1 的數對 (i, j) 刪除
刪除的同時，也要將 p = i*j 的 mul[p] 刪除可能性
當玩家 P 說「我不知道」時，同理

所以 S 的不知道，可以過濾 P 猜測的數對
而 P 的不知道，可以過濾 S 猜測的數對

玩家每次「不知道」時，就是表達目前 s 或 p 可能的數對至少還有 2 個 另一位玩家則會排除不符合條件的數對

每次玩家 S 先回答，玩家 P 後回答 經過 m 次篩選後，所有 add[s] == 1 或是 mul[p] == 1 代表著說「我知道」的玩家手上
目前的 s 或 p 可能性為一種的數對，就是題目的答案

程式碼

#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<vector<int>> v(n+1, vector<int>(n+1)); // v[i][j] 用於紀錄數對 (i, j) 是否已被刪除
        // add[s] 記錄所有 i<j 且 i+j == s 的候選對數量
        // mul[p] 記錄所有 i<j 且 i*j == p 的候選對數量
        vector<int> add(2*n+10), mul(n*n+10);
        // 列舉所有可能的 (i,j) 對
        for (int i = 1; i+1 <= n; i++) for (int j = i+1; j <= n; j++) add[i+j]++, mul[i*j]++; // 和為 s 的組合數 +1，積為 p 的組合數 +1

        // 模擬 m 次「我不知道」的過濾過程
        // 每一次迴圈代表一輪玩家發言 (第 k 輪):
        for (int k = 0; k < m; k++) for (int i = 1; i+1 <= n; i++) for (int j = i+1; j <= n; j++)
            //  偶數輪 (k%2==0)：S 玩家（知道和）說不知道 → 刪除 add[s] == 1 的對
            //  奇數輪 (k%2==1)：P 玩家（知道積）說不知道 → 刪除 mul[p] == 1 的對
            if (!v[i][j] && ((!(k&1) && add[i+j] == 1) || (k&1 && mul[i*j] == 1))) {
                // 移除該數對，相關的 add 和 mul 各減 1
                add[i+j]--;
                mul[i*j]--;
                v[i][j] = 1; // 標記數對 (i,j) 已刪除
            }

        // 經過 m 次「不知道」後，下一輪就能「知道」的對就是答案
        vector<PII> ans;
        for (int i = 1; i+1 <= n; i++) for (int j = i+1; j <= n; j++)
            // 如果 m 是偶數，下一輪輪到 S 知道 → add[s] 必須剛好等於 1
            // 如果 m 是奇數，下一輪輪到 P 知道 → mul[p] 必須剛好等於 1
            if (!v[i][j] && ((!(m&1) && add[i+j] == 1) || (m&1 && mul[i*j] == 1))) ans.push_back({i, j});

        // 先印數對總數，再逐行印出所有 (X, Y)
        cout << ans.size() << '\n';
        for (auto &i : ans) cout << i.first << ' ' << i.second << '\n';
    }
}

練習題

Game解答