#P1488. Fat Cat's Triangular Game

    ID: 14774 Type: Default 1000ms 256MiB

Fat Cat's Triangular Game

Fat Cat's Triangular Game

Wildcat and Fatty (nicknamed Fat Cat) are math prodigies in their class. One day, Wildcat discovered an interesting geometric game and showed it to Fatty. The game is played on a convex polygon with $n$ vertices. In any triangulation of such a polygon, the $n-3$ diagonals partition the polygon into $n-2$ triangles. One of these triangles is painted black while all the others remain white.

The two players take turns. When it is a player's turn, he must remove one triangle that is cut off from the polygon along one of the drawn diagonals. A triangle can only be removed if it is a leaf triangle (i.e. it shares exactly one diagonal with the rest of the polygon). The player who removes the black triangle wins immediately.

In this problem, we assume that the polygon is triangulated in a canonical way by drawing all the diagonals from vertex $1$ (a fan triangulation). As a result, the triangles are arranged in a linear chain (or path) in the dual graph. They are numbered from $1$ to $n-2$ in order. In this arrangement, the two end triangles (triangle $1$ and triangle $n-2$) are immediately removable. If the black triangle is one of these endpoints, then the first player (Wildcat) can win immediately by removing it. Otherwise, let the black triangle be at position $p$ where $2\le p\le n-3$. In the chain the triangles to the left of the black one number $L=p-1$ and those to the right number $R=n-2-p$. Players remove one triangle from one of the ends (thereby reducing $L$ or $R$ by $1$) until the black triangle becomes a leaf. However, a player will avoid making a move that makes one of these counts zero on his own turn because if he does so, his opponent will then remove the black triangle and win.

It turns out that the outcome in the non‐trivial case (where the black triangle is not at an end) depends on the relative sizes of $L$ and $R$. Specifically, the first player has a winning strategy if and only if $L\neq R$. In summary, given $n$ and $p$ (the index of the black triangle in the canonical fan triangulation), Wildcat (the first player) can force a win if either:

  • $p=1$ or $p=n-2$ (i.e. the black triangle is at an end), or
  • $p\neq1$ and $p\neq n-2$ and $p-1\neq (n-2)-p$ (i.e. the two arms of the chain are of different lengths).

Your task is to determine whether Wildcat has a winning strategy.

Note: $n\ge 3$ and $p$ is an integer satisfying $1\le p\le n-2$.

inputFormat

The input consists of two space‐separated integers:

  • The first integer is $n$, the number of vertices of the convex polygon ($n \ge 3$).
  • The second integer is $p$, the index of the black triangle in the canonical fan triangulation (with triangles numbered from $1$ to $n-2$).

You may assume that $1 \le p \le n-2$.

outputFormat

Output a single line containing Yes if Wildcat (the first player) has a winning strategy, or No otherwise.

sample

3 1
Yes