列表

详情

NC24157. Pyramid

描述

Alice和Bob又要开始在棋盘上下棋了。
这次的棋盘为金字塔形，由行组成，其中第行有个单元格，把第行第个单元格记为。如图是一个的棋盘:
                   
游戏的规则如下：
        1.初始时在(1,1)处放置一颗棋子。Alice和Bob轮流移动它，Alice先移动。
        2.移动棋子的规则是:当棋子处于单元格时,有以下三种移动方式 
                ,如果。
                ,如果。
                ,如果。
        简而言之，每次移动可以选择水平向右、向右下、或者向左下移动到相邻的单元格，前提是不能超出棋盘的范围。
        3.如果轮到某玩家移动时棋子没办法按上面的规则再移动，也就是棋子已经处于单元格，那么这个玩家被判负，另一个玩家取得游戏胜利。
        4.为了使游戏更加有趣，在游戏开始前设定了一个禁着单元格(无法落子的单元格),任何一个玩家不能把棋子走到这个单元格。也就是说可以认为这个单元格不可进入。
Alice和Bob都觉得这个禁着单元格很重要。所以他们正在讨论以哪个单元格作为禁着单元格。
已知棋盘的大小和一些候选的单元格，假设Alice和Bob都选择最佳的游戏策略，你需要计算出以这些单元格中的每一个如果被选为禁着单元格谁将会取得游戏胜利。

输入描述

第一行两个整数--棋盘的大小和候选标记单元格的个数。
然后行，其中第行为两个整数--第个候选单元格。
保证任何一个候选单元格都既不为也不为。

输出描述

对于每个候选单元格输出一行：

输出"Alice"，如果选择该候选单元格作为禁着单元格Alice会获得游戏胜利。否则输出"Bob"。

示例1

输入: 

3 2
3 1
3 2

输出: 

Alice
Bob

说明:

以红色代表禁着单元格，两种情况如图所示：

如果选择(3,1)作为禁着单元格:
Alice可以选择把棋子从(1,1)走到(2,1).
如果Bob选择走到(2,2),Alice可以选择走到(3,3)，Bob无棋可走，Alice胜利。
如果Bob选择走到(3,2),Alice可以选择走到(3,3)，Bob无棋可走，Alice胜利。
所以Alice一定能取得胜利。
如果选择(3,2)作为禁着单元格:
如果Alice选择把棋子从(1,1)走到(2,1),Bob可以选择走到(3,1)，Alice无棋可走，Bob胜利。
如果Alice选择把棋子从(1,1)走到(2,2),Bob可以选择走到(3,3)，Alice无棋可走，Bob胜利。
所以Bob一定能取得胜利。

示例2

输入: 

631 1
589 72

输出: 

Bob

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 698ms, 内存消耗: 4536K, 提交时间: 2019-09-10 18:05:08 

#include <bits/stdc++.h>
#define A cout << "Alice\n";
#define B cout << "Bob\n";
using namespace std;

int n, q;

int main() {
    cin >> n >> q;
    for (int x, y, i = 1; i <= q; i++) {
        cin >> x >> y;
        if (n % 2 == 0) {
            if (x > 3 && x % 2 == 0 && y == 2) B
            else A
        } else {
            if ((x == 3 && y == 1) || (x > 3 && x % 2 == 1 && (y == 1 || y == 3))) A
            else B
        }
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 98ms, 内存消耗: 1528K, 提交时间: 2020-03-25 14:33:57 

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int main()
{
	long long n,T,x,y;
	cin>>n>>T;
	while(T--)
	{
		scanf("%lld %lld",&x,&y);
		long long f=(n-1)%2;
		if((n-x)%2==0&&(n-y)%2==0&&y<=3&&x!=y) f=!f;
		printf(f?"Alice\n":"Bob\n");
	}
	return 0;
}

上一题

© 2024 nowcoder.com