問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 411
作問者 : ats5515ats5515 / テスター : cielciel
1 ProblemId : 1892 / 出題時の順位表
問題文最終更新日: 2017-09-12 15:10:11

問題文

ランダムウォークとは、一般に、次の位置がランダムに決まる運動のことをいいます。
ここでは以下のような、数直線上における点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から移動していないので不適です。

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