01 Game

AtCoder

IDarc151_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ squares called square $1$, square $2$, $\ldots$, square $N$, where square $i$ and square $i+1$ are adjacent for each $i = 1, 2, \ldots, N-1$. Initially, $M$ of the squares have $0$ or $1$ written on them. Specifically, for each $i = 1, 2, \ldots, M$, $Y_i$ is written on square $X_i$. The other $N-M$ squares have nothing written on them. Takahashi and Aoki will play a game against each other. The two will alternately act as follows, with Takahashi going first. * Choose a square with nothing written yet, and write $0$ or $1$ on that square. Here, it is forbidden to make two adjacent squares have the same digit written on them. The first player to be unable to act loses; the other player wins. Determine the winner when both players adopt the optimal strategy for their own victory. ## Constraints * $1 \leq N \leq 10^{18}$ * $0 \leq M \leq \min\lbrace N, 2 \times 10^5 \rbrace$ * $1 \leq X_1 \lt X_2 \lt \cdots \lt X_M \leq N$ * $Y_i \in \lbrace 0, 1\rbrace$ * $X_i + 1 = X_{i+1} \implies Y_i \neq Y_{i+1}$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$ [samples]

Samples

Input #1

7 2
2 0
4 1

Output #1

Takahashi

Here is one possible progression of the game.

1.  Takahashi writes $0$ on square $6$.
2.  Aoki writes $1$ on square $1$.
3.  Takahashi writes $1$ on square $7$.

Then, Aoki cannot write $0$ or $1$ on any square, so Takahashi wins.

Input #2

Output #2

Aoki

Since every square already has $0$ or $1$ written at the beginning, Takahashi, who goes first, cannot act, so Aoki wins.

Input #3

1000000000000000000 0

Output #3

Aoki

API Response (JSON)

{
  "problem": {
    "name": "01 Game",
    "description": {
      "content": "There are $N$ squares called square $1$, square $2$, $\\ldots$, square $N$, where square $i$ and square $i+1$ are adjacent for each $i = 1, 2, \\ldots, N-1$. Initially, $M$ of the squares have $0$ or $1",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc151_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ squares called square $1$, square $2$, $\\ldots$, square $N$, where square $i$ and square $i+1$ are adjacent for each $i = 1, 2, \\ldots, N-1$.\nInitially, $M$ of the squares have $0$ or $1...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments