No.33 アメーバがたくさん
nmnmnmnmnmnmnm問題文
\(N\)匹のアメーバが１直線上にいます。
各アメーバには初期座標が与えられます。
初期座標はすべて整数座標です。
アメーバは１秒後に３つに分裂します。
その後、１匹は現在の座標から\(-D\)だけ移動します。
もう１匹は現在の座標から\(+D\)だけ移動します。
最後の１匹はそのままの座標です。
また、アメーバは同じ座標に２匹以上いると、
合体して１匹になります。
最初に\(N\)匹いたアメーバが\(T\)秒後には
何匹になっているか答えなさい。
入力
N D T X0 X1 ... Xn-1
\(1\le N\le 100\) (Nは整数)
\(1\le D \le 10^9\)(Dは整数)
\(1\le T \le10^9\)(Tは整数)
-\(10^9\le Xi \le10^9\)(Xiはi番目のアメーバの初期位置)
出力
Ans
T秒後のアメーバの数Ansを返してください。
答えは３２ビット値におさまらないので注意してください。
改行を入れるのも忘れずに。
サンプル
サンプル1
入力
2 3 1 0 7
出力
6
最初、座標0に1匹、座標7に1匹アメーバがいます。
１秒後、アメーバは座標-3、0、3、4、7、10に合計6匹います。
サンプル2
入力
2 3 2 0 6
出力
7
最初、座標0に1匹、座標6に1匹アメーバがいます。
１秒後、アメーバは座標-3、0、3、6、9に合計5匹います。
座標3でアメーバが合体して1匹になりました。
２秒後、アメーバは座標-6、-3、0、3、6、9、12に合計7匹います。
サンプル3
入力
2 3 1 0 2
出力
6
最初、座標0に1匹、座標2に1匹アメーバがいます。
１秒後、アメーバは座標-3、-1、0、2、3、5に合計6匹います。
分裂後の移動中にアメーバが合体することはありません。
同じ座標にいるときのみ合体が発生します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。