Luogu

LOJ

分析

下面的 $n,m$ 和题面上是反的（因为我写完才发现这个问题所以就懒得改了）。

先复原一下样例一（$s=5,nm=60,n+m=16$）的游戏过程中双方的心理活动。

• Bob：$(n,m)$ 的可能情况有 $(5,11),(6,10),(7,9),(8,8)$，所以回答不知道。
• Alice：$(n,m)$ 的可能情况有 $(5,12),(6,10)$，两种情况 Bob 之前的回答都应该是不知道，无法排除任何一种，所以回答不知道。
• Bob：$(n,m)$ 的可能情况有 $(5,11),(6,10),(7,9),(8,8)$，但是对于 $(5,11),(7,9),(8,8)$ Alice 的可能情况只有一种，所以 Alice 应该回答知道，但是 Alice 回答的是不知道，所以 $n=6,m=10$，回答知道。
• Alice：$(n,m)$ 的可能情况有 $(5,12),(6,10)$，但是对于 $(5,12)$ Bob 应该回答不知道（因为对于 $n+m=17$ Bob 还有 $(7,10),(8,9)$ 无法排除掉），所以 $n=6,m=10$，回答知道。
• Alice和 Bob分别单独写出了正确的 $n$ 和 $m$ ，观众们觉得 Alice 和 Bob很厉害。

那么可以考虑 DP。设 $dp_{i,j,k}$ 表示回答了 $i$ 次不知道时能否确定 $n=j,m=k$。

考虑转移。首先会有 $dp_{i,j,k}\leftarrow dp_{i-2,j,k}$。其次，假设当前是 Alice（Bob 同理），那么枚举 $j\times k$ 的所有约数 $x$，如果只有一个 $dp_{i-1,x,j\times k/x}=0$ 且这个 $x=j$，那么可以确定 $j,k$。

考虑求答案。枚举 $n,m$，那么一对 $n,m$ 满足条件至少要有 $dp_{t,n,m}=1$ 且 $\forall k<t,dp_{k,n,m}=0$。其次还要保证另一个人在当前这个人回答知道后能够确定 $n,m$，做一次类似的转移即可。

DP 的上界可以自己调一调，事实上都不到 $500$，一个点在本地跑也不要几秒。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int L=500;

int s,t; char name[10];
int dp[20][L+10][L+10];

bool solveAlice(int t,int x,int y) {
    int l=x*y,ansc=0,ansx,ansy;
    for (int i=s;i*i<=l;++i) {
        if (l%i) continue;
        if (!t||!dp[t-1][i][l/i])
            ++ansc,ansx=i,ansy=l/i;
    }
    return ansc==1&&ansx==x&&ansy==y;
}
bool solveBob(int t,int x,int y) {
    int l=x+y,ansc=0,ansx,ansy;
    for (int i=s;i+i<=l;++i)
        if (!t||!dp[t-1][i][l-i])
            ++ansc,ansx=i,ansy=l-i;
    return ansc==1&&ansx==x&&ansy==y;
}
bool checkAlice(int t,int x,int y) {
    int l=x*y,ansc=0,ansx,ansy;
    for (int i=s;i*i<=l;++i) {
        if (l%i) continue;
        if (dp[t][i][l/i]&&(t<2||!dp[t-2][i][l/i]))
            ++ansc,ansx=i,ansy=l/i;
    }
    return ansc==1&&ansx==x&&ansy==y;
}
bool checkBob(int t,int x,int y) {
    int l=x+y,ansc=0,ansx,ansy;
    for (int i=s;i+i<=l;++i)
        if (dp[t][i][l-i]&&(t<2||!dp[t-2][i][l-i]))
            ++ansc,ansx=i,ansy=l-i;
    return ansc==1&&ansx==x&&ansy==y;
}

int main() {
    file(guess);
    s=read(); scanf("%s",name); t=read();
    for (int i=0,o=(name[0]=='A');i<=t;++i,o=!o)
        for (int j=1;j<=L;++j)
            for (int k=1;k<=L;++k) {
                if (i>=2) dp[i][j][k]=dp[i-2][j][k];
                if (o) dp[i][j][k]=solveAlice(i,j,k);
                else dp[i][j][k]=solveBob(i,j,k);
            }
    for (int l=s+s;;++l)
        for (int i=s;i+i<=l;++i) {
            int x=i,y=l-i;
            if (!dp[t][x][y]) continue;
            int flag=0;
            for (int j=0;j<t;++j)
                if (dp[j][x][y]) { flag=1; break; }
            if (flag) continue;
            if (t&1) {
                if (name[0]=='A') flag=checkAlice(t,x,y);
                else flag=checkBob(t,x,y);
            } else {
                if (name[0]=='A') flag=checkBob(t,x,y);
                else flag=checkAlice(t,x,y);
            }
            if (flag) { printf("%d %d\n",x,y); return 0; }
        }
    return 0;
}