問題一覧 > 通常問題

No.1506 Unbalanced Pocky Game

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 175
作問者 : oliverx3 / テスター : nok0 👑 qand yuto1115
お気に入りにしたユーザー ProblemId : 6261 / 自分の提出
問題文最終更新日: 2021-05-14 11:30:36
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 295 (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ of length $N$ consisting of positive integers. The $i\ (1 \leq i \leq N)$-th element of the sequence is $A_i$.

Alice and Bob play a game with this sequence. The $2$ players take turns performing the following operation until $A$ becomes empty.

  • Let $k$ be the last element of the sequence. The player changes the last element to an integer at least $0$ and less than $k$. An element that becomes $0$ is removed from the sequence.

A player who cannot perform the operation on their turn loses.

Alice moves first. Assuming that both $2$ players play optimally, determine which player wins.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9\ (1 \leq i \leq N)$
  • All input values are integers.

Input

$N$
$A_1\ A_2\ \cdots\ A_N$

Output

Print Alice if Alice wins, and Bob if Bob wins.

Sample

Sample 1
Input
3
2 1 3
Output
Alice

The game may proceed, for example, as follows:

  • Alice changes the last element to $1$. Now $A=(2,\ 1,\ 1)$.
  • Bob changes the last element to $0$. Now $A=(2,\ 1)$.
  • Alice changes the last element to $0$. Now $A=(2)$.
  • Bob changes the last element to $1$. Now $A=(1)$.
  • Alice changes the last element to $0$. Now $A=()$.

In this case, Bob cannot perform any more operations, so Alice wins.

Sample 2
Input
3
1 2 1
Output
Bob

Sample 3
Input
6
3 1 4 1 5 9
Output
Alice

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