問題一覧 > 通常問題

No.761 平均値ゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 : butsurizukibutsurizuki / テスター : matsu7874matsu7874
9 ProblemId : 2552 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-12-07 13:07:33

メモ

これはAdvent Calendar Contest 2018の9日目用の問題です。

問題

物理好きさんは、以下のようなゲームを考えました。

まず、$N$個の自然数$A_i$を用意します。
プレイヤーは以下の操作のどちらかを行えます。
(i)平均値以上の自然数を全て削除する
(ii)平均値未満の自然数を全て削除する

先攻から交互に操作を行い、先に操作が行えなくなった方が負けです。
なお、1つも数が削除されない操作は行うことができません。

両者が最善を尽くした時、勝つのはどちらか求めてください。

入力

$N$
$A_1$ $A_2$ $...$ $A_N$

・制約
$1 \le N \le 10^5$
$1 \le A_i \le 10^{12}(1 \le i \le N)$
$A_i \le A_{i+1}(1 \le i < N)$

出力

先攻が勝つ場合はFirst、後攻が勝つ場合はSecondを出力し、最後に改行してください。

サンプル

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

先手が先に1,2,3を削除すると後手が5,8のどちらを削除しても先手はもう片方を削除することで勝つことができます。

サンプル2
入力
7
1 3 3 4 575 1333 1640
出力
Second

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

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