P9153 - Agnej - ZUFEOJ

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：0 通过：0

Jenga is a game of physical skill created by British board game designer and author Leslie Scott. Jenga is played with 54 wooden blocks. Players take turns removing one block from any layer below the highest completed one and placing it horizontally atop the tower, perpendicular to any blocks on which it is to rest. The game ends when any portion of the tower collapses, caused by either the removal of a block or its new placement.

Alice and Bob are playing Agnej, a Jenga-liked building blocks game. At the beginning, Alice build a block tower of

n + 1

layers. The blocks within each layer are oriented in the same direction, with their long sides touching, and are perpendicular to the ones in the layer immediately below. Each block is

m

times as long as it is wide, so there are exactly

m

positions to place blocks in each layer, numbered from

1

m

. Alice and Bob take turns removing one block from any layer except the top layer, and the removed block won't be placed back atop the tower. The player who causes the tower to collapse loses the game, while the other player wins.

For simplicity, we can assume that the blocks from layer

1

(from top to bottom) to layer

i - 1

are light enough for the blocks of layer

i

, and both Alice and Bob are careful enough when removing blocks. Therefore, the tower will collapse if and only if after a player removes a block of some layer

l

, there are no blocks on position

1

through position

⌈m2⌉\lceil \frac{m}{2} \rceil

in layer

l

, or there are no blocks on position

⌊m2⌋+1\lfloor \frac{m}{2} \rfloor + 1

through position

m

in layer

l

.

You are given the initial shape of the tower. Assume both Alice and Bob plays optimally and Alice plays first, please determine who will win the game.

The first line contains two integer

n

and

m

(

1≤n×m≤1051\le n, m\le 10^5, ~1\le n\times m\le 10^5

).
Then follows

n

lines. The

i

-th line contains a 0-1 string of length

m

, denoting the shape of layer

i + 1

(from top to bottom). The

j

-th bit of the string denotes whether there is a block at

j

-th position (0 denotes no while 1 denotes yes).
Please note that the top layer does not affect the answer, so it does not appear in input. The input just shows the shape from layer 2 to layer

n + 1

. You can assume the top layer is not empty.
It is guaranteed that the tower won't collapse before the game starts.

Print ``Alice'' if Alice will win the game, ``Bob'' otherwise (both without quotes).

Alice

牛客暑期多校10

9153: Agnej

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签