【题解】[BJOI2018] 双人猜数游戏

题目链接：[BJOI2018] 双人猜数游戏

题意：

提交答案题。
现有 $\text{Alice},\text{Bob}$ 两人，要猜出两个数字 $m,n\ (m\le n)$。一开始 $\text{Alice}$ 知道 $m\times n$，$\text{Bob}$ 知道 $m+n$，两人同时知道一个下界 $s$，即 $s\le m\le n$。
从 $\text{Alice}$ 或 $\text{Bob}$，交替回答现在自己是否已经知道了 $m,n$。要求是两人在说了总共 $t$ 次“不知道”之后，同时知道了 $m,n$。
给出 $s,t$ 和从谁开始，构造一组合法的 $m,n$，使得 $m+n$ 最小的情况下，$m$ 的值最小。
对于 $100\%$ 的数据，满足 $1\le s\le 200,\ 2\le t\le 15$，数据保证有解。

挺有意思的题。

首先需要意识到，之所以在说了若干次“不知道”之后，知道了 $m,n$ 的取值，是因为之前另一人所说的“不知道”能够减少可能的 $(m,n)$。

以 $\text{Alice}$ 开头为例，考虑一些简单的情形。以下不考虑两数之间的大小关系。

如果第一轮 $\text{Alice}$ 就知道了呢？说明满足 $a\times b=m\times n$ 且 $a,b\ge s$ 的方案是唯一的。

如果第二轮 $\text{Bob}$ 就知道了呢？$\text{Bob}$ 知道的是 $m+n$，在所有 $a+b=m+n$ 且 $a,b\ge s$ 的 $(a,b)$ 中，“合法”的数对方案唯一。

这里的合法，意思是这对数在这轮之前还不能被另一个人猜到。例如在第二局中，数对 $(a,b)$ “合法”就指“满足 $c\times d=a\times b$ 且 $c,d\ge s$ 的方案不唯一”。

如果我们简单地称 $\{(a,b)|a+b=m+n,\ a,b\ge s\}$ 为“和拆分”，$\{(a,b)|a\times b=m\times n,\ a,b\ge s\}$ 为“积拆分”，那么：

• 第 $1$ 轮 $\text{Alice}$ 没猜到 $\to$ 积拆分不唯一。
• 第 $2$ 轮 $\text{Bob}$ 没猜到 $\to$ 和拆分中“积拆分不唯一”的元素不唯一。
• 第 $3$ 轮 $\text{Alice}$ 没猜到 $\to$ 积拆分中“和拆分中‘积拆分不唯一’的元素不唯一”的元素不唯一。

以此类推。虽然这样写下去非常绕，但是我们容易从中观察出类似递归的形式。

于是，尝试使用递归函数的形式描述上面的文字。

我们称“已经完成 $t$ 轮后，下一个回答”的人称为 $p$，另一人称为 $q$。

设 $f(t,a,b)$ 表示说了 $\le t$ 轮“不知道”后，$p$ 是否已经能猜到 $a,b$。注意到一个人只有在另外一个人说完话之后才会得到新信息。

先判掉边界情况，$f(0,a,b)$ 就意味着和拆分 / 积拆分中元素唯一。

然后，如果当前这个人在 $t-2$ 局后就已经能猜出了，那么这一轮肯定也行。

接着，枚举积拆分 / 和拆分，判断有多少个元素在当前这轮“合法”。如果这样的元素唯一，那么 $p$ 就猜到了，否则就是暂时还猜不到。

于是，我们就可以使用 $f(t,a,b)$ 来初步判断在 $t$ 次“不知道”后，当前 $p$ 能否猜出 $a,b$ 了。

怎么判断 $(a,b)$ 满足“在恰好 $t$ 次‘不知道’后，两个人同时猜到了”呢？

首先，$f(t,a,b)$ 应为真：这能保证在第 $t$ 轮的时候 $p$ 能够猜到。

其次，$f(t-2,a,b),f(t-1,a,b)$ 均应为假：这保证要恰好第 $t$ 轮之后两人才可能猜到。

我们使用 $g(a,b)$ 表示上述三个条件是否同时满足。

容易想到还有一个条件：在 $p$ 说完“我知道了”之后，$q$ 应该立即也知道了。但是这不代表 $f(t+1,a,b)$ 为真，因为此时有人说出“我知道了”，与 $f$ 的定义情形不符。

于是需要特殊判断，这相当于和拆分 / 积拆分中，“$g(a,b)$ 为真”的元素唯一。

套上记忆化，暴力从小到大枚举 $m+n$，并从小到大枚举 $m$ 即可通过。跑的很快，所以这题是提交答案题是不是因为出题人没法证明答案上界啊。

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1

const int MAXN = 20;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, m, S, T, opt;
map<pii, bool> ok[MAXN];
string who;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

bool f(int t, int a, int b) { // 说了 t 次之后,下个人是否已经知道
    if(a > b) swap(a, b);
    if(ok[t].count(mp(a, b))) return ok[t][mp(a, b)];
    if(t >= 2 && f(t - 2, a, b)) return true;
    int cnt = 0, sum = a + b, prod = a * b;
    if(t == 0) {
        if(!opt) {
            for(int i = S; i * i <= prod; ++i)
                if(prod % i == 0 && prod / i >= S) ++cnt;
            return ok[t][mp(a, b)] = (cnt == 1);
        } else {
            for(int i = S; i <= (sum >> 1); ++i)
                if(sum - i >= S) ++cnt;
            return ok[t][mp(a, b)] = (cnt == 1);
        }
    }
    if(!((t & 1) ^ opt)) { // Alice
        for(int i = S; i * i <= prod; ++i)
            if(prod % i == 0 && prod / i >= S && !f(t - 1, i, prod / i)) ++cnt;
        return ok[t][mp(a, b)] = (cnt == 1);
    } else { // Bob
        for(int i = S; i <= (sum >> 1); ++i)
            if(sum - i >= S && !f(t - 1, i, sum - i)) ++cnt;
        return ok[t][mp(a, b)] = (cnt == 1);
    }
} 

bool valid(int a, int b) { return f(T, a, b) && (!f(T - 2, a, b)) && (!f(T - 1, a, b)); }

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(S); cin >> who; read(T); opt = (who == "Bob");
    for(int sum = (S << 1); ; ++sum) {
        for(int a = S, b, prod, cnt; a <= (sum >> 1); ++a) {
            b = sum - a; prod = a * b, cnt = 0;
            if(!valid(a, b)) continue;
            if((T & 1) ^ opt) { // Alice
                for(int i = S; i * i <= prod; ++i)
                    if(prod % i == 0 && prod / i >= S && valid(i, prod / i)) ++cnt;
                if(cnt != 1) continue;
            } else {
                for(int i = S; i <= (sum >> 1); ++i)
                    if(sum - i >= S && valid(i, sum - i)) ++cnt;
                if(cnt != 1) continue;
            }
            printf("%d %d\n", a, b);
            return 0;
        }
    }
    return 0;
}