問題一覧 > 教育的問題

No.2538 2-adic Element Game

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : 👑 p-adic / テスター : ecottea hiro1729
お気に入りにしたユーザー ProblemId : 9580 / 自分の提出
問題文最終更新日: 2023-10-02 21:00:33
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 412 (順位表) の他の問題:

Problem Statement

First, we introduce some notation and terminology. For an integer sequence $a$ and each positive integer $i$ not exceeding its length, $a_i$ denotes the $i$-th component of $a$.

For each non-negative integer $m$ and integer $n$, the $2^m$ place of the $2$-adic expansion of $n$ means the following:

  • When $n \geq 0$, the $2^m$ place in the base-$2$ notation of $n$.
  • When $n < 0$, the $2^m$ place in the base-$2$ notation of the $2$'s complement obtained when $-n$ is written in base-$2$ notation with $\max \{m+1,-n\}$ digits, that is, of $2^{\max \{m+1,-n\}}+n$.

This is what the term denotes.

Here is an explanation for those unfamiliar with the base-$2$ notation of integers. (Click to open)

 

The $2^m$ place of the $2$-adic expansion of $n$ is the unique integer $d$ satisfying all of the following $2$ conditions:

  • $d$ is $0$ or $1$.
  • There exist integers $q, r$ satisfying $n = q 2^{m+1} + d2^m + r$ and $0 \leq r < 2^m$.

First, for example, let $n = 0$. The $2^m$ place of the $2$-adic expansion of $n$ is $\textcolor{red}{0}$ regardless of $m$. Indeed, $d = \textcolor{red}{0}$ satisfies condition 1, and in condition 2 we can choose $(q,r) = (0,0)$.

Next, for example, let $n = 2$. When $m = 1$, the $2^m$ place of the $2$-adic expansion of $n$ is $\textcolor{red}{1}$. Indeed, $d = \textcolor{red}{1}$ satisfies condition 1, and in condition 2 we can choose $(q,r) = (0,0)$. On the other hand, when $m \neq 1$, the $2^m$ place of the $2$-adic expansion of $n$ is $\textcolor{red}{0}$. Indeed, $d = \textcolor{red}{0}$ satisfies condition 1, and in condition 2 we can choose $(q,r) = (2^{-(m+1)}n,0)$ if $m = 0$, and $(q,r) = (0,2)$ if $m > 1$.

Finally, for example, let $n = -1$. In this case, the $2^m$ place of the $2$-adic expansion of $n$ is $\textcolor{red}{1}$. Indeed, $d = \textcolor{red}{1}$ satisfies condition 1, and in condition 2 we can choose $(q,r) = (-1,2^m-1)$.

Note that $n$ is sometimes extended beyond the integers to $2$-adic integers, in which case the range of $q$ is also extended to the $2$-adic integers.

 

For each non-negative integer $m$ and integer $n$, we say that $m$ is a $2$-adic element of $n$ if the $2^m$ place of the $2$-adic expansion of $n$ is $1$:

Here are examples of $2$-adic elements. (Click to open)

 

First, for example, let $n = 0$. In this case, $m$ can never be a $2$-adic element of $n$.

Next, for example, let $n = 2$. A necessary and sufficient condition for $m$ to be a $2$-adic element of $n$ is $m = 1$.

Finally, for example, let $n = -1$. In this case, $m$ is always a $2$-adic element of $n$.

 

You are given as input a positive integer $N$ and an integer sequence $A$ of length $N$.

$2$-adic Element Lover Bot is a bot that loves $2$-adic elements.

$2$-adic Element Lover Bot Lover Bot is a bot that loves $2$-adic Element Lover Bot. Of course, the two are different entities.

The "$2$-adic element game with initial value $A$", whose two players are $2$-adic Element Lover Bot and $2$-adic Element Lover Bot Lover Bot, is defined as follows:

  1. First, the integer sequence $a$ is set to $A$.
  2. Next, the two players, starting with $2$-adic Element Lover Bot, alternately perform the following operation for as long as they can:
    • Choose $1$ pair of a positive integer $i$ not exceeding $N$ and a non-negative integer $m$ that is a $2$-adic element of the value of $a_i$, and update $a$ by replacing the value of $a_i$ with $m$.
  3. When the above operation can no longer be performed, the player who could not perform it loses, that is, the other player wins.

When both players choose their moves optimally in the $2$-adic element game with initial value $A$, aiming for their own victory and avoiding the opponent's victory, determine whether the game is decided within a finite number of operations and, if it is, which player wins.

Input

The input is given from standard input in $2$ lines in the following format:

  • Line $1$ contains $N$.
  • Line $2$ contains the components of $A$, separated by half-width spaces.
$N$
$A_1$ $\cdots$ $A_N$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^5$.
  • For every positive integer $i$ not exceeding $N$, $A_i$ is an integer satisfying $-10^{18} \leq A_i \leq 10^{18}$.

Output

Output in $1$ line in the following format:

  • If the game is not decided within a finite number of operations, output 0.
  • If $2$-adic Element Lover Bot wins, output 1.
  • If $2$-adic Element Lover Bot Lover Bot wins, output 2.

End the output with a newline.

Sample

Sample 1
Input
1
0
Output
2

Initially, the integer sequence $a$ of length $N = 1$ is given as $A = (0)$. Since the only positive integer $i$ not exceeding $N$ is $1$, the choice of $i$ is omitted from this explanation.

Since $a_1 = 0$ has no $2$-adic elements, $2$-adic Element Lover Bot, who moves first, cannot perform the operation. Therefore, $2$-adic Element Lover Bot Lover Bot, who moves second, has a winning strategy.

Sample 2
Input
1
1
Output
1

Initially, the integer sequence $a$ of length $N = 1$ is given as $A = (1)$. Since the only positive integer $i$ not exceeding $N$ is $1$, the choice of $i$ is omitted from this explanation.

First, $2$-adic Element Lover Bot, who moves first, can choose the non-negative integer $0$, which is a $2$-adic element of $a_1 = 1$, and replace $a_1$ with $0$. This updates $a$ to $(0)$.

Then, since $a_1 = 0$ has no $2$-adic elements, $2$-adic Element Lover Bot Lover Bot, who moves second, cannot perform the operation. Therefore, $2$-adic Element Lover Bot has a winning strategy.

Sample 3
Input
1
2
Output
2

Initially, the integer sequence $a$ of length $N = 1$ is given as $A = (2)$. Since the only positive integer $i$ not exceeding $N$ is $1$, the choice of $i$ is omitted from this explanation.

First, since the only non-negative integer that is a $2$-adic element of $2$ is $1$, $2$-adic Element Lover Bot, who moves first, has no choice but to choose $1$ and replace $a_1$ with $1$. This updates $a$ to $(1)$.

$2$-adic Element Lover Bot Lover Bot, who moves second, can choose the non-negative integer $0$, which is a $2$-adic element of $a_1 = 1$, and replace $a_1$ with $0$. This updates $a$ to $(0)$.

Then, since $a_1 = 0$ has no $2$-adic elements, $2$-adic Element Lover Bot cannot perform any further operation. Therefore, $2$-adic Element Lover Bot Lover Bot has a winning strategy.

Sample 4
Input
1
-1

As shown here, negative integers may appear among the components of $A$.

Output
1

Initially, the integer sequence $a$ of length $N = 1$ is given as $A = (-1)$. Since the only positive integer $i$ not exceeding $N$ is $1$, the choice of $i$ is omitted from this explanation.

First, $2$-adic Element Lover Bot, who moves first, can choose the non-negative integer $0$, which is a $2$-adic element of $a_1 = -1$, and replace $a_1$ with $0$. This updates $a$ to $(0)$.

Then, since $a_1 = 0$ has no $2$-adic elements, $2$-adic Element Lover Bot Lover Bot, who moves second, cannot perform the operation. Therefore, $2$-adic Element Lover Bot has a winning strategy.

Sample 5
Input
2
1 1
Output
2

Initially, the integer sequence $a$ of length $N = 2$ is given as $A = (1,1)$. The positive integers $i$ not exceeding $N$ are the following $2$: $1,2$.

First, $2$-adic Element Lover Bot, who moves first, chooses $i$ from either $1$ or $2$.

 

First, consider the case where $2$-adic Element Lover Bot initially chooses $i = 1$. Since the only $2$-adic element of $a_1 = 1$ is $0$, $2$-adic Element Lover Bot has no choice but to choose $0$ and replace $a_1$ with $0$. This updates $a$ to $(0,1)$.

$2$-adic Element Lover Bot Lover Bot, who moves second, can choose $i = 2$ and the $2$-adic element $0$ of $a_2 = 1$, and replace $a_2$ with $0$. This updates $a$ to $(0,0)$.

Then, whichever of $1,2$ $2$-adic Element Lover Bot chooses as $i$, we have $a_i = 0$, and since $0$ has no $2$-adic elements, it cannot perform the operation. Therefore, in this case, $2$-adic Element Lover Bot Lover Bot wins.

 

Next, consider the case where $2$-adic Element Lover Bot initially chooses $i = 2$. Since the only $2$-adic element of $a_2 = 1$ is $0$, $2$-adic Element Lover Bot has no choice but to choose $0$ and replace $a_2$ with $0$. This updates $a$ to $(1,0)$.

$2$-adic Element Lover Bot Lover Bot, who moves second, can choose $i = 1$ and the $2$-adic element $0$ of $a_1 = 1$, and replace $a_1$ with $0$. This updates $a$ to $(0,0)$.

Then, whichever of $1,2$ $2$-adic Element Lover Bot chooses as $i$, we have $a_i = 0$, and since $0$ has no $2$-adic elements, it cannot perform the operation. Therefore, in this case as well, $2$-adic Element Lover Bot Lover Bot wins.

 

From the above,$2$-adic Element Lover Bot Lover Bot has a winning strategy.

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