No.33 アメーバがたくさん

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 98
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
2 ProblemId : 6 / 出題時の順位表

問題文

\(N\)匹のアメーバが1直線上にいます。
各アメーバには初期座標が与えられます。
初期座標はすべて整数座標です。
アメーバは1秒後に3つに分裂します。
その後、1匹は現在の座標から\(-D\)だけ移動します。
もう1匹は現在の座標から\(+D\)だけ移動します。
最後の1匹はそのままの座標です。
また、アメーバは同じ座標に2匹以上いると、
合体して1匹になります。
最初に\(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を返してください。
答えは32ビット値におさまらないので注意してください。
改行を入れるのも忘れずに。

サンプル

サンプル1
入力
2 3 1
0 7
出力
6

最初、座標0に1匹、座標7に1匹アメーバがいます。
1秒後、アメーバは座標-3、0、3、4、7、10に合計6匹います。

サンプル2
入力
2 3 2
0 6
出力
7

最初、座標0に1匹、座標6に1匹アメーバがいます。
1秒後、アメーバは座標-3、0、3、6、9に合計5匹います。
座標3でアメーバが合体して1匹になりました。
2秒後、アメーバは座標-6、-3、0、3、6、9、12に合計7匹います。

サンプル3
入力
2 3 1
0 2
出力
6

最初、座標0に1匹、座標2に1匹アメーバがいます。
1秒後、アメーバは座標-3、-1、0、2、3、5に合計6匹います。
分裂後の移動中にアメーバが合体することはありません。
同じ座標にいるときのみ合体が発生します。

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

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