NC213991. SplitGame
描述
Alice and Bob like to cut paper, but they only have one piece of new paper. Both of them want to use this one, but no one wants to split the new paper. Therefore, Alice and Bob decide to fight...in a game.
Alice find an old rectangular paper that consists of N*M grids. Two players take turns and Alice goes first. In each round of action, the player chooses a piece of paper and splits it horizontally or vertically along the grid line. If one player splits out a piece of paper with a single grid, he or she will lose the game. Alice and Bob are smart, and both of them want to win the game. Now you know the size of paper, please predict who will win.
输入描述
Each line contains two integer numbers N and M, Process to end of file. (1<=N, M<=150, N*M>1)
输出描述
For each case, output the name of the winner.
示例1
输入:
1 2 1 6 4 3 3 5
输出:
Bob Alice Alice Bob
说明:
In test case 1: No matter how Alice operates, she will cut out a 1*1 piece of paper.
In test case 2: Alice split the paper along the vertical line between grid (1,3) and grid (1,4) at her first turn.
In test case 3: At first, Alice split the paper along the horizontal line between grid (2,1) and grid (3,1), then there are two 2*3 papers. Then Alice can copy Bob's actions.
In test case 4: Alice can’t win.
The number of test cases is no more than 22499.
C++(g++ 7.5.0) 解法, 执行用时: 69ms, 内存消耗: 716K, 提交时间: 2022-09-22 17:36:43
#include <iostream>
using namespace std;
const int kN = 151;
int a[kN][kN], n, m, p;
int C(int i, int j) {
if (~a[i][j]) {
return a[i][j];
}
int v[kN] = {0};
for (int k = 1; k < i; k++) {
if ((k != 1 && i - k != 1) || j != 1) {
v[C(k, j) ^ C(i - k, j)] = 1;
}
}
for (int k = 1; k < j; k++) {
if ((k != 1 && j - k != 1) || i != 1) {
v[C(i, k) ^ C(i, j - k)] = 1;
}
}
for (a[i][j] = 0; v[a[i][j]]; a[i][j]++) {
}
return a[i][j];
}
int main() {
fill(a[0], a[kN], -1);
while (cin >> n >> m) {
cout << (C(n, m) ? "Alice\n" : "Bob\n");
}
return 0;
}
C++ 解法, 执行用时: 120ms, 内存消耗: 632K, 提交时间: 2022-06-28 16:58:16
#include<bits/stdc++.h>
using namespace std;
int dp[155][155];
int sg(int n,int m)
{
if(dp[n][m]!=-1) return dp[n][m];
set<int>a;
for(int i=1;i<n;i++)
if(n-i+m>2&&i+m>2)
{
a.insert(sg(n-i,m)^sg(i,m));
}
for(int i=1;i<m;i++)
if(n+m-i>2&&n+i>2)
{
a.insert(sg(n,m-i)^sg(n,i));
}
for(int i=0;;i++)
if(!a.count(i)) return dp[n][m]=i;
}
int main()
{
memset(dp,-1,sizeof(dp));
dp[1][2]=dp[2][1]=dp[1][3]=dp[3][1]=0;
int n,m;
while(cin>>n>>m)
{
sg(n,m);
if(dp[n][m]) cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
}
return 0;
}