問題一覧 > 通常問題

No.1613 Rush and Remove

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 65
作問者 : ygussany / テスター : tatyam chocorusk
お気に入りにしたユーザー ProblemId : 6520 / 自分の提出
問題文最終更新日: 2021-07-22 01:44:26
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 305 (順位表) の他の問題:

Problem Statement

R.R. loves games and came up with the following game.

  • It is a game for $2$ players, who take turns alternately. A player who cannot perform an operation on their turn loses, and the other player wins.
  • The board is an $H \times W$ grid, and the cell at the $i$-th $(1 \le i \le H)$ row from the top and the $j$-th $(1 \le j \le W)$ column from the left is denoted by $(i, j)$.
  • Each cell either has exactly $1$ piece on it or has no piece on it.
  • The player whose turn it is performs the following sequence of operations exactly $1$ time.
    • Choose $1$ cell $(i, j)$ $(1 \le i \le H,~1 \le j \le W)$ that has a piece on it.
    • Choose $1$ positive integer $i^*$ less than or equal to $i$ such that not even $1$ piece is placed on the cells $(i^*, j), (i^* + 1, j), \dots, (i - 1, j)$.
    • Remove the piece from cell $(i, j)$, and place $1$ piece each on the cells $(i^*, j), (i^* + 1, j), \dots, (i - 1, j)$.

Given the initial board of the game, determine which of the first player and the second player wins when the $2$ players both play optimally to win.

Input

$H$ $W$
$B_{1}$
$B_{2}$
 $\vdots$
$B_{H}$

  • $1 \le H, W \le 300$
  • $B_{i} \ (1 \le i \le H)$ is a string of length $W$ consisting of o and ..
  • If the $j$-th character from the left of $B_{i}$ is o, a piece is placed on cell $(i, j)$ in the initial board; otherwise, no piece is placed there.

Output

Print First if the first player wins when both players play optimally, and Second if the second player wins.

Sample

Sample 1
Input
4 1
.
.
o
.
Output
First

The operations available to the first player are $(i, i^*) = (3, 1), (3, 2), (3, 3)$. In every case, the piece is removed from cell $(3, 1)$, and

  • if $(i, i^*) = (3, 1)$, pieces are placed on cells $(1, 1)$ and $(2, 1)$;
  • if $(i, i^*) = (3, 2)$, a piece is placed only on cell $(2, 1)$;
  • if $(i, i^*) = (3, 3)$, no new piece is placed.
In the last case, the second player cannot perform an operation on their turn (there is no cell with a piece on it), so the first player can always win by choosing this move.

Sample 2
Input
3 1
.
o
o
Output
Second

The operations available to the first player are $(i, i^*) = (2, 1), (2, 2), (3, 3)$.

If the first player chooses one of $(2, 2), (3, 3)$, the second player can win by removing the remaining piece.

If the first player chooses $(2, 1)$, pieces will be on cells $(1, 1)$ and $(3, 1)$. The second player performs the operation with $(i, i^*) = (3, 2)$, so that pieces are on cells $(1, 1)$ and $(2, 1)$. Then the first player can only remove one of the pieces, and the second player can win by removing the remaining piece.

Therefore, the second player can always win regardless of the first player's choice.

Sample 3
Input
4 4
o.oo
.oo.
oo.o
oo..
Output
First

Sample 4
Input
4 4
..oo
.oo.
oo.o
oo..
Output
Second

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