No.761 平均値ゲーム
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : butsurizuki / テスター : matsu7874
タグ : / 解いたユーザー数 78
作問者 : butsurizuki / テスター : matsu7874
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。