問題一覧 > 通常問題

No.3090 NimNim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : yuusaan / テスター : 👑 amentorimaru
3 ProblemId : 11806 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-04 21:08:05

問題文

長さ $N$ の正整数列 $A_1,A_2,\dots ,A_N$ 、長さ $M$ の正整数列 $B_1,B_2, \dots ,B_M$ が与えられます。また、この与えられた時点での $A$ を「初期状態」と呼びます。

ゆ~さんとおさかなさんがこの配列を用いてゲームをします。ゲームは以下の手順をゆ~さんから交互に繰り返すというものです。

  • $A_i\ge 1$ であるような $1$ 以上 $N$ 以下の整数 $i$ を選択し、$A_i$ を $0$ 以上 $A_i$ 未満の整数に置き換える。
  • 置き換えた直後の配列 $A$ の全要素が $0$ であった場合、 $A$ を初期状態に戻し、$B_j\ge 1$ であるような $1$ 以上 $M$ 以下の整数 $j$ を選択し、$B_j$ を $0$ 以上 $B_j$ 未満の整数に置き換える。
    • ただし、この時にそのような配列 $B$ の要素がなかった場合、敗北する。敗北しなかった方が勝者となる。

このゲームは必ず有限回の操作で勝者が決定し、ゆ~さんかおさかなさん、ちょうど一方は最善手を尽くすことで必ず勝利することができます。それがどちらであるか判定してください。

入力

$N\ M$
$A_1 \ A_2 \ \dots \ A_N$
$B_1 \ B_2 \ \dots \ B_M$

制約

  • $1\le N,M \le 10^5$
  • $1\le A_i,B_j \le 10^6(1\le i \le N,1\le j \le M)$
  • 入力はすべて整数

出力

最善手を尽くすことで必ず勝利できるのがゆ~さんである場合 First と、おさかなさんである場合 Second と一行に出力し、最後に改行してください。

サンプル

サンプル1
入力
1 3
1
2 1 2
出力
First

一例としてゲームは以下のように進行します。

  • ゆ~さんが $A_1$ を $0$ に置き換える。 $A$ の全要素が $0$ になったため、$A$ を初期状態に戻し、 $B_2$ を $0$ に置き換える。
  • おさかなさんが $A_1$ を $0$ に置き換える。 $A$ の全要素が $0$ になったため、$A$ を初期状態に戻し、 $B_1$ を $0$ に置き換える。
  • ゆ~さんが $A_1$ を $0$ に置き換える。 $A$ の全要素が $0$ になったため、$A$ を初期状態に戻し、 $B_3$ を $0$ に置き換える。
  • おさかなさんが $A_1$ を $0$ に置き換える。 $A$ の全要素が $0$ になっため、$A$ を初期状態に戻すが、 配列 $B$ の全要素が $0$ であるため敗北し、ゆ~さんが勝利する。

この入力において、ゆ~さんは最善手を尽くすことで必ず勝利できます。そのため First と出力します。

サンプル2
入力
2 1
2 2
1
出力
Second

一例としてゲームは以下のように進行します。

  • ゆ~さんが $A_1$ を $0$ に置き換える。
  • おさかなさんが $A_2$ を $0$ に置き換える。 $A$ の全要素が $0$ になったため、 $A$ を初期状態に戻し、$B_1$ を $0$ に置き換える。
  • ゆ~さんが $A_1$ を $1$ に置き換える。
  • おさかなさんが $A_2$ を $0$ に置き換える。
  • ゆ~さんが $A_1$ を $0$ に置き換える。 $A$ の全要素が $0$ になったため、$A$ を初期状態に戻すが、配列 $B$ の全要素が $0$ であるため敗北し、おさかな さんが勝利する。

この入力において、おさかなさんは最善手を尽くすことで必ず勝利できます。そのため Second と出力します。

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