Problem 4F. 剪纸游戏

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 4F. 剪纸游戏

时间限制:2s

空间限制:256MB

题目描述

Alice和Bob正在玩一个剪纸游戏:纸的大小可以用 \(r \times 2\) 大小的矩形来表示,两人轮流剪去这张纸的一个 \(1 \times 1\) 的矩形块,但是要求在剪的过程中纸不能被剪成多张;也就是说,如果 \((i,c)\) 这个正方形块被剪去了,那么下一步就不能剪去 \((i-1,3-c)\), \((i, 3-c)\), \((i+1, 3-c)\) 这三个正方形块;因为一旦剪去这三个正方形块中的一个,这张纸就会被”剪断“。

特别的,如果最后只剩下 \(1 \times 1\) 的矩形,那么也不能将其剪去。

现在给定一个初始被剪去 \(n\) 个小正方形的 \(r \times 2\) 的矩形,Alice 先手进行剪纸操作,如果到某个人无法进行剪纸操作,那么另外一个人获胜。假设Alice和Bob都是足够聪明的,请问最后谁会获得胜利?

输入格式

第一行包括两个整数 \(r, n\),分别代表矩形的行数和一开始被剪去的正方形块数量;

下面 \(n\) 行每行两个整数 \(r_i\), \(c_i\), 代表初始每个被剪去的正方形块的行号和列号。

数据保证一开始的矩形不会被剪断。

输出格式

输出一行字符串,如果最后 Alice 能获得胜利,则输出 "Alice";如果最后 Bob 能获得胜利,则输出 "Bob".

样例1

输入

3 1
1 2

输出

Alice

解释

如下图所示,一开始黄色位置的小正方形被剪去了;那么Alice只需要选择绿色位置的小正方形剪去,下一步Bob将会无法进行任何操作,Alice获得胜利。

image-20231027193535324.png

样例2

输入

12 4
5 1
7 2
8 2
10 1

输出

Alice

样例3

输入

1 1
1 1

输出

Bob

数据范围

对于 \(60\%\) 的数据,\(1 \le r \le 5\);

对于 \(100\%\) 的数据,\(1 \le r \le 500\), \(0 \le n \le r\),\(1 \le r_i \le r\),\(1 \le c_i \le 2\).

2023秋 悬赏令第四周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-10-29 18:30
结束于
2023-11-05 00:00
持续时间
149.5 小时
主持人
参赛人数
83