問題一覧 > 通常問題

No.2666 Decreasing Modulo Nim

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 72
作問者 : suisen / テスター : cureskol ygussany kaichou243
お気に入りにしたユーザー ProblemId : 10495 / 自分の提出
問題文最終更新日: 2024-02-29 19:05:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 420 (順位表) の他の問題:

Problem Statement

You are given a sequence of positive integers $A=(A_1,A_2,\ldots,A_n)$ of length $n$ and a positive integer $m$. In addition, a non-negative integer $x$ is initialized as $x = m - 1$.

Alice and Bob play a game using this sequence. Starting with Alice, they alternately perform the following operation.

  • Choose a pair of integers $(i,k)$ satisfying $1\leq k\leq A_i$ and $(k\bmod m) \leq x$, and update $A_i\gets A_i-k,\ x\gets (k\bmod m)$. Here, $a\bmod b$ denotes the remainder when $a$ is divided by $b$.

The player who becomes unable to perform the operation loses, and the other player wins.

Determine which player wins when both players play optimally to win.

Input

The input is given from Standard Input in the following format.

$n$ $m$
$A_1$ $A_2$ $\cdots$ $A_n$
  • All input values are integers.
  • $1\leq n\leq 2\times 10 ^ 5$
  • $1\leq m\leq 10 ^ 9$
  • $1\leq A_i\leq 10 ^ 9$

Output

If Alice wins, print Alice; if Bob wins, print Bob, on $1$ line, followed by a newline.

Sample

Sample 1
Input
3 2
1 2 3
Output
Bob

This input represents $n=3,\ m=2,\ A=(1,2,3)$.

An example of how the game may proceed is shown below. Note that this example does not necessarily represent optimal play by both players.

  1. For $A=(1,2,3),\ x=m-1=1$, Alice chooses $(i,k)=(3,1)$ and updates $A=(1,2,2),\ x=(1 \bmod 2)=1$.
  2. For $A=(1,2,2),\ x=1$, Bob chooses $(i,k)=(1,1)$ and updates $A=(0,2,2),\ x=(1 \bmod 2)=1$.
  3. For $A=(0,2,2),\ x=1$, Alice chooses $(i,k)=(3,2)$ and updates $A=(0,2,0),\ x=(2 \bmod 2)=0$.
  4. For $A=(0,2,0),\ x=0$, Bob chooses $(i,k)=(2,2)$ and updates $A=(0,0,0),\ x=(2 \bmod 2)=0$.
  5. For $A=(0,0,0),\ x=0$, Alice cannot perform the operation, so the winner in this case is Bob.

It can be proved that no matter what operations Alice performs, Bob can operate so that Bob wins. Therefore, in this case, Bob wins when both players play optimally.

Sample 2
Input
4 10
1 2 3 4
Output
Alice
Sample 3
Input
10 5
7 4 10 15 9 4 1 13 5 6
Output
Alice

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。