题目理解

三个学生 A、B、C，每人额头有一个正整数 $(x,y,z)$，满足 $x+y=z$（或轮换）。
他们能看见别人的数字但看不见自己的。
教授按 A→B→C→A→B→C… 的顺序轮流提问「你知道自己的数字吗？」
前若干轮都回答「不知道」，直到第 $N$ 次提问时，被问者猜出了自己的数字 $M$。

已知 $N$ 和 $M$，求所有可能的 $(A,B,C)$ 三元组。

核心思路

1. 关键观察

• 三个数满足 $x+y=z$（或轮换），其中 $z$ 是最大数
• 总是最大数的人先猜出来
• 第 $N$ 次提问对应的人编号为 $k = ((N-1) \bmod 3) + 1$（A=1,B=2,C=3）
• 如果第 $N$ 次猜出的人是 $k$，且他的数字是 $M$，那么 $M$ 一定是三个数中最大的

2. 递归推理过程

设当前三个数为 $(x,y,z)$，当前轮到的人编号为 $t$（A=1,B=2,C=3）。

推理规则：

• 如果某个人看到另外两个数字相等，就能立刻猜出自己的数字（因为只能是和，不会是差）
• 否则，他需要模拟「如果自己的数是另外两个数的差」时，别人能否提前猜出
• 如果在假设情况下别人应该提前猜出但实际没有，就排除这种可能性，从而确定自己的数是和而不是差

代码解析

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int n, m, k, cnt, Out[3][10000], Ans, a, b, c;

// 核心递归函数：模拟推理过程
// (x,y,z): 当前三个数，t: 当前轮到的人(1:A,2:B,3:C)，sum: 已进行的轮次
int work(int x, int y, int z, int t, int sum) {
    if (sum > n)  // 超过N轮还没猜出，返回大数表示不可能
        return 100;
    
    if (t == 0)   // 轮次循环处理
        t = 3;
    
    if (y == z)   // 关键：看到另外两个数相等，立刻能猜出
        return t;
    
    // 递归模拟：假设自己的数是差，看别人能否提前猜出
    return work(y, z, abs(y - z), t - 1, sum + 1) + 1;
}

// 检查三元组(x,y,z)是否满足条件
void doit(int x, int y, int z) {
    // 根据当前轮到的人k，确定递归的起始位置
    if (k == 1)      // A猜出
        Ans = work(x, z, y, 1, 0);
    else if (k == 2) // B猜出  
        Ans = work(x, y, z, 2, 0);
    else             // C猜出
        Ans = work(x, z, y, 3, 0);
    
    // 如果推理轮次正好是N，保存解
    if (Ans == n) {
        cnt++;
        Out[a][cnt] = x;
        Out[b][cnt] = y;
        Out[c][cnt] = z;
    }
}

int main() {
    while (scanf("%d%d", &n, &m) && m != -1) {
        k = n % 3;  // 确定第N次轮到的人
        cnt = 0;
        
        // 设置输出顺序：保证输出按A,B,C排序
        if (k == 1)      // A猜出
            a = 0, b = 1, c = 2;
        else if (k == 2) // B猜出
            a = 1, b = 0, c = 2;  
        else             // C猜出
            a = 2, b = 0, c = 1;
        
        // 枚举所有可能的分解：M = i + (M-i)
        for (int i = 1; i < m; i++)
            doit(m, i, m - i);
        
        printf("%d\n", cnt);
        
        // 按A,B,C顺序输出所有解
        for (int i = 1; i <= cnt; i++)
            printf("%d %d %d\n", Out[0][i], Out[1][i], Out[2][i]);
    }
    return 0;
}

算法详解

1. 确定猜出者

k = n % 3;  // 1:A, 2:B, 0:C

因为提问顺序是固定的 A,B,C,A,B,C...，第 $N$ 次对应的人编号为 $(N-1) \bmod 3 + 1$。

2. 枚举可能的三元组

for (int i = 1; i < m; i++)
    doit(m, i, m - i);

由于猜出者 $k$ 的数字 $M$ 是最大值，所以另外两个数 $i$ 和 $M-i$ 满足 $i + (M-i) = M$。

3. 递归推理模拟

work(x, y, z, t, sum) 函数：

• 基础情况：如果看到 $y = z$，当前人 $t$ 立即猜出
• 递归情况：假设自己的数是差 $|y-z|$，模拟下一人的推理
• 返回值：如果能在第 sum 轮猜出，返回猜出者的编号

4. 输出排序

通过 a,b,c 变量控制输出顺序，确保按 A,B,C 排序：

• 如果 A 猜出：(m, i, m-i) 对应 (A,B,C)
• 如果 B 猜出：调整为 (i, m, m-i)
• 如果 C 猜出：调整为 (i, m-i, m)

示例分析

对于输入 5 8（第5次提问猜出数字8）：

• $k = 5 \% 3 = 2$，B猜出
• 枚举分解：8=1+7, 2+6, 3+5, 4+4, 5+3, 6+2, 7+1
• 对每个分解模拟推理过程，找到在第5轮B猜出的情况
• 输出3个解，按A的数字排序

算法复杂度

• 枚举分解：$O(M)$
• 递归深度：最多 $N$ 层
• 总复杂度：$O(M \times N)$，在数据范围内可接受

总结

这个解法通过：

1. 数学建模 将逻辑推理转化为递归模拟
2. 枚举分解 遍历所有可能的三元组
3. 递归验证 检查是否符合推理轮次
4. 输出控制 保证结果按指定顺序排列