No.627 ランダムウォークの軌跡

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 285
作問者 : ats5515ats5515 / テスター : cielciel
0 ProblemId : 1892 / 出題時の順位表

問題文

ランダムウォークとは、一般に、次の位置がランダムに決まる運動のことをいいます。
ここでは以下のような、数直線上における点Pのランダムウォークを考えます。
・時刻$t=0$において、点Pは原点にある。
・ある時刻$t$にPが座標$x$にある時、時刻$(t+1)$には確率$\frac{1}{2}$で座標$(x+1)$に移動し、確率$\frac{1}{2}$で座標$(x-1)$へ移動する。
長さ$T$の数列$X_i$が与えられる。この数列が時刻$1$から時刻$T$における点Pの座標を順に記録したものとなり得るか判定してください。

入力

T
X_1
X_2
...
X_T

$1 \le T \le 100$
$-100 \le X_i \le 100$
1行目には数列の長さ$T$が与えられる。
続く$T$行には時刻$i$におけるPの座標$X_i$が与えられる。

出力

数列$X_i$が点Pの座標を順に記録したものとなり得るなら"T"を、なり得ないのなら"F"を出力してください。
最後に改行してください。

サンプル

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

サンプル2
入力
5
-1
-2
0
1
2
出力
F

-2から0へ1秒で移動できません

サンプル3
入力
4
0
1
2
1
出力
F

時刻0から時刻1において座標0から移動していないので不適です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。